Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors

Atsushi TAKAYASU; Noboru KUNIHIRO

doi:10.1587/transfun.E97.A.1259

Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors

Atsushi TAKAYASU, Noboru KUNIHIRO

Full Text Views

0

Cite this

Summary :

At CaLC 2001, Howgrave-Graham proposed the polynomial time algorithm for solving univariate linear equations modulo an unknown divisor of a known composite integer, the so-called partially approximate common divisor problem. So far, two forms of multivariate generalizations of the problem have been considered in the context of cryptanalysis. The first is simultaneous modular univariate linear equations, whose polynomial time algorithm was proposed at ANTS 2012 by Cohn and Heninger. The second is modular multivariate linear equations, whose polynomial time algorithm was proposed at Asiacrypt 2008 by Herrmann and May. Both algorithms cover Howgrave-Graham's algorithm for univariate cases. On the other hand, both multivariate problems also become identical to Howgrave-Graham's problem in the asymptotic cases of root bounds. However, former algorithms do not cover Howgrave-Graham's algorithm in such cases. In this paper, we introduce the strategy for natural algorithm constructions that take into account the sizes of the root bounds. We work out the selection of polynomials in constructing lattices. Our algorithms are superior to all known attacks that solve the multivariate equations and can generalize to the case of arbitrary number of variables. Our algorithms achieve better cryptanalytic bounds for some applications that relate to RSA cryptosystems.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1259-1272

Publication Date: 2014/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E97.A.1259

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Authors

Atsushi TAKAYASU
The University of Tokyo
Noboru KUNIHIRO
The University of Tokyo

Keyword

lattices, Coppersmith's method, small roots, implicit factorization, Multi-Prime Φ-Hiding Assumption, fault attacks, digital signatures, RSA

Cite this

Copy

Atsushi TAKAYASU, Noboru KUNIHIRO, "Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors" in IEICE TRANSACTIONS on Fundamentals, vol. E97-A, no. 6, pp. 1259-1272, June 2014, doi: 10.1587/transfun.E97.A.1259.
Abstract: At CaLC 2001, Howgrave-Graham proposed the polynomial time algorithm for solving univariate linear equations modulo an unknown divisor of a known composite integer, the so-called partially approximate common divisor problem. So far, two forms of multivariate generalizations of the problem have been considered in the context of cryptanalysis. The first is simultaneous modular univariate linear equations, whose polynomial time algorithm was proposed at ANTS 2012 by Cohn and Heninger. The second is modular multivariate linear equations, whose polynomial time algorithm was proposed at Asiacrypt 2008 by Herrmann and May. Both algorithms cover Howgrave-Graham's algorithm for univariate cases. On the other hand, both multivariate problems also become identical to Howgrave-Graham's problem in the asymptotic cases of root bounds. However, former algorithms do not cover Howgrave-Graham's algorithm in such cases. In this paper, we introduce the strategy for natural algorithm constructions that take into account the sizes of the root bounds. We work out the selection of polynomials in constructing lattices. Our algorithms are superior to all known attacks that solve the multivariate equations and can generalize to the case of arbitrary number of variables. Our algorithms achieve better cryptanalytic bounds for some applications that relate to RSA cryptosystems.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1259/_p

Copy

@ARTICLE{e97-a_6_1259,
author={Atsushi TAKAYASU, Noboru KUNIHIRO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors},
year={2014},
volume={E97-A},
number={6},
pages={1259-1272},
abstract={At CaLC 2001, Howgrave-Graham proposed the polynomial time algorithm for solving univariate linear equations modulo an unknown divisor of a known composite integer, the so-called partially approximate common divisor problem. So far, two forms of multivariate generalizations of the problem have been considered in the context of cryptanalysis. The first is simultaneous modular univariate linear equations, whose polynomial time algorithm was proposed at ANTS 2012 by Cohn and Heninger. The second is modular multivariate linear equations, whose polynomial time algorithm was proposed at Asiacrypt 2008 by Herrmann and May. Both algorithms cover Howgrave-Graham's algorithm for univariate cases. On the other hand, both multivariate problems also become identical to Howgrave-Graham's problem in the asymptotic cases of root bounds. However, former algorithms do not cover Howgrave-Graham's algorithm in such cases. In this paper, we introduce the strategy for natural algorithm constructions that take into account the sizes of the root bounds. We work out the selection of polynomials in constructing lattices. Our algorithms are superior to all known attacks that solve the multivariate equations and can generalize to the case of arbitrary number of variables. Our algorithms achieve better cryptanalytic bounds for some applications that relate to RSA cryptosystems.},
keywords={},
doi={10.1587/transfun.E97.A.1259},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1259
EP - 1272
AU - Atsushi TAKAYASU
AU - Noboru KUNIHIRO
PY - 2014
DO - 10.1587/transfun.E97.A.1259
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - At CaLC 2001, Howgrave-Graham proposed the polynomial time algorithm for solving univariate linear equations modulo an unknown divisor of a known composite integer, the so-called partially approximate common divisor problem. So far, two forms of multivariate generalizations of the problem have been considered in the context of cryptanalysis. The first is simultaneous modular univariate linear equations, whose polynomial time algorithm was proposed at ANTS 2012 by Cohn and Heninger. The second is modular multivariate linear equations, whose polynomial time algorithm was proposed at Asiacrypt 2008 by Herrmann and May. Both algorithms cover Howgrave-Graham's algorithm for univariate cases. On the other hand, both multivariate problems also become identical to Howgrave-Graham's problem in the asymptotic cases of root bounds. However, former algorithms do not cover Howgrave-Graham's algorithm in such cases. In this paper, we introduce the strategy for natural algorithm constructions that take into account the sizes of the root bounds. We work out the selection of polynomials in constructing lattices. Our algorithms are superior to all known attacks that solve the multivariate equations and can generalize to the case of arbitrary number of variables. Our algorithms achieve better cryptanalytic bounds for some applications that relate to RSA cryptosystems.
ER -