\input zb-basic
\input zb-ioport
\iteman{io-port 06043992}
\itemau{Kunihiro, Noboru; Shinohara, Naoyuki; Izu, Tetsuya}
\itemti{A unified framework for small secret exponent attack on RSA.}
\itemso{Miri, Ali (ed.) et al., Selected areas in cryptography. 18th international workshop, SAC 2011, Toronto, ON, Canada, August 11--12, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28495-3/pbk). Lecture Notes in Computer Science 7118, 260-277 (2012).}
\itemab
Summary: We address a lattice based method on small secret exponent attack on RSA scheme. Boneh and Durfee reduced the attack into finding small roots of a bivariate modular equation: $x(N+1+y)+1 \equiv 0 (\bmod\; e)$, where $N$ is an RSA moduli and $e$ is the RSA public key. Boneh and Durfee proposed a lattice based algorithm for solving the problem. When the secret exponent $d$ is less than $N ^{0.292}$, their method breaks RSA scheme. Since the lattice used in the analysis is not full-rank, the analysis is not easy. Bl\"omer and May gave an alternative algorithm. Although their bound $d \leq N ^{0.290}$ is worse than Boneh-Durfee result, their method used a full rank lattice. However, the proof for their bound is still complicated. Herrmann and May gave an elementary proof for the Boneh-Durfee's bound: $d \leq N ^{0.292}$. In this paper, we first give an elementary proof for achieving the bound of Bl\"omer-May: $d \leq N ^{0.290}$. Our proof employs unravelled linearization technique introduced by Herrmann and May and is rather simpler than Bl\"omer-May's proof. Then, we provide a unified framework to construct a lattice that are used for solving the problem, which includes two previous method: Herrmann-May and Bl\"omer-May methods as a special case. Furthermore, we prove that the bound of Boneh-Durfee: $d \leq N ^{0.292}$ is still optimal in our unified framework.
\itemrv{~}
\itemcc{}
\itemut{LLL algorithm; small inverse problem; RSA; lattice-based cryptanalysis}
\itemli{doi:10.1007/978-3-642-28496-0\_16}
\end