The Modular Inversion Hidden Number Problem
Authors: D. Boneh, S. Halevi, and N. Howgrave-Graham
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 (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.
Reference:
In proceedings of Asiacrypt '01, LNCS Vol. 2248,
Springer-Verlag, pp. 36-51, 2001