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

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

来源：评论

学校读者我要写书评

暂无评论

Solving Generalized Small Inverse Problems

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2011年第6期E94A卷 1274-1284页

作者： Kunihiro, Noboru Univ Tokyo Kashiwa Chiba 2778561 Japan

We introduce a "generalized small inverse problem (GSIP)" and present an algorithm for solving this problem. GSIP is formulated as finding small solutions of f(x(0), x(1),...x(n)) = x(0)h(x(1),...,x(n))+C = 0(mod M) for an n-variate polynomial h, non-zero integers C and M. Our algorithm is based on lattice-based Coppersmith technique. We provide a strategy for construction of a lattice basis for solving f = 0, which is systematically transformed from a lattice basis for solving h = 0. Then, we derive an upper bound such that the target problem can be solved in polynomial time in log M in an explicit form. Since GSIPs include some RSA-related problems, our algorithm is applicable to them. For example, the small key attacks by Boneh and Durfee are re-found automatically.

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

来源：评论

学校读者我要写书评

暂无评论

cryptanalysis of Server-Aided RSA Protocols with Private-Key Splitting

引用

COMPUTER JOURNAL 2019年第8期62卷 1194-1213页

作者： Mefenza, Thierry Vergnaud, Damien Univ Pantheon Assas Paris France Sorbonne Univ CNRS LIP6 Paris France Inst Univ France Paris France

We analyze the security and the efficiency of interactive protocols where a client wants to delegate the computation of an RSA signature given a public key, a public message and the secret signing exponent. We consider several protocols where the secret exponent is split using some algebraic decomposition. We first provide an exhaustive analysis of the delegation protocols in which the client outsources a single RSA exponentiation to the server. We then revisit the security of the protocols RSA-S1 and RSA-S2 that were proposed by Matsumoto, Kato and Imai in 1988. We present an improved lattice-based attack on RSA-S1 and we propose a simple variant of this protocol that provides better efficiency for the same security level. Eventually, we present the first attacks on the protocol RSA-S2 that employs the Chinese Remainder Theorem to speed up the client's computation. The efficiency of our (heuristic) attacks has been validated experimentally.

关键词： RSA exponentiation outsourcing lattice-based cryptanalysis Coppersmith's methods RSA-S1 RSA-S2

来源：评论

学校读者我要写书评

暂无评论

A Refined Hardness Estimation of LWE in Two-Step Mode 27th

A Refined Hardness Estimation of LWE in Two-Step Mode

引用

27th IACR International Conference on Practice and Theory of Public Key Cryptography (PKC)

作者： Xia, Wenwen Wang, Leizhang Wang, Geng Gu, Dawu Wang, Baocang Xidian Univ Sch Cyber Engn Xian 710071 Peoples R China Shanghai Jiao Tong Univ Lab Cryptol & Comp Secur Shanghai 200240 Peoples R China Xidian Univ State Key Lab Integrated Serv Networks Xian 710071 Peoples R China Shanghai Jiao Tong Univ Sch Elect Informat & Elect Engn Shanghai 200240 Peoples R China State Key Lab Cryptol POB 5159 Beijing 100878 Peoples R China

ISBN: (纸本)9783031577246;9783031577253

Recently, researchers have proposed many LWE estimators, such as lattice-estimator (Albrecht et al, Asiacrypt 2017) and leaky-LWE-Estimator (Dachman-Soled et al, Crypto 2020), while the latter has already been used in estimating the security level of Kyber and Dilithium using only BKZ. However, we prove in this paper that solving LWE by combining a lattice reduction step (by LLL or BKZ) and a target vector searching step (by enumeration or sieving), which we call a Two-step mode, is more efficient than using only BKZ. Moreover, we give a refined LWE estimator in Two-step mode by analyzing the relationship between the probability distribution of the target vector and the solving success rate in a Two-step mode LWE solving algorithm. While the latest Two-step estimator for LWE, which is the "primal-bdd" mode in lattice-estimator (https://***/malb/lattice-estimator), does not take into account some up-to-date results and lacks a thorough theoretical analysis. Under the same gate-count model, our estimation for NIST PQC standards drops by 2.1-3.4 bits (2.2-4.6 bits while considering more flexible blocksize and jump strategy) compared with leaky-LWE-Estimator. Furthermore, we also give a conservative estimation for LWE from the Two-step solving algorithm. Compared with the Core-SVP model, which is used in previous conservative estimations, our estimation relies on weaker assumptions and outputs higher evaluation results than the Core-SVP model. For NIST PQC standards, our conservative estimation is 4.17-8.11 bits higher than the Core-SVP estimation. Hence our estimator can give a closer estimation for both upper bound and lower bound of LWE hardness.

关键词： lattice-based cryptanalysis Security Strength LWE estimator Two-step mode

来源：评论

学校读者我要写书评

暂无评论

Solving Generalized Small Inverse Problems

Solving Generalized Small Inverse Problems

引用

15th Australasian conference, ACISP 2010

作者： Kunihiro, Noboru Univ Tokyo Tokyo 1138654 Japan

ISBN: (纸本)9783642140808

We introduce a "generalized small inverse problem (GSIP)" and present an algorithm for solving this problem. GSIP is formulated as finding small solutions of f(x(0), x(1), . . , x(n)) = x(0)h(x(1), . . . , x(n)) + C = 0(mod M) for an n-variate polynomial h, non-zero integers C and M. Our algorithm is based on lattice-based Coppersmith technique. We provide a strategy for construction of a lattice basis for solving f = 0, which are systematically transformed from a lattice basis for solving h = 0. Then, we derive an upper bound such that the target problem can be solved in polynomial time in log M in an explicit form. Since GSIPs include some RSA-related problems, our algorithm is applicable to them. For example, the small key attacks by Boneh and Durfee are re-found automatically.

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

来源：评论

学校读者我要写书评

暂无评论

Analyzing Blockwise lattice Algorithms Using Dynamical Systems

引用

31st Annual International Cryptology Conference (CRYPTO)

作者： Hanrot, Guillaume Pujol, Xavier Stehle, Damien Univ Lyon CNRS ENS Lyon Lab LIPINRIAUCBL 46 Allee Italie F-69364 Lyon 07 France

ISBN: (纸本)9783642227929;9783642227912

Strong lattice reduction is the key element for most attacks against lattice-based cryptosystems. Between the strongest but impractical HKZ reduction and the weak but fast LLL reduction, there have been several attempts to find efficient trade-offs. Among them, the BKZ algorithm introduced by Schnorr and Euchner [FCT'91] seems to achieve the best time/quality compromise in practice. However, no reasonable complexity upper bound is known for BKZ, and Gama and Nguyen [Eurocrypt'08] observed experimentally that its practical runtime seems to grow exponentially with the lattice dimension. In this work, we show that BKZ can be terminated long before its completion, while still providing bases of excellent quality. More precisely, we show that if given as inputs a basis (b(i))(i <= n) is an element of Q(nxn) of a lattice L and a block-size beta, and if terminated after Omega(n(3)/beta(2) (log n + log log max(i) parallel to bi parallel to)) calls to a beta-dimensional HKZ-reduction (or SVP) subroutine, then BKZ returns a basis whose first vector has norm <= 2v(beta)(n-1/2(beta-1)n-1) (+) (3/2) . (det L)(1/n), where v(beta) <= beta is the maximum of Hermite's constants in dimensions <= beta. To obtain this result, we develop a completely new elementary technique based on discrete-time affine dynamical systems, which could lead to the design of improved lattice reduction algorithms.

关键词： Euclidean lattices BKZ lattice-based cryptanalysis

来源：评论

学校读者我要写书评

暂无评论

Heterogeneous Implementation of a Voronoi Cell-based SVP Solver

引用

IEEE ACCESS 2019年 7卷 127012-127023页

作者： Falcao, Gabriel Cabeleira, Filipe Mariano, Artur Santos, Luis Paulo Univ Coimbra Inst Telecomunicacoes Dept Elect & Comp Engn P-3030290 Coimbra Portugal INESC TEC P-4200465 Porto Portugal Univ Minho Dept Informat P-4710057 Braga Portugal

This paper presents a new, heterogeneous CPU+GPU attacks against lattice-based (post-quantum) cryptosystems based on the Shortest Vector Problem (SVP), a central problem in lattice-based cryptanalysis. To the best of our knowledge, this is the first SVP-attack against lattice-based cryptosystems using CPUs and GPUs simultaneously. We show that Voronoi-cell based CPU+GPU attacks, algorithmically improved in previous work, are suitable for the proposed massively parallel platforms. Results show that 1) heterogeneous platforms are useful in this scenario, as they increment the overall memory available in the system (as GPU's memory can be used effectively), a typical bottleneck for Voronoi-cell algorithms, and we have also been able to increase the performance of the algorithm on such a platform, by successfully using the GPU as a co-processor, 2) this attack can be successfully accelerated using conventional GPUs and 3) we can take advantage of multiple GPUs to attack lattice-based cryptosystems. Experimental results show a speedup up to 7.6x for 2 GPUs hosted by an Intel Xeon E5-2695 v2 CPU (12 cores x2 sockets) using only 1 core and gains in the order of 20% for 2 GPUs hosted by the same machine using all 22 CPU threads (2 are reserved for orchestrating the GPUs), compared to single-CPU execution using the entire 24 threads available.

关键词： lattices lattice-based cryptanalysis Voronoi-cell algorithms high performance computing parallelism multi-threading multicores graphics processing units multi-GPU parallel computing CUDA OpenMP StarPU

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：