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

A physical study of the lll algorithm

Journal of Number Theory 2023年 244卷 339-368页

作者： Ding, Jintai Kim, Seungki Takagi, Tsuyoshi Wang, Yuntao Yang, Bo-yin Tsinghua University China University of Cincinnati United States University of Tokyo Japan Osaka University Japan Academia Sinica China

This paper presents a study of the lll algorithm from the perspective of statistical physics. Based on our experimental and theoretical results, we suggest that interpreting lll as a sandpile model may help understand much of its mysterious behavior. In the language of physics, our work presents evidence that lll and certain 1-d sandpile models with simpler toppling rules belong to the same universality class. This paper consists of three parts. First, we introduce sandpile models whose statistics imitate those of lll with compelling accuracy, which leads to the idea that there must exist a meaningful connection between the two. Indeed, on those sandpile models, we are able to prove the analogues of some of the most desired statements for lll, such as the existence of the gap between the theoretical and the experimental RHF bounds. Furthermore, we test the formulas from finite-size scaling theory (FSS) against the lll algorithm itself, and find that they are in excellent agreement. This in particular explains and refines the geometric series assumption (GSA), and allows one to extrapolate various quantities of interest to the dimension limit. In particular, we obtain the estimate that the empirical average RHF converges to ≈1.02265 as the dimension goes to infinity. © 2022 The Author(s)

关键词： Finite-size scaling theory Lattice reduction lll algorithm Sandpile models

来源：评论

学校读者我要写书评

暂无评论

Algebraic number fields and the lll algorithm

引用

JOURNAL OF SYMBOLIC COMPUTATION 2024年 121卷

作者： Uray, M. J. Eotvos Lorand Univ Fac Informat Dept Comp Algebra Pazmany Peter Setany 1-C H-1117 Budapest Hungary

In this paper we analyze the computational costs of various operations and algorithms in algebraic number fields using exact arithmetic. Let K be an algebraic number field. In the first half of the paper, we calculate the running time and the size of the output of many operations in K in terms of the size of the input and the parameters of K. We include some earlier results about these, but we go further than them, e.g. we also analyze some R-specific operations in K like less-than comparison. In the second half of the paper, we analyze two algorithms: the Bareiss algorithm, which is an integer-preserving version of the Gaussian elimination, and the lll algorithm, which is for lattice basis reduction. In both cases, we extend the algorithm from Zn to Kn, and give a polynomial upper bound on the running time when the computations in K are performed exactly (as opposed to floating-point approximations). (c) 2023 Elsevier Ltd. All rights reserved.

关键词： Algebraic number field lll algorithm Bareiss algorithm Exact computation Running time analysis

来源：评论

学校读者我要写书评

暂无评论

Performance Evaluation of Lower Complexity Hybrid-Fix-and-Round-lll algorithm for MIMO System

引用

KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS 2018年第6期12卷 2554-2580页

作者： Lv, Huazhang Network Technol Res Inst China Unicorn Innovat Ctr 5G Beijing Peoples R China

Lenstra-Lenstra-Lovasz (lll) is an effective receiving algorithm for Multiple-Input-Multiple-Output (MIMO) systems, which is believed can achieve full diversity in MIMO detection of fading channels. However, the lll algorithm features polynomial complexity and shows poor performance in terms of convergence. The reduction of algorithmic complexity and the acceleration of convergence are key problems in optimizing the lll algorithm. In this paper, a variant of the lll algorithm, the Hybrid-Fix-and-Round lll algorithm, which combines both fix and round measurements in the size reduction procedure, is proposed. By utilizing fix operation, the algorithmic procedure is altered and the size reduction procedure is skipped by the hybrid algorithm with significantly higher probability. As a consequence, the simulation results reveal that the Hybrid-Fix-and-Round-lll algorithm carries a faster rate of convergence compared to the original lll algorithm, and its algorithmic complexity is at most one order lower than original lll algorithm in real field. Comparing to other families of lll algorithm, Hybrid-Fix-and-Round-lll algorithm can make a better compromise in performance and algorithmic complexity.

关键词： lll algorithm lattice reduction algorithmic complexity size reduction MIMO system

来源：评论

学校读者我要写书评

暂无评论

Storage efficient algorithm for Hermite Normal Form using lll

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2021年 613卷 183-200页

作者： Cho, Gook Hwa Lee, Hyang-Sook Lim, Seongan Kim, Yoonjeong Ewha Womans Univ Inst Math Sci Seoul South Korea Ewha Womans Univ Dept Math Seoul South Korea DuDu Informat Tech Inc Seoul South Korea

Computing HNF has a long history, but designing a storage efficient algorithm is a challenging issue for matrices of large sizes. One of the main challenges in the design of storage efficient HNF algorithm is to control the rank and the size of the intermediate input. In our proposed algorithm, we use a multiple extended gcd algorithm and show that the rank of the intermediate input matrix decreases as the number of iteration increases. The determinant of the intermediate input matrix of our algorithm is a factor of the determinant d of the input matrix and thus size reduction modulo d can be done in the computations of our algorithm. By using a lattice reduction algorithm and a proven quality of lll reduced basis, we prove that the storage of the intermediate input matrix B-k of our algorithm is less than (n - k + 1)(n - k + 1)(n-k)/4 + log(2) d) in bits. Therefore, it is expected that a smaller storage for kth iteration is required as k closes to n. We compare the intermediate computations of our algorithm to MW-type algorithm which has an optimal asymptotic space requirement. Our experimental example and results on intermediate size suggest that the intermediate storage of our HNF algorithm is comparable to MW-type algorithm and well controlled by the intermediate input size. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Lattice Hermite Normal Form lll algorithm

来源：评论

学校读者我要写书评

暂无评论

Deep lll on Module Lattices 27th

Deep LLL on Module Lattices

引用

27th International Conference on Information Security

作者： Zhou, Yang Cao, Heyang Wang, Mingsheng Univ Chinese Acad Sci Sch Cyber Secur Beijing Peoples R China Chinese Acad Sci Key Lab Cyberspace Secur Def Inst Informat Engn Beijing Peoples R China

ISBN: (纸本)9783031757631;9783031757648

The lll algorithm, renowned for its application to Euclidean lattices, plays a crucial role in lattice cryptanalysis by offering a standard method for refining lattice bases. With the increasing importance of module lattices-defined as modules over the ring of integers of a number field-in lattice cryptography, there is a compelling need to adapt the lll algorithm for module lattices. This paper presents a generalization of the Deep lll algorithm-a variant of lll proposed by Schnorr and Euchner [25], which relaxes the restriction on the insertion position-to module lattices. Deep lll has been widely used in BKZ reduction as a sub-procedure. Our algorithm is suitable as a sub-procedure in adapted BKZ reduction for module lattices. We implemented a proof-of-concept version of our algorithm, and compared to the lll algorithm on module lattices, our algorithm outperformed it in all of our experimental cases. Additionally, we introduced a simplification that avoids invoking the computation of the Module Hermite Form and corrected mistakes in the previous work.

关键词： lll algorithm Module lattices Lattice Reduction

来源：评论

学校读者我要写书评

暂无评论

An optimal bound for factoring unbalanced RSA moduli by solving Generalized Implicit Factorization Problem

引用

JOURNAL OF SUPERCOMPUTING 2025年第1期81卷 1-24页

作者： Zhang, Ran Bi, Jingguo Li, Lixiang Peng, Haipeng Beijing Univ Posts & Telecommun Sch Cyberspace Secur Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Informat Secur Ctr State Key Lab Networking & Switching Technol Beijing 100876 Peoples R China State Key Lab Cryptol POB 5159 Beijing 100878 Peoples R China

The integer factorization problem, concerning the product of two primes N = pq, has been a focal point for researchers since its rise to prominence with the RSA algorithm, a renowned public key scheme. It is well known that the integer factorization problem can be solved by the Number Field Sieve (NFS) algorithm in sub-exponential time, this challenge may also find resolution in polynomial time under certain conditions for the primes. In this paper, we revisit the problem of factoring RSA moduli with the implicit hint, where the implicit hint is the shared bits of primes. As for k RSA moduli, we present a novel implicit factorization approach applicable when the unknown multiples ap of the prime factors p share a certain number of most significant bits (MSBs) or least significant bits (LSBs). By drawing inspiration from addressing the Approximate Common Divisor Problem (ACDP), we transform this problem into solving the small roots of k-1 trivariate polynomials. To compute these small roots, we employ Coppersmith's method to construct a lattice basis for the modular polynomials. We modify the lattice basis by introducing new variables, achieving an optimal bound in the MSB and LSB cases. Our attack breaks the RSA system and improves upon all previous attacks on such variants when the amount of the shared bits is sufficiently large. Concluding our paper, we meticulously validate the theoretical analysis results, with experimental data confirming the full practical feasibility of our attack on such an RSA variant system.

关键词： RSA system Generalized Implicit Factorization Problem Coppersmith's method 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

来源：评论

学校读者我要写书评

暂无评论

On the largest value of the solutions of Erdős' last equation

引用

INTERNATIONAL JOURNAL OF NUMBER THEORY 2025年第0期

作者： Luca, Florian Pink, Istvan Sandor, Csaba Stellenbosch Univ Math Div Stellenbosch South Africa Univ Debrecen Inst Math POB 400 H-4002 Debrecen Hungary Univ Salzburg Hellbrunnerstr 34 A-I5020 Salzburg Austria Budapest Univ Technol & Econ Inst Math Dept Stochast Muegyetem Rkp 3 H-1111 Budapest Hungary HUN REN Alfred Renyi Inst Math Realtanoda Utca 13-15 H-1053 Budapest Hungary MTA HUN REN RI Lendulet Momentum Arithmet Combinat Realtanoda Utca 13-15 H-1053 Budapest Hungary

Let n be a positive integer. The Diophantine equation n(x(1) + x(2) + & ctdot;+ x(n)) = x(1)x(2 )& mldr;x(n), 1 infinity as n ->infinity and determine all tuples (n, x(1), & mldr;, x(n)) with x(n) <=... 详细信息

Let n be a positive integer. The Diophantine equation n(x(1) + x(2) + & ctdot;+ x(n)) = x(1)x(2 )& mldr;x(n), 1 <= x(1) <= x(2) <= & ctdot;<= x(n) is called Erd & odblac;s' last equation. We prove that x(n) ->infinity as n ->infinity and determine all tuples (n, x(1), & mldr;, x(n)) with x(n) <= 10.

关键词： Erd & odblac s's last equation Baker's method lll algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Diophantine equation Fn^x + Fk^x = Fm^y

引用

RAMANUJAN JOURNAL 2025年第2期67卷 1-37页

作者： Berczes, Attila Hajdu, Lajos Luca, Florian Pink, Istvan Univ Debrecen Inst Math POB 400 H-4002 Debrecen Hungary HUN REN Equat Funct Curves & their Applicat Res Gr Debrecen Hungary Stellenbosch Univ Math Div Stellenbosch South Africa Univ Salzburg Hellbrunner str 34-I A-5020 Salzburg Austria

In this paper, we find all solutions of the Diophantine equation F-n(x) + F-k(x) = F-m(y), where {F-m}(m >= 0 )is the Fibonacci sequence.

关键词： Fibonacci numbers Exponential Diophantine equations Baker's method lll algorithm

来源：评论

学校读者我要写书评

暂无评论

Security Analysis of Hybrid Attack for NTRU-Class Encryption Schemes

引用

IEEE ACCESS 2023年 11卷 109939-109952页

作者： Levina, Alla Kadykov, Victor Valluri, Maheswara Rao St Petersburg Electrotech Univ LETI Lab Fundamentals Intelligent Syst LETI St Petersburg 197376 Russia Quinfosystems Pvt Ltd Telangana 500072 India

One of the significant post-quantum cryptographic candidates is the NTRU public key cryptosystem. It operates on polynomial rings, where the parameter largely determines the security of the system. Although NTRU is being studied currently, it has a long and well-established history. There are several lattice-based attacks on NTRU-like systems that exploit the special structures of the rings used in these systems. The aim of this paper is to analyze the original NTRU, NTRU Encrypt, and NTRU Primes encryption schemes by structuring their common elements and showing the strongest hybrid attack using both lattice reduction and meet-in-the-middle (MITM) search on them. Furthermore, it is noted that, ignoring a polynomial factor of the not-well-studied cost of Block Korkin-Zolotarev (BKZ) algorithm, we estimate the security of the construction of encryption keys and show that by balancing lattice reduction costs and a MITM search cost, one can achieve better performance than using any of these methods on their own. Unlike previous studies, we found the way to ignore polynomial impact 2(2)-2(4) from BKZ loops with multiple shortest vector problem (SVP) and the factor of 2(7) was omitted from the cost of one step in guessing the SVP.

关键词： BKZ algorithm cryptography ideals lattices lll algorithm NTRU public key polynomial ring security proof

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：