System Overview Naccache–Stern knapsack cryptosystem

1 system overview

1.1 key generation
1.2 encryption
1.3 decryption

system overview

this system based on type of knapsack problem. specifically, underlying problem this: given integers c,n,p , v0,...,vn, find vector



x
∈
{
0
,
1

}

n




{\displaystyle x\in \{0,1\}^{n}}

such that

c
≡

∏

i
=
0


n



v

i



x

i





mod


p


{\displaystyle c\equiv \prod _{i=0}^{n}v_{i}^{x_{i}}\mod p}

the idea here when vi relatively prime , smaller modulus p problem can solved easily. observation allows decryption.

key generation

to generate public/private key pair

pick large prime modulus p.
pick positive integer n , 0 n, set pi ith prime, starting p0 = 2 , such




∏

i
=
0


n



p

i


<
p


{\displaystyle \prod _{i=0}^{n}p_{i}<p}

.
pick secret integer s < p-1, such gcd(p-1,s) = 1.
set




v

i


=



p

i



s




mod


p


{\displaystyle v_{i}={\sqrt[{s}]{p_{i}}}\mod p}

.

the public key p,n , v0,...,vn. private key s.

encryption

to encrypt n-bit long message m, calculate

c
=

∏

i
=
0


n



v

i



m

i





mod


p


{\displaystyle c=\prod _{i=0}^{n}v_{i}^{m_{i}}\mod p}

where mi ith bit of message m.

decryption

to decrypt message c, calculate

m
=

∑

i
=
0


n





2

i




p

i


−
1



×

(
gcd
(

p

i


,

c

s



mod


p
)
−
1
)



{\displaystyle m=\sum _{i=0}^{n}{\frac {2^{i}}{p_{i}-1}}\times \left(\gcd(p_{i},c^{s}\mod p)-1\right)}

this works because fraction

gcd
(

p

i


,

c

s



mod


p
)
−
1



p

i


−
1





{\displaystyle {\frac {\gcd(p_{i},c^{s}\mod p)-1}{p_{i}-1}}}

is 0 or 1 depending on whether pi divides c mod p.