Header menu link for other important links
X
New Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator
Published in Springer Verlag
2019
Volume: 11692 LNCS
   
Pages: 297 - 321
Abstract
The Modular Inversion Hidden Number Problem (MIHNP), introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001, is briefly described as follows: Let$${\mathrm {MSB}}_{\delta }(z)$$ refer to the$$\delta $$ most significant bits of z. Given many samples$$\left(t_{i}, {\mathrm {MSB}}_{\delta }((\alpha + t_{i})^{-1} \bmod {p})\right) $$ for random$$t:i \in \mathbb {Z}_p$$, the goal is to recover the hidden number$$\alpha \in \mathbb {Z}_p$$. MIHNP is an important class of Hidden Number Problem. In this paper, we revisit the Coppersmith technique for solving a class of modular polynomial equations, which is respectively derived from the recovering problem of the hidden number$$\alpha $$ in MIHNP. For any positive integer constant d, let integer$$n=d^{3+o(1)}$$. Given a sufficiently large modulus p,$$n+1$$ samples of MIHNP, we present a heuristic algorithm to recover the hidden number$$\alpha $$ with a probability close to 1 when$$\delta /\log _2 p>\frac{1}{d\,+\,1}+o(\frac{1}{d})$$. The overall time complexity of attack is polynomial in$$\log _2 p$$, where the complexity of the LLL algorithm grows as$$d^{\mathcal {O}(d)}$$ and the complexity of the Gröbner basis computation grows as$$(2d)^{\mathcal {O}(n^2)}$$. When$$d> 2$$, this asymptotic bound outperforms$$\delta /\log _2 p>\frac{1}{3}$$ which is the asymptotic bound proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. It is the first time that a better bound for solving MIHNP is given, which implies that the conjecture that MIHNP is hard whenever$$\delta /\log _2 p<\frac{1}{3}$$ is broken. Moreover, we also get the best result for attacking the Inversive Congruential Generator (ICG) up to now. © 2019, International Association for Cryptologic Research.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
ISSN03029743
Open AccessNo
Concepts (9)
  •  related image
    Cryptography
  •  related image
    Heuristic algorithms
  •  related image
    Recovery
  •  related image
    CONGRUENTIAL GENERATORS
  •  related image
    Lattice
  •  related image
    LLL ALGORITHM
  •  related image
    MODULAR INVERSION
  •  related image
    THE COPPERSMITH TECHNIQUE
  •  related image
    Polynomials