Modular Inversion Hidden Number Problem Revisited
In this paper we revisit the modular inversion hidden num ber problem, which is to find a hidden number given several integers and partial bits of the corresponding modular inverse integers (in the sense of modulo a prime number) of the sums of the known integers and that unknown integer.Along with another direction different to the previ ous study, we present a better polynomial time algorithm to solve the problem by utilizing a technique of priority queue computation and by constructing related lattices from algebraically dependent polynomials.Let n be the number of known integers, our algorithm assumes to know about (1/2+1/(n+1)!) of the bits of the modular inverses, which means about 2/3 of bits are required to be known in our algorithm when n =2, while in the case that only 2/3 of bits of the modular inverses are required to be known, the result of Boneh et al.and the latest algorithm of Ling et al.in Journal of Symbolic Computation need more samples (i.e., known integers and the corresponding partial bits).Our algorithm is also better for other n.
Hidden number problem modular inversion hidden number problem lattice LLL algorithm Coppersmiths algorithm
Jun Xu Lei Hu Zhangjie Huang Liqiang Peng
State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of
国际会议
福州
英文
537-551
2014-05-05（万方平台首次上网日期，不代表论文的发表时间）