The Modular Inversion Hidden Number Problem

摘要

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{sub}i, MSB{sub}k ((α + x{sub}i){sub}(-1) mod p)〉 for random x{sub}i∈Z{sub}p the problem is to find α∈Z{sub}p (here MSB{sub}k(x) refers to the k most significant bits of x). We describe an algorithm for this problem when k > (log{sub}2 p)/3 and conjecture that the problem is hard whenever k < (log{sub}2 p)/3. We show that assuming hardness of some variants of this MIHNP problem leads to very efficient algebraic PRNGs and MACs.