** 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.