Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/138108
Title: New results on modular inversion hidden number problem and inversive congruential generator
Authors: Xu, Jun
Sarkar, Santanu
Hu, Lei
Wang, Huaxiong
Pan, Yanbin
Keywords: Science::Mathematics
Issue Date: 2019
Source: Xu, J., Sarkar, S., Hu, L., Wang, H., & Pan, Y. (2019). New results on modular inversion hidden number problem and inversive congruential generator. Advances in Cryptology – CRYPTO 2019, 297-321. doi:10.1007/978-3-030-26948-7_11
Abstract: The Modular Inversion Hidden Number Problem (MIHNP), introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001, is briefly described as follows: Let MSB𝛿(𝑧) refer to the δ most significant bits of z. Given many samples(𝑡𝑖,MSB𝛿((𝛼+𝑡𝑖)−1mod𝑝))(ti,MSBδ((α+ti)−1modp)) for random 𝑡𝑖∈ℤ𝑝, the goal is to recover the hidden number 𝛼∈ℤ . MIHNP is an important class of Hidden Number Problem. In this paper, we revisit the Coppersmith technique for solving a class of modular polynomial equations, which is respectively derived from the recovering problem of the hidden number α in MIHNP. For any positive integer constant d, let integer 𝑛=𝑑3+𝑜(1) . Given a sufficiently large modulus p, n+1 samples of MIHNP, we present a heuristic algorithm to recover the hidden number$$\alpha $$ with a probability close to 1 when𝛿/log2𝑝>1𝑑+1+𝑜(1𝑑). The overall time complexity of attack is polynomial in log2𝑝, where the complexity of the LLL algorithm grows as dO(d) and the complexity of the Gröbner basis computation grows as(2d)O(n2). When 𝑑>2, this asymptotic bound outperforms 𝛿/log2𝑝>1/3 which is the asymptotic bound proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. It is the first time that a better bound for solving MIHNP is given, which implies that the conjecture that MIHNP is hard whenever 𝛿/log2𝑝<1/3 is broken. Moreover, we also get the best result for attacking the Inversive Congruential Generator (ICG) up to now.
URI: https://hdl.handle.net/10356/138108
ISBN: 9783030269470
DOI: 10.1007/978-3-030-26948-7_11
Rights: © 2019 International Association for Cryptologic Research. All rights reserved. This paper was published in Advances in Cryptology – CRYPTO 2019 and is made available with permission of International Association for Cryptologic Research.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:NTC Conference Papers

SCOPUSTM   
Citations 50

1
Updated on Jan 28, 2023

Web of ScienceTM
Citations 50

2
Updated on Jan 21, 2023

Page view(s)

271
Updated on Feb 3, 2023

Download(s) 50

39
Updated on Feb 3, 2023

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.