Notes for UMich EECS 598 (2015): Lecture 4

Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for lecture 4, Coppersmith, cryptanalysis.

In this note, I write down a more detailed and careful analysis of (and a correction to) the choice of parameters of Coppersmith algorithm as well as some nostalgia from my undergraduate study. Due to the nature of personal notes, I will not formally put references.

Update on 5 January 2020. I fixed my calculation on Coppersmith algorithm.

Coppersmith algorithm

The ‘full version’ of the algorithm upgrades the basic version as follows:

• consider a larger modulus Nm, where $m$ is a natural number to be determined later;
• consider polynomials of degree at most n−1=(m+1)d−1;
• use basis polynomials $b_{u,v}(x)=x^u{N}^{m-v}{f}^v(x)$ for $u=0,\dots ,d-1$ and v=0,…,m;
• ensure ∣v∣<nNm​, where $\mathbf{v}$ is a short non-zero vector in the lattice generated by bu,v​(Bx).

Note that the degrees of the basis polynomials are pairwise distinct, so if we order them by their degrees, the resulting lattice basis is triangular. This allows us to work out the bounds without too much labour.

Correction. The lecture note considers $(m+1)d$ basis polynomials of degree at most (m+1)d. Obviously there is an off-by-one error.

Let’s work out the real ‘full version’ of Coppersmith algorithm, with B=Θ(N1/d). The determinant is of the lattice is $$\det \mathcal{L}=\prod _{u=0}^{d-1}\prod _{v=0}^m{N}^{m-v}{B}^{u+dv}=N^{mn/2}{B}^{n(n-1)/2}.$$ Setting $m=\lfloor \frac{5d+(d-1){\log }_{2}N}{d^2}\rfloor$ and B=N1/d/8, we get $$\begin{array}{rl}& 2{\log }_2\left(2^{(n-1)/2}\sqrt{n}(\det \mathcal{L}{)}^{1/n}\frac{n}{N^m}\right)\\ =& \boxed{-2(n-1)+3{\log }_{2}n}+(1-1/d){\log }_{2}N\\ \le & \boxed{-n+5}+(1-1/d){\log }_{2}N<0.\end{array}$$ Therefore, the $\mathbf{v}$ output by LLL algorithm will have ∣v∣<nNm​, and we’re done.

Another attempt

The full version doesn’t cover the basic version. What happens if we remove the polynomials $b_{u,m}(Bx)$ for $u>0$ from the basis and confine ourselves with polynomials of degree at most n−1=md? Note that this modified version covers the basic algorithm by setting m=1.

It turns out that the same $B,m$ work. This version has slightly better performance — when we use the same B,m, the lattice dimension is smaller.

Cryptanalysis of RSA variants

Theorem 2.2. The theorem is interesting in the sense that it recovers the message. If we’re inspecting the IND-CPA security of the encryption scheme, it is immediate that the scheme cannot be IND-CPA secure due to the short padding length. An encryption of zero is small (<2me), and an encryption of one is large (>2me).

OAEP-RSA-3

OAEP-RSA-3 stands for optimal asymmetric encryption with padded RSA with exponent 3. The first time I heard of Coppersmith algorithm was in Fundamentals of Cryptography (taught by John P. Steinberger in the fall of 2016), when we were discussing OAEP. The OAE scheme, proposed by Bellare and Rogaway in 1994, had a wrong security proof of its IND-CCA security. This was pointed out by Shoup in 2000 and fixed for RSA with exponent 3. Soon afterwards, Fujisaki, Okamoto, Pointcheval and Stern proved that the construction with RSA (without restriction on exponents).

Shoup fixed the proof of OAEP-RSA-3 using Coppersmith algorithm. Funnily enough, usually Coppersmith is used to attack RSA-based cryptosystems. For me, it’s a beautiful twist that one can use it in the security reduction to prove security, and not until today did I fully know how the ‘decryption oracle’ is shimmed (i.e., implemented to fix the gap in the proof).