Cryptology ePrint Archive: Report 2015/1140

Modular Inversion Hidden Number Problem- A Lattice Approach

Pranjal Dutta

Abstract: The Modular Inversion Hidden Number Problem (MIHNP) was introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001 (BHH’01). They provided two heuristics - in Method I, two-third of the output bits are required to solve the problem, whereas the more efficient heuristic (Method II) requires only one-third of the bits of the output. After more than a decade, here Sarkar in [28] identified that the claim in Method II is actually not correct and a detailed calculation justified that this method too requires two-third of the bits of the output, contrary to the claim in BHH’01. He reconstructed the lattice and give a bound which heuristically solve with half of the output bits. Although J.Xu et al in [29] solved it with only one-third of the output bits asymptotically but that technique is difficult to understand and implement. Here we essentially use similar idea of [28] but in a clever way such that it is a better bound although we solve the problem heuristically with only half of the output bits in asymptotic sense. This is lot easier to understand and implement. Also experimental results support the claim corresponding to our heuristics. In the last section we actually talk about a variant of this which seems to be hard to solve under lattice attack.

Category / Keywords: public-key cryptography /

Date: received 25 Nov 2015

Contact author: duttpranjal at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20151126:194100 (All versions of this report)

Short URL: ia.cr/2015/1140

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]