The Modular Inversion Hidden Number Problem

Authors: D. Boneh, S. Halevi, and N. Howgrave-Graham

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 (x_i, msb_k[1/(A+x_i) mod p]) for random x_i in Z_p the problem is to find A in Z_p (here msb_k(x) refers to the k most significant bits of x). We describe an algorithm for this problem when k> (\log_2 p)/3 and conjecture that the problem is hard whenever k < (\log_2 p)/3. We show that assuming hardness of some variants of this MIHNP problem leads to very efficient algebraic PRNGs and MACs.

In proceedings of Asiacrypt '01, LNCS Vol. 2248, Springer-Verlag, pp. 36-51, 2001