id: 06043992 dt: a an: 06043992 au: Kunihiro, Noboru; Shinohara, Naoyuki; Izu, Tetsuya ti: A unified framework for small secret exponent attack on RSA. so: 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). py: 2012 pu: Berlin: Springer la: EN cc: ut: LLL algorithm; small inverse problem; RSA; lattice-based cryptanalysis ci: li: doi:10.1007/978-3-642-28496-0_16 ab: 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ömer 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ömer-May: $d \leq N ^{0.290}$. Our proof employs unravelled linearization technique introduced by Herrmann and May and is rather simpler than Blömer-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ömer-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. rv: