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: