检索结果-内蒙古大学图书馆

Solving a class of modular polynomial equations and its relation to modular inversion hidden number problem and inversive congruential generator

引用

DESIGNS CODES AND CRYPTOGRAPHY 2018年第9期86卷 1997-2033页

作者： Xu, Jun Sarkar, Santanu Hu, Lei Huang, Zhangjie Peng, Liqiang Chinese Acad Sci Inst Informat Engn State Key State Lab Informat Secur Beijing 100093 Peoples R China Chinese Acad Sci Data Assurance & Commun Secur Res Ctr Beijing 100093 Peoples R China Indian Inst Technol Madras Dept Math Chennai 600036 Tamil Nadu India

In this paper we revisit the modular inversion hidden number problem (MIHNP) and the inversive congruential generator (ICG) and consider how to attack them more efficiently. We consider systems of modular polynomial equations of the form and show the relation between solving such equations and attacking MIHNP and ICG. We present three heuristic strategies using Coppersmith's lattice-based root-finding technique for solving the above modular equations. In the first strategy, we use the polynomial number of samples and get the same asymptotic bound on attacking ICG proposed in PKC 2012, which is the best result so far. However, exponential number of samples is required in the work of PKC 2012. In the second strategy, a part of polynomials chosen for the involved lattice are linear combinations of some polynomials and this enables us to achieve a larger upper bound for the desired root. Corresponding to the analysis of MIHNP we give an explicit lattice construction of the second attack method proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. We provide better bound than that in the work of PKC 2012 for attacking ICG. Moreover, we propose the third strategy in order to give a further improvement in the involved lattice construction in the sense of requiring fewer samples.

关键词： modular inversion hidden number problem Inversive congruential generator Lattice LLL algorithm Coppersmith's technique

来源：评论

学校读者我要写书评

暂无评论

Revisiting modular inversion hidden number problem and Its Applications

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2023年第8期69卷 5337-5356页

作者： Xu, Jun Sarkar, Santanu Hu, Lei Wang, Huaxiong Pan, Yanbin Chinese Acad Sci Inst Informat Engn State Key Lab Informat Secur Beijing 100085 Peoples R China Univ Chinese Acad Sci Sch Cyber Secur Beijing 100049 Peoples R China Indian Inst Technol Madras Chennai 600036 India Nanyang Technol Univ Sch Phys & Math Sci Div Math Sci Singapore 637371 Singapore Chinese Acad Sci Acad Math & Syst Sci Key Lab Math Mechanizat NCMIS Beijing 100190 Peoples R China

The modular inversion hidden number problem (MIHNP), which was proposed at Asiacrypt 2001 by Boneh, Halevi, and Howgrave-Graham, is summarized as follows: Assume that the delta most significant bits of z are denoted by MSB delta(z). The goal is to retrieve the hidden number alpha is an element of Z(p) given many samples (t(i), MSB delta((alpha + t(i))(-1) mod p)) for random t(i) is an element of Z(p). MIHNP is a significant subset of hidden number problems. Eichenauer and Lehn introduced the Inversive Congruential Generator (ICG) in 1986. It is basically characterized as follows: For iterated relations v(i+1) = (av(i)(-1) + b) mod p with a secret seed v(0) is an element of Z(p), each iteration produces MSB delta(v(i)+1) where i >= 0. The ICG family of pseudorandom number generators is a significant subclass of number-theoretic pseudorandom number generators. Sakai-Kasahara scheme is an identity-based encryption (IBE) system proposed by Sakai and Kasahara. It is one of the few commercially implemented identity-based encryption schemes. We explore the Coppersmith approach for solving a class of modular polynomial equations, which is derived from the recovery issue for the hidden number alpha in MIHNP and the secret seed v(0) in ICG, respectively. Take a positive integer n = d(3+o(1)) for some positive integer constant d. We propose a heuristic technique for recovering the hidden number a or secret seed v(0) with a probability close to 1 when delta/log(2) p > 1\d+1 + o(1\d). The attack's total time complexity is polynomial in the order of log(2) p, with the complexity of the LLL algorithm increasing as d(O)(d) and the complexity of the Grobner basis computation increasing as d(O)(n). When d > 2, this asymptotic bound surpasses the asymptotic bound delta/log(2) p > 1\3 established by Boneh, Halevi, and Howgrave-Graham at Asiacrypt 2001. This is the first time a more precise constraint for solving MIHNP is established, implying that the claim that MIHNP is difficult is v

关键词： modular inversion hidden number problem inversive congruential generator signature schemes lattice LLL algorithm coppersmith technique

来源：评论

学校读者我要写书评

暂无评论

New Results on modular inversion hidden number problem and Inversive Congruential Generator 1

引用

39th Annual International Cryptology Conference (CRYPTO)

作者： Xu, Jun Sarkar, Santanu Hu, Lei Wang, Huaxiong Pan, Yanbin Chinese Acad Sci Inst Informat Engn State Key Lab Informat Secur Beijing 100093 Peoples R China Chinese Acad Sci Data Assurance & Commun Secur Res Ctr Beijing 100093 Peoples R China Indian Inst Technol Madras Dept Math Sardar Patel Rd Chennai 600036 Tamil Nadu India Nanyang Technol Univ Singapore Sch Phys & Math Sci Div Math Sci Singapore Singapore Chinese Acad Sci Key Lab Math Mech NCMIS Acad Math & Syst Sci Beijing 100190 Peoples R China Univ Chinese Acad Sci Sch Cyber Secur Beijing 100049 Peoples R China

ISBN: (数字)9783030269487

ISBN: (纸本)9783030269487;9783030269470

The modular inversion hidden number problem (MIHNP), introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001, is briefly described as follows: Let MSB delta(z) refer to the delta most significant bits of z. Given many samples (t(i), MSB delta((alpha + t(i))(-1) mod p)) for random t(i) is an element of Z(p), the goal is to recover the hidden number alpha is an element of Z(p). 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 alpha in MIHNP. For any positive integer constant d, let integer n = d(3+o(1)). Given a sufficiently large modulus p, n + 1 samples of MIHNP, we present a heuristic algorithm to recover the hidden number a with a probability close to 1 when delta/log(2) p > 1/d + 1 + o(1/d). The overall time complexity of attack is polynomial in log(2) p, where the complexity of the LLL algorithm grows as d(O(d)) and the complexity of the Grobner basis computation grows as (2d)(O(n2)()). When d > 2, this asymptotic bound outperforms delta/log(2) p > 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 delta/log(2)p < 1/3 is broken. Moreover, we also get the best result for attacking the Inversive Congruential Generator (ICG) up to now.

关键词： modular inversion hidden number problem Inversive Congruential Generator Lattice LLL algorithm The Coppersmith technique

来源：评论

学校读者我要写书评

暂无评论

Improving Bounds on Elliptic Curve hidden number problem for ECDH Key Exchange 28th

Improving Bounds on Elliptic Curve Hidden Number Problem for...

引用

28th Annual International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)

作者： Xu, Jun Sarkar, Santanu Wang, Huaxiong Hu, Lei Chinese Acad Sci Inst Informat Engn State Key Lab Informat Secur Beijing 100093 Peoples R China Univ Chinese Acad Sci Sch Cyber Secur Beijing 100049 Peoples R China Indian Inst Technol Madras Sardar Patel Rd Chennai 600036 Tamil Nadu India Nanyang Technol Univ Sch Phys & Math Sci Div Math Sci Singapore Singapore

ISBN: (纸本)9783031229688;9783031229695

Elliptic Curve hidden number problem (EC-HNP) was first introduced by Boneh, Halevi and Howgrave-Graham at Asiacrypt 2001. To rigorously assess the bit security of the Diffie-Hellman key exchange with elliptic curves (ECDH), the Diffie-Hellman variant of EC-HNP, regarded as an elliptic curve analogy of the hidden number problem (HNP), was presented at PKC 2017. This variant can also be used for practical cryptanalysis of ECDH key exchange in the situation of sidechannel attacks. In this paper, we revisit the Coppersmith method for solving the involved modular multivariate polynomials in the Diffie-Hellman variant of EC-HNP and demonstrate that, for any given positive integer d, a given sufficiently large prime p, and a fixed elliptic curve over the prime field Fp, if there is an oracle that outputs about 1/d+1 of the most (least) significant bits of the x-coordinate of the ECDH key, then one can give a heuristic algorithm to compute all the bits within polynomial time in log2 p. When d > 1, the heuristic result 1/d+1 significantly outperforms both the rigorous bound 5 6 and heuristic bound 1 2. Due to the heuristics involved in the Coppersmith method, we do not get the ECDH bit security on a fixed curve. However, we experimentally verify the effectiveness of the heuristics on NIST curves for small dimension lattices.

关键词： hidden number problem Elliptic curve hidden number problem modular inversion hidden number problem Lattice Coppersmith method

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：