Explicit expression for decryption in a generalisation of the Paillier scheme

O. O. Obi, F. H. Ali, E. Stipidis

    Research output: Contribution to journalArticlepeer-review


    The Paillier scheme encryption, (m, r) → c=gm rN mod N2, where m is in ZN, r is in ZN *, N=pq (p, q being strong primes) and g is an element of Z*N2 of order a multiple of N, is decrypted by mmodN= (L(cλ mod N2)/L(g λ mod N2)) mod N, where L is defined on all u in Z*N2 such that umodN = 1, by L(u)=(u-1)/N. In the generalisation of the scheme by Damgård and Jurik, the modulus N2 is replaced by N1+s, 1 ≤ s < p, q, but an explicit expression for decryption was not given. Rather a method, the only one known so far, was found for decryption, by first encoding the ciphertext and then using an algorithm of a quadratic order of complexity in s to extract the plaintext part by part therefrom. This gap is filled. An explicit expression for decryption in this setting is presented, which is more straight forward, linear in s in complexity and hence more efficient and reduces to the original Paillier L function for s=1.

    Original languageEnglish
    Pages (from-to)163-166
    Number of pages4
    JournalIET Information Security
    Issue number4
    Publication statusPublished - 1 Dec 2007


    Dive into the research topics of 'Explicit expression for decryption in a generalisation of the Paillier scheme'. Together they form a unique fingerprint.

    Cite this