The modular inversion hidden number problem

Authors: Dan Boneh, Shai Halevi,and Nick Howgrave-Graham.

Reference: ASIACRYPT 2001

Abstract: We study a class of problems called Modular Inverse Hidden Number Problems (MIHNPs). The basic problem in this class is the following: Given many pairs (xi,MSB_k((a+xi)^{-1} mod p)) for random xi's in Zp, the problem is to find a. (Here MSB_k(x) refers to the k most significant bits of x). We describe an algorithm for this problem when k > (log p)/3 and conjecture that the problem is hard whenever k < (log p)/3. We show that assuming hardness of some variants of this MIHNP problem leads to very efficient algebraic PRNGs and MACs.

Keywords: Hidden number problems, PRNG, MAC, Approximations, Modular inversion, Lattices, Coppersmith's attack

Availability: Paper available as Compressed PostScript (89 Kbyte) and PDF (190 Kbyte).

Shai Halevi's home page.