The Naccache–Stern cryptosystem is a homomorphic public-key cryptosystem whose security rests on the higher residuosity problem . The Naccache–Stern cryptosystem was discovered by David Naccache and Jacques Stern in 1998.
Scheme Definition
Like many public key cryptosystems , this scheme works in the group
(
Z
/
n
Z
)
∗ ∗ -->
{\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}
where n is a product of two large primes . This scheme is homomorphic and hence malleable .
Key Generation
Pick a family of k small distinct primes p 1 ,...,p k .
Divide the set in half and set
u
=
∏ ∏ -->
i
=
1
k
/
2
p
i
{\displaystyle u=\prod _{i=1}^{k/2}p_{i}}
and
v
=
∏ ∏ -->
k
/
2
+
1
k
p
i
{\displaystyle v=\prod _{k/2+1}^{k}p_{i}}
.
Set
σ σ -->
=
u
v
=
∏ ∏ -->
i
=
1
k
p
i
{\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i}}
Choose large primes a and b such that both p = 2au +1 and q =2bv +1 are prime.
Set n =pq .
Choose a random g mod n such that g has order φ(n )/4.
The public key is the numbers σ,n ,g and the private key is the pair p ,q .
When k =1 this is essentially the Benaloh cryptosystem .
Message Encryption
This system allows encryption of a message m in the group
Z
/
σ σ -->
Z
{\displaystyle \mathbb {Z} /\sigma \mathbb {Z} }
.
Pick a random
x
∈ ∈ -->
Z
/
n
Z
{\displaystyle x\in \mathbb {Z} /n\mathbb {Z} }
.
Calculate
E
(
m
)
=
x
σ σ -->
g
m
mod
n
{\displaystyle E(m)=x^{\sigma }g^{m}\mod n}
Then E(m) is an encryption of the message m .
Message Decryption
To decrypt, we first find m mod p i for each i , and then we apply the Chinese remainder theorem to calculate m mod
σ σ -->
{\displaystyle \sigma }
.
Given a ciphertext c , to decrypt, we calculate
c
i
≡ ≡ -->
c
ϕ ϕ -->
(
n
)
/
p
i
mod
n
{\displaystyle c_{i}\equiv c^{\phi (n)/p_{i}}\mod n}
. Thus
c
ϕ ϕ -->
(
n
)
/
p
i
≡ ≡ -->
x
σ σ -->
ϕ ϕ -->
(
n
)
/
p
i
g
m
ϕ ϕ -->
(
n
)
/
p
i
mod
n
≡ ≡ -->
g
(
m
i
+
y
i
p
i
)
ϕ ϕ -->
(
n
)
/
p
i
mod
n
≡ ≡ -->
g
m
i
ϕ ϕ -->
(
n
)
/
p
i
mod
n
{\displaystyle {\begin{matrix}c^{\phi (n)/p_{i}}&\equiv &x^{\sigma \phi (n)/p_{i}}g^{m\phi (n)/p_{i}}\mod n\\&\equiv &g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\mod n\\&\equiv &g^{m_{i}\phi (n)/p_{i}}\mod n\end{matrix}}}
where
m
i
≡ ≡ -->
m
mod
p
i
{\displaystyle m_{i}\equiv m\mod p_{i}}
.
Since p i is chosen to be small, m i can be recovered by exhaustive search, i.e. by comparing
c
i
{\displaystyle c_{i}}
to
g
j
ϕ ϕ -->
(
n
)
/
p
i
{\displaystyle g^{j\phi (n)/p_{i}}}
for j from 1 to p i -1.
Once m i is known for each i , m can be recovered by a direct application of the Chinese remainder theorem.
Security
The semantic security of the Naccache–Stern cryptosystem rests on an extension of the quadratic residuosity problem known as the higher residuosity problem .
References
Naccache, David; Stern, Jacques (1998). "A New Public Key Cryptosystem Based on Higher Residues". Proceedings of the 5th ACM Conference on Computer and Communications Security . CCS '98. ACM. pp. 59–66. doi :10.1145/288090.288106 . ISBN 1-58113-007-4 .
Algorithms
Theory Standardization Topics