Tampere University of Technology

TUTCRIS Research Portal

Non-injective knapsack public-key cryptosystems

Research output: Contribution to journalArticleScientificpeer-review


Original languageEnglish
Pages (from-to)401-422
Number of pages22
JournalTheoretical Computer Science
Issue number1-2
Publication statusPublished - 2001
Publication typeA1 Journal article-refereed


Two public-key 0-1 knapsack cryptosystems are proposed, that have so high a density and use so weak a modular multiplication as a trapdoor, that known attacks can be avoided. Decryption is fairly slow and may produce more than one decipherment, but all alternative decipherments can be found. Disambiguating protocols are needed to determine the correct decipherment. It is suggested to use also redundancy for this purpose. In the first system, the initial knapsack is constructed from the powers of two, which are multiplied by a constant and reduced with respect to a modulus to a specific range, thus producing the «easy» knapsack. Then weak modular multiplication is used as a trapdoor transformation with respect to another modulus, which is typically smaller than some or all of the elements of the easy knapsack. The second knapsack is constructed iteratively from modularly injective or nearly injective components. Decryption of small components is based on look-up tables. The specific form of the proposal uses also one large non-injective component, which is generated and decrypted in a way that resembles superincrease.

ASJC Scopus subject areas


  • Cryptosystem, Knapsack, Non-injectivity, Public key

Publication forum classification