Public-key cryptography
A new public-key crypto system
via Mersenne numbers
Divesh Aggarwal

joint work with Antoine Joux, Anupam Prakash and Miklos Santha-Introduced by Diffie and Hellman in [DH76]-Many candidates over the years-The quest in the recent years has shifted to advanced primitives-In this work, we propose an arguably simpler PKC scheme.
-We also believe it is secure against quantum attacks.

Mersenne cryptosystem- Belongs to the Ring and Noise family with- NTRU
- Code-based crypto- Ring LWE based crypto- With a different Ring: Z/pZ (p Mersenne prime),and- a different Noise: Hamming weight mod p.

Mersenne cryptosystem
Mersenne primes: They are primes of the form
p=2n-1, where n is a prime, and is named after Marin
Mersenne, a French mathematician, who studied themin the early 17th century. (Wikipedia)

Main advantage of the cryptosystem: Simplicity

Mersenne ring anddistance- Ring Z/pZ
- p a Mersenne prime, i.e., 2n-1
Let :- Rp(X)=rep of X in [0,p-1]- HW(X)=num of 1 in binary rep of X mod p

Some properties of arithmetic mod p
1) HW(X+Y) ≤ HW(X) + HW(Y)11010100111001+00000000001000—————————————————=11010101000001
2) For all i, HW(X 2i ) = HW(X)3) HW(XY) ≤ HW(X) x HW(Y)Induction
4) HW(-X) = n-HW(X)

Hard problem
Warm Up
Single bit version

p = 2^n - 1,h << nf, g are numbers mod p with few (< h) 1s in binary rep.
H=f/g [mod p]
Assumption: Given H, obtain f, g.

Single bit version
H=f/g [mod p],
PK = H, SK = g(f and g containing few 1s, i.e. ≤h)Encryption

Decryption

a and b with few 1s

gC = ± [a f + b g]
Compute HW(gC)
Small => 0Large => 1

C0 = Enc(0) = (a H + b)
C1 = Enc(1) = -(a H + b)

Toy Example
p=231-1= 2147483647 = 0x7FFFFFFF
H=f/g=0x8002000/0x20000008=0x42E8BE0F
Encryption
a=0x80800
b=0x40000080
C = Enc(0) = (a H + b)
=Ox766CAB3A

Decryption
gC = 0x110084A6
HW(gC) = 8 (< 15) => 0Correctness of decryption
For correctness, we need n > 4 h2
g(aH+b) ≡ af+bg [mod p]
HW(Rp(af+bg)) ≤ HW(a)HW(f)+HW(b)HW(g)≤ 2 h2 ≤ n/2
HW(Rp(-(af+bg))) = n - HW(Rp(af+bg))≥ n/2

Multi-bit version
underlying encryption

Change public/private key
H=f/g [mod p]

f (-1/H) + g = 0 [mod p]
I.e. f R + g = 0

T=f R + g [mod p] (R fully random)

Mersenne(basic multi-bit encrypt)
T=fR+g [mod p] (R fully random)
Encryption

Decryption of (C1,Z)

C1=a R + b1
C2=a T + b2
Z = C2⊕E(m)Enc(m)=(C1, Z)

C2’=f C1
m=D(C2’⊕Z)

E and D : Error correction code

Multi-bit encryption
Analysis of decryption
C2 = a T + b2 = afR + (ag+b2)
C2’= f C1 = f (a R + b1) = afR + b1 f
HW(C2⊕C2’) ≤ Hdist(C2,afR) + Hdist(C2’,afR)

Thus Dec(Enc(m) ⊕ small error) = m
Heuristic : Error is well distributed
Allows to use simple repetition code

Analysis of decryption
LEMMA: Let U be a random n-bit string and let x
be an n-bit string of Hamming weight h. ThenPr[Hdist(U, U + x) > 2 h (1 + c)]<negligible

EXAMPLE:
11001010101011110101110101000111110100101+000010000001000100000000100010000100010
11010010101101111101110101101001111000111

Choice of error-correcting code
-Thus, the total number of errors we expect is at moste = 2 (2 h2 + h)
-We need an ECC correcting e out of n errors-Can use Reed Muller codes, and n = O(h2)-The number e is clearly an overestimate of the no. oferrors in practice

Recommended parametersn = 756839
Low HW parameter h=256
Encode 256 bits:with 2048-repetition coding-Also, we expect the errors to be distributed randomly

Heuristics

Hard Problem
Distinguish
Hidden low weight

Random tuple(R1, R2, aR1+b1, a R2+b2)(R1, R2, R3, R4)a, b1, b2 with low HWCCA-KEM
Alice

Multi-bit Mersenne
CCA-KEM

Bob
Alice’s PK

Alice’s SK
DecapsCiphertext

Shared Key

Alice
Alice’s SK
Decaps

CCA-KEM underactive attack

Shared Key

Mersenne KEM encaps(with CCA security)
S = Random seed

Invalid Ciphertext

EveAlice’s PK⊥

Encaps1) Initialize PRG from s2) Produce pseudo random shared secret
3) Run basic encryption of s(getting a, b1, b2 from PRG)
4) Output (C1, Z)Mersenne KEM decaps(with CCA security)
1) Run basic decryption on (C1, Z)
2) Re-encapsulate from s3) Compare and Outputa) Shared secretb) or ⊥Best Known attacks [BCGN17, BDJW18](for proposed params)
Trivial :nh((Best Classical : At least 22h
Best Quantum : At least 2h

Future Work
-Cryptanalysis-Improve efficiency without compromising security

Thank You