Paper 2015/778

Modular Inversion Hidden Number Problem -- Correction and Improvements

Santanu Sarkar

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 we identify that the claim in Method II is actually not correct and a detailed calculation justifies that this method too requires two-third of the bits of the output, contrary to the claim in BHH'01. Further, we show that using the same relations as in Boneh et al., one can reconstruct the lattice so that the problem can be heuristically solved by the knowledge of five-eighth of the bits. Finally, we could accumulate additional relations to solve the problem heuristically with only half of the output bits in asymptotic sense. Experimental results support the claim corresponding to our heuristics.

Metadata
Available format(s)
-- withdrawn --
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
sarkar santanu bir @ gmail com
History
2016-04-26: withdrawn
2015-08-04: received
See all versions
Short URL
https://ia.cr/2015/778
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.