Thread by @fgrosshans

Now seated @ScienceSorbonne for a talk by Antoine Joux on “The Mersenne Cryptosystem”, his submission to the @usnistgov #postquantum standardization effort¹
#LTQI
———
¹ apparently saying “competition” is discouraged

@ScienceSorbonne @usnistgov Antoine Joux starts by recalling basics of public key crypto, quantum computing, Grover and Shor’s algorithms and tehir consequence (almost none for Grover, Diffie-Hellman and RSA break by Shor )
#LTQI

@ScienceSorbonne @usnistgov Antoine Joux: The Mersten system is inside the Rang and Noise family, with (NTRU, Codes, Ideal LAttices, TLWE)

The ring here is ℤ/pℤ with p Mersenne prime (p=2ⁿ-1). It was initially a simplification of the above schemes, but we couldn’t break it, so we proposed it.
#LTQI

@ScienceSorbonne @usnistgov Antoine Joux:
Nice properties of arithmetics mod p
Reduction mod p is very easy.
HW(X+Y)≤HW(X)+HW(Y)
(HW:=Hamming weight)
HW(XY)≤HW(X)×HW(Y)
HW(Rp(X))≤HW(X)
Rp(X) = representent of X ∈[0,p-1]
X≠0⇒ HW(-X)=n-HW(X)
#LTQI

@ScienceSorbonne @usnistgov Antoine Joux strats a warm up with single bit (±)

H=f/g [mod p], f and g contain few (≤h) 1s
H public key
f,g: private key

a,b random with few 1s
Encryption: C=±(aH+b)
Decryption: gC=±(af+bg): The number of 1s (small or big) tells you whether the bit is + or -
#LTQI

@ScienceSorbonne @usnistgov Antoine Joux has a nice small example with p=2³¹-1, but I couldn’t type fast enoug...

HW rules above allows to show that it works with small=≤2h², and big=≥n-2h²
#LTQI

@ScienceSorbonne @usnistgov Antoine Joux expands it for more bits.
Initially, we had fR+g=0, with R=-1/H. Nouw we move to T=fR+g, with R random. Public key is (T,R).

Enc/Dec: En/De-coding
Encryption;
C₁=aR+b₁
C₂=a T+b₂
E(m)=(C₁,C₂⊕(Enc(m))

Decryption (I guess):
C₂'=fC₁ which is almost C₂. #LTQI

@ScienceSorbonne @usnistgov Antoine Joux: The encoding allows to correct the few errors.
But the above scheme is only secure against passive adversaries. He uses CCA-KEM encapsulation/decpasulation to get CCA security.
#LTQI

@ScienceSorbonne @usnistgov Antoine Joux: CCA-KEM uses a pseudo random generator PRNG of seed s. The shared secret and the “random parameters” come from the PRNG, and s is encrypted using the basic encryption.
#LTQI

@ScienceSorbonne @usnistgov Antoine Joux: The parameter:
n=756839
low HW threshold h=256

The hidden problem is distinguish
(R₁, R₂, aR₁+b₁, aR₂+b₂) from (R₁, R₂, R₃, R₄) with a, b₁, b₂ of small HW

Best known attacks worse than 2^2h (classical) and 2^h (quantum)
#LTQI