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

A PARAMETRIC VERSION OF lll AND SOME CONSEQUENCES: PARAMETRIC SHORTEST AND CLOSEST VECTOR PROBLEMS

SIAM JOURNAL ON DISCRETE MATHEMATICS 2020年第4期34卷 2363-2387页

作者： Bogart, Tristram Goodrick, John Woods, Kevin Univ Los Andes Dept Matemat Bogota 11001000 Colombia

Given a parametric lattice with a basis given by polynomials in Z[t], we give an algorithm to construct an lll-reduced basis whose elements are eventually quasi-polynomial in t: that is, they are given by formulas that are piecewise polynomial in t (for sufficiently large t), such that each piece is given by a congruence class modulo a period. As a consequence, we show that there are parametric solutions of the shortest vector problem and closest vector problem that are also eventually quasi-polynomial in t.

关键词： lattices lll algorithm shortest vector problem parametric lattices

来源：评论

学校读者我要写书评

暂无评论

lll & ABC

引用

JOURNAL OF NUMBER THEORY 2004年第1期107卷 161-167页

作者： Dokchitser, T Univ Durham Dept Math Sci Durham DH1 3HP England

关键词： ABC-conjecture Szpiro conjecture lll algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved Herrmann-May's Attack with Merging Variables and Lower lll Bound 19th

Improved Herrmann-May's Attack with Merging Variables and Lo...

引用

19th International Conference on Information Security and Cryptology (Inscrypt)

作者： Cheng, Qingfeng Zhao, Chunzhi Cao, Jinzheng Wei, Fushan Informat Engn Univ Zhengzhou 450001 Peoples R China

ISBN: (纸本)9789819709441;9789819709458

Using side information to attack RSA is a practical method. In reality, it's possible to intercept some bits of an unknown divisor p of a known composite integer N for us. Then we can utilize Coppersmith's method to recover the whole p in polynomial time according to the work of Herrmann and May (Asiacrypt'08). In this paper, we analyze the idea of merging unknown bit blocks proposed by Herrmann and May in detail and indicate the cases where the blocks can be merged with a considerable reduction in the complexity of Herrmann-May's attack. In fact, the complexity of this attack depends on the output quality of the lll algorithm. For this, we purposely propose a lower upper bound of the length of lll-reduced vectors using probabilistic statistical methods. To be specific, considering the parallel to v(i)*parallel to/parallel to v(i vertical bar 1)*parallel to's as continuous random variables, we find that the middle parallel to v(i)*parallel to/parallel to v(i+1)*parallel to's after lll-reduction are almost independently and identically distributed. Then we utilize the central limit theorem to present a lower lll bound holding with probability close to 1. We have shown the advantages of merging variables and applying new bound by experiments. Finally, we combine these two points to propose the improved Herrmann-May's attack.

关键词： RSA Lattice lll algorithm Coppersmith's method

来源：评论

学校读者我要写书评

暂无评论

Cryptanalysis of Prime Power RSA with two private exponents

引用

Science China(Information Sciences) 2015年第11期58卷 59-66页

作者： ZHENG MengCe HU HongGang Key Laboratory of Electromagnetic Space Information Chinese Academy of Sciences School of Information Science and Technology University of Science and Technology of China

In this paper, we consider a variant of RSA schemes called Prime Power RSA with modulus N= prq for r 2, where p, q are of the same bit-size. May showed that when private exponent d<N;/（r+1）;or d < N;, N can be... 详细信息

In this paper, we consider a variant of RSA schemes called Prime Power RSA with modulus N= prq for r 2, where p, q are of the same bit-size. May showed that when private exponent d

关键词： cryptanalysis Prime Power RSA two private exponents lll algorithm Coppersmith’s techniques

来源：评论

学校读者我要写书评

暂无评论

Generalized cryptanalysis of RSA with small public exponent

引用

Science China(Information Sciences) 2016年第3期59卷 97-106页

作者： Mengce ZHENG Honggang HU Zilong WANG Key Laboratory of Electromagnetic Space Information Chinese Academy of Sciences (CAS) School of Information Science and Technology University of Science and Technology of China

In this paper, we demonstrate that there exist weak keys in the RSA public-key cryptosystem with the public exponent e = NαN0.5. In 1999, Boneh and Durfee showed that when α≈ 1 and the private exponent d = Nβ< N0.292, the system is insecure. Moreover, their attack is still effective for 0.5 < α < *** propose a generalized cryptanalytic method to attack the RSA cryptosystem with α≤0.5. For c = [（1-α）/α] and eγc≡ d（mod ec）, when γ, β satisfy γ < 1+1/c-1/（2αc） and β < αc +7/6- αγc-1/3（6α + 6αc + 1- 6αγc）1/2, we can perform cryptanalytic attacks based on the lll algorithm. The basic idea is an application of Coppersmith's techniques and we further adapt the technique of unravelled linearization, which leads to an optimized *** advantage is that we achieve new attacks on RSA with α 0.5 and consequently, there exist weak keys in RSA for most α.

关键词： cryptanalysis RSA lll algorithm Coppersmith’s techniques unravelled linearization

来源：评论

学校读者我要写书评

暂无评论

Small CRT-Exponent RSA Revisited

引用

JOURNAL OF CRYPTOLOGY 2019年第4期32卷 1337-1382页

作者： Takayasu, Atsushi Lu, Yao Peng, Liqiang Univ Tokyo Tokyo Japan Natl Inst Adv Ind Sci & Technol Tokyo Japan Chinese Acad Sci Inst Informat Engn State Key Lab Informat Secur Beijing Peoples R China Chinese Acad Sci Data Assurance & Commun Secur Res Ctr Beijing Peoples R China

Since May (Crypto'02) revealed the vulnerability of the small CRT-exponent RSA using Coppersmith's lattice-based method, several papers have studied the problem and two major improvements have been made. (1) Bleichenbacher and May (PKC'06) proposed an attack for small d(q) when the prime factor p is significantly smaller than the other prime factor q;the attack works for p < N-0.468. (2) Jochemsz and May (Crypto'07) proposed an attack for small d(p) and d(q) when the prime factors p and q are balanced;the attack works for d(p), d(q) < N-0.073. Even a decade has passed since their proposals, the above two attacks are still considered as the state of the art, and no improvements have been made thus far. A novel technique seems to be required for further improvements since it seems that the attacks have been studied with all the applicable techniques for Coppersmith's methods proposed by Durfee-Nguyen (Asiacrypt'00), Jochemsz-May (Asiacrypt'06), and Herrmann-May (Asiacrypt'09, PKC'10). Since it seems that the attacks have been studied with all the applicable techniques for Coppersmith's methods proposed by Durfee-Nguyen (Asiacrypt'00), Jochemsz-May (Asiacrypt'06), and Herrmann-May (Asiacrypt'09, PKC'10), improving the previous results seem technically hard. In this paper, we propose two improved attacks on the small CRT-exponent RSA: a small d(q) attack for p < N-0.5 (an improvement of Bleichenbacher-May's) and a small d(p) and d(q) attack for d(p), d(q) < N-0.122 (an improvement of Jochemsz-May's). The latter result is also an improvement of our result in the proceeding version (Eurocrypt'17);d(p), d(q) < N-0.091. We use Coppersmith's lattice-based method to solve modular equations and obtain the improvements from a novel lattice construction by exploiting useful algebraic structures of the CRT-RSA key generation equation. We explicitly show proofs of our attacks and verify the validities by computer experiments. In addition to the two main attacks, we also propose sm

关键词： CRT-RSA Cryptanalysis Coppersmith's method Lattices lll algorithm

来源：评论

学校读者我要写书评

暂无评论

Deterministic polynomial time equivalence between factoring and key-recovery attack on Takagi's RSA

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2008年第9期E91A卷 2356-2364页

作者： Kunihiro, Noboru Kurosawa, Kaoru Univ Electrocommun Chofu Tokyo 1828585 Japan Ibaraki Univ Hitachi Ibaraki 3168511 Japan

For RSA, May showed a deterministic polynomial time equivalence of computing d to factoring N(= pq). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA, where N = p(r)q while ed = 1 mod (p - 1)(q-1). In this paper, we show that a deterministic polynomial time equivalence also holds in this variant. The coefficient matrix T to which lll algorithm is applied is no longer lower triangular, and hence we develop a new technique to overcome this problem.

关键词： RSA factoring lll algorithm

来源：评论

学校读者我要写书评

暂无评论

A Unified Framework for Small Secret Exponent Attack on RSA

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2014年第6期E97A卷 1285-1295页

作者： Kunihiro, Noboru Shinohara, Naoyuki Izu, Tetsuya Univ Tokyo Kashiwa Chiba 2778561 Japan NICT Koganei Tokyo 1848795 Japan Fujitsu Labs Kawasaki Kanagawa 2118588 Japan

In this paper, we present a lattice based method on small secret exponent attack on the RSA scheme. Boneh and Durfee reduced the attack to finding the small roots of the bivariate modular equation: x(N + 1 + y)+1 0 (mod e), where N is an RSA modulus and e is the RSA public key and proposed a lattice based algorithm for solving the problem. When the secret exponent d is less than N-0.292, their method breaks the RSA scheme. Since the lattice used in the analysis is not full-rank, the analysis is not easy. Blomer and May proposed an alternative algorithm that uses a full-rank lattice, even though it gives a bound (d <= N-0.290) that is worse than Boneh-Durfee. However, the proof for their bound is still complicated. Herrmann and May, however, have given an elementary proof for the Boneh-Durfee's bound: d <= N-0.292. In this paper, we first give an elementary proof for achieving Blomer-May's bound: d <= N-0.290. Our proof employs the unravelled linearization technique introduced by Herrmann and May and is rather simpler than that of Blamer-May's proof. We then provide a unified framework - which subsumes the two previous methods, the Herrmann-May and the Blomer-May methods, as a special case - for constructing a lattice that can be are used to solve the problem. In addition, we prove that Boneh-Durfee's bound: d <= N-0.292 is still optimal in our unified framework.

关键词： lll algorithm small inverse problem RSA lattice-based cryptanalysis

来源：评论

学校读者我要写书评

暂无评论

Improving BDD Enumeration for LWE Problem Using GPU

引用

IEEE ACCESS 2020年 8卷 19737-19749页

作者： Esseissah, Mohamed S. Bhery, Ashraf Bahig, Hatem M. Ain Shams Univ Fac Sci Math Dept Comp Sci Div Cairo 11566 Egypt

In this paper, we present a GPU-based parallel algorithm for the Learning With Errors (LWE) problem using a lattice-based Bounded Distance Decoding (BDD) approach. To the best of our knowledge, this is the first GPU-based implementation for the LWE problem. Compared to the sequential BDD implementation of Lindner-Peikert and pruned-enumeration strategies by Kirshanova [1], our GPU-based implementation is almost faster by a factor 6 and 9 respectively. The used GPU is NVIDIA GeForce GTX 1060 6G. We also provided a parallel implementation using two GPUs. The results showed that our algorithm is scalable and faster than the sequential version (Lindner-Peikert and pruned-enumeration) by a factor of almost 13 and 16 respectively. Moreover, the results showed that our parallel implementation using two GPUs is more efficient than Kirshanova et al.'s parallel implementation using 20 CPU-cores.

关键词： Learning with error lattice-based cryptography lll algorithm shortest vector problem closest vector problem bounded distance decoding GPU cryptanalysis

来源：评论

学校读者我要写书评

暂无评论

Jug measuring: algorithms and complexity

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期396卷 50-62页

作者： Shieh, Min-Zheng Tsai, Shi-Chun Natl Chiao Tung Univ Dept Comp Sci Hsinchu 30050 Taiwan

We study the hardness of the optimal jug measuring problem. By proving tight lower and upper bounds on the minimum number of measuring steps required, we reduce an inapproximable NP-hard problem (i.e., the shortest GCD multiplier problem [G. Havas, J.-P. Seifert, The Complexity of the Extended GCD Problem, in: LNCS, vol. 1672, Springer, 1999]) to it. It follows that the optimal jug measuring problem is NP-hard and so is the problem of approximating the minimum number of measuring steps within a constant factor. Along the way, we give a polynomial-time approximation algorithm with an exponential error based on the well-known lll basis reduction algorithm. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Jug measuring problem inapproximability lll algorithm lattice problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：