The Damgård–Jurik cryptosystem is a generalization of the Paillier cryptosystem. It uses computations modulo
Contents
Key generation
- Choose two large prime numbers p and q randomly and independently of each other.
- Compute
n = p q andλ = lcm ( p − 1 , q − 1 ) . - Choose an element
g ∈ Z n s + 1 ∗ g = ( 1 + n ) j x mod n s + 1 j relative prime ton andx ∈ H . - Using the Chinese Remainder Theorem, choose
d such thatd mod n ∈ Z n ∗ d = 0 mod λ . For instanced could beλ as in Paillier's original scheme.
Encryption
- Let
m be a message to be encrypted wherem ∈ Z n s - Select random
r wherer ∈ Z n s + 1 ∗ - Compute ciphertext as:
c = g m ⋅ r n s mod n s + 1
Decryption
- Ciphertext
c ∈ Z n s + 1 ∗ - Compute
c d m o d n s + 1 c d = ( g m r n s ) d = ( ( 1 + n ) j m x m r n s ) d = ( 1 + n ) j m d m o d n s ( x m r n s ) d m o d λ = ( 1 + n ) j m d m o d n s - Apply a recursive version of the Paillier decryption mechanism to obtain
j m d . Asj d is known, it is possible to computem = ( j m d ) ⋅ ( j d ) − 1 m o d n s
Simplification
At the cost of no longer containing the classical Paillier cryptosystem as an instance, Damgård–Jurik can be simplified in the following way:
In this case decryption produces