Non-injective knapsack public-key cryptosystems

    Research output: Contribution to journalArticleScientificpeer-review

    5 Citations (Scopus)


    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.

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


    • Cryptosystem
    • Knapsack
    • Non-injectivity
    • Public key

    Publication forum classification

    • No publication forum level

    ASJC Scopus subject areas

    • Computational Theory and Mathematics


    Dive into the research topics of 'Non-injective knapsack public-key cryptosystems'. Together they form a unique fingerprint.

    Cite this