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

28th Signal Processing and Communications Applications Conference (SIU)

作者： Satilmis, Hami Akleylek, Sedat Ondokuz Mayis Univ Bilgisayar Muhendisligi Bolumu Samsun Turkey

ISBN: (纸本)9781728172064

The security of lattice-based cryptosystems in post-quantum cryptography is mainly based on the difficulty of solving the shortest vector problem (SVP) or the closest vector problem (CVP). In this paper, efficient implementations of GaussSieve and ProGaussSieve algorithms alternatives to solve the shortest vector problem are studied. A cryptographic software library is developed which is an infrastructure for the implementation of sieving algorithms in order to have faster running times than the ones in the literature. In addition, a comparison table including the running times of the implementations of GaussSieve and ProGaussSieve algorithms is presented. According to the experimental results, the proposed GaussSieve and ProGaussSieve implementations are much more faster and efficient than the others.

关键词： lattice-based cryptography sieving algorithms GaussSieve ProGaussSieve SVP

来源：评论

学校读者我要写书评

暂无评论

Parameter Estimation for Lattice-Based Cryptosystems By Using sieving algorithms 4

Parameter Estimation for Lattice-Based Cryptosystems By Usin...

引用

4th International Conference on Computer Science and Engineering (UBMK)

作者： Akleylek, Sedat Satilmis, Hami Ondokuz Mayis Univ Bilgisayar Muhendisligi Bolumu Samsun Turkey

ISBN: (纸本)9781728139647

The security of quantum resistant lattice-based cryptosystems mainly depend on the shortest vector problem (SVP) or the closest vector problem (CVP). In this paper, sieving algorithms such as ListSieve, GaussSieve, ProGaussSieve and HashSieve are discussed and compared in terms of their complexity and capabilities. The algorithm of Becker et al., used in LIVE-Estimator software, is analyzed by considering HashSieve to generate reliable parameter sets. According to the experimental results, up to 81-bit security level, using HashSieve is comparable with other algorithms. It's shown that for low security levels small key sizes can be obtained.

关键词： sieving algorithms lattice-based cryptography SVP parameter selection

来源：评论

学校读者我要写书评

暂无评论

sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing 35th

Sieving for Shortest Vectors in Lattices Using Angular Local...

引用

35th Annual International Cryptology Conference (CRYPTO)

作者： Laarhoven, Thijs Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands

ISBN: (纸本)9783662479896;9783662479889

By replacing the brute-force list search in sieving algorithms with Charikar's angular locality-sensitive hashing (LSH) method, we get both theoretical and practical speedups for solving the shortest vector problem (SVP) on lattices. Combining angular LSH with a variant of Nguyen and Vidick's heuristic sieve algorithm, we obtain heuristic time and space complexities for solving SVP of 2(0.3366n+o(n)) and 2(0.2075n+o(n)) respectively, while combining the same hash family with Micciancio and Voulgaris' GaussSieve algorithm leads to an algorithm with (conjectured) heuristic time and space complexities of 2(0.3366n+o(n)). Experiments with the GaussSieve-variant show that in moderate dimensions the proposed HashSieve algorithm already outperforms the GaussSieve, and the practical increase in the space complexity is much smaller than the asymptotic bounds suggest, and can be further reduced with probing. Extrapolating to higher dimensions, we estimate that a fully optimized and parallelized implementation of the GaussSieve-based HashSieve algorithm might need a few core years to solve SVP in dimension 130 or even 140.

关键词： Lattices Shortest vector problem (SVP) sieving algorithms Approximate nearest neighbor problem Locality-sensitive hashing (LSH)

来源：评论

学校读者我要写书评

暂无评论

Faster sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing 4th

Faster Sieving for Shortest Lattice Vectors Using Spherical ...

引用

4th International Conference on Cryptology and Information Security in Latin America

作者： Laarhoven, Thijs de Weger, Benne Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands

ISBN: (纸本)9783319221748;9783319221731

Recently, it was shown that angular locality-sensitive hashing (LSH) can be used to significantly speed up lattice sieving, leading to a heuristic time complexity for solving the shortest vector problem (SVP) of 2(0.337n+o(n)) (and space complexity 2(0.208n+o(n)). We study the possibility of applying other LSH methods to sieving, and show that with the spherical LSH method of Andoni et al. we can heuristically solve SVP in time 2(0.298n+o(n)) and space 2(0.208n+o(n)). We further show that a practical variant of the resulting SphereSieve is very similar to Wang et al.'s two-level sieve, with the key difference that we impose an order on the outer list of centers.

关键词： Shortest vector problem (svp) sieving algorithms Nearest neighbor problem Locality-sensitive hashing (lsh) Lattice cryptography

来源：评论

学校读者我要写书评

暂无评论

The irreducible vectors of a lattice: Some theory and applications

引用

DESIGNS CODES AND CRYPTOGRAPHY 2023年第2期91卷 609-643页

作者： Doulgerakis, Emmanouil Laarhoven, Thijs de Weger, Benne Eindhoven Univ Technol Eindhoven Netherlands TNO Cyber Secur & Robustness The Hague Netherlands

The main idea behind lattice sieving algorithms is to reduce a sufficiently large number of lattice vectors with each other so that a set of short enough vectors is obtained. It is therefore natural to study vectors which cannot be reduced. In this work we give a concrete definition of an irreducible vector and study the properties of the set of all such vectors. We show that the set of irreducible vectors is a subset of the set of Voronoi relevant vectors and study its properties. For extremal lattices this set may contain as many as r vectors, which leads us to define the notion of a complete system of irreducible vectors, whose size can be upper-bounded by the kissing number. One of our main results shows that modified heuristic sieving algorithms heuristically approximate such a set (modulo sign). We provide experiments in low dimensions which support this theory. Finally we give some applications of this set in the study of lattice problems such as SVP, SIVP and CVPP. The introduced notions, as well as various results derived along the way, may provide further insights into lattice algorithms and motivate new research into understanding these algorithms better.

关键词： Lattices Relevant vectors Irreducible vectors sieving algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster exponential time algorithms for the shortest vector problem

Faster exponential time algorithms for the shortest vector p...

引用

21st Annual ACM/SIAM Symposium on Discrete algorithms

作者： Micciancio, Daniele Voulgaris, Panagiotis Univ Calif San Diego La Jolla CA 92093 USA

ISBN: (纸本)9780898717013

We present new faster algorithms for the exact solution of the shortest;vector problem in arbitrary lattices Our main result shows that the shortest vector in any n-dimensional lattice can be found in time 2(3) (199n) (and space 2(1) (325n)), or in Space 2(1) (095n) (and still tune 2(O(n))). Tins improves the best previously known algorithm by Ajtai, Kumar and Sivakumar [Proceedings of STOC 2001] which was shown by Nguyen and Vidick [J Math Crypto. 2(2) 181-207] to inn in time 2(5) (9n) and space 2(2) (95n) We also present a practical variant of our algorithm which provably uses an amount of space proportional to tau(n), the "kissing" constant in dimension n. No upper bound on the running tune of our second algorithm is currently known, but experimentally the algorithm seems 1,0 perforin fairly well in practice with running Lime 2(0) (52n) and space complexity 2(0) (2n)

关键词： Algorithm Analysis Cryptography Shortest Vector Problem sieving algorithms Software implementations

来源：评论

学校读者我要写书评

暂无评论

Finding Closest Lattice Vectors Using Approximate Voronoi Cells 10th

Finding Closest Lattice Vectors Using Approximate Voronoi Ce...

引用

10th International Workshop on Post-Quantum Cryptography (PQCrypto)

作者： Doulgerakis, Emmanouil Laarhoven, Thijs de Weger, Benne Eindhoven Univ Technol Eindhoven Netherlands

ISBN: (纸本)9783030255107;9783030255091

The two traditional hard problems underlying the security of lattice-based cryptography are the shortest vector problem (SVP) and the closest vector problem (CVP). For a long time, lattice enumeration was considered the fastest method for solving these problems in high dimensions, but recent work on memory-intensive methods has resulted in lattice sieving overtaking enumeration both in theory and in practice. Some of the recent improvements [Ducas, Eurocrypt 2018;Laarhoven-Mariano, PQCrypto 2018;Albrecht-Ducas-Herold-Kirshanova-Postlethwaite-Stevens, 2018] are based on the fact that these methods find more than just one short lattice vector, and this additional data can be reused effectively later on to solve other, closely related problems faster. Similarly, results for the preprocessing version of CVP (CVPP) have demonstrated that once this initial data has been generated, instances of CVP can be solved faster than when solving them directly, albeit with worse memory complexities [Laarhoven, SAC 2016]. In this work we study CVPP in terms of approximate Voronoi cells, and obtain better time and space complexities using randomized slicing, which is similar in spirit to using randomized bases in lattice enumeration [Gama-Nguyen-Regev, Eurocrypt 2010]. With this approach, we improve upon the state-of-the-art complexities for CVPP, both theoretically and experimentally, with a practical speedup of several orders of magnitude compared to non-preprocessed SVP or CVP. Such a fast CVPP solver may give rise to faster enumeration methods, where the CVPP solver is used to replace the bottom part of the enumeration tree, consisting of a batch of CVP instances in the same lattice. Asymptotically, we further show that we can solve an exponential number of instances of CVP in a lattice in essentially the same amount of time and space as the fastest method for solving just one CVP instance. This is in line with various recent results, showing that perhaps the biggest strength of m

关键词： Lattices Preprocessing Voronoi cells sieving algorithms Shortest vector problem (SVP) Closest vector problem (CVP)

来源：评论

学校读者我要写书评

暂无评论

Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices

Analysis of Gauss-Sieve for Solving the Shortest Vector Prob...

引用

5th International Workshop on algorithms and Computation

作者： Schneider, Michael Tech Univ Darmstadt Darmstadt Germany

ISBN: (纸本)9783642190933

Lattice based cryptography is gaining more and more importance in the cryptographic community. The security of lattice based cryptosystems can be proven to be as hard as worst case lattice problems. The most important underlying hard problem is the shortest vector problem. There are two concurrent approaches for the search for shortest ye:tors in lattices: enumeration and probabilistic sieving algorithms. Enumeration algorithms were the best choice, until in 2010, Micciancio and Voulgaris present a new heuristic sieving algorithm called Gauss Sieve, which was the first sieving algorithm considered to be competitive to exhaustive search algorithms. Later in 2010, Gama, Nguyen, and Regev published their extreme pruning variant of the enumeration, which again ruled out sieving. In this paper, we present the practical results using Gauss Sieve that we gained in our experiments throughout the last year. We analyze the behaviour of Gauss Sieve that helps understanding the strengths and weaknesses of the algorithm.

关键词： lattice reduction shortest vector problem sieving algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Implementation of HashSieve Algorithm for Lattice-Based Cryptography 13

Efficient Implementation of HashSieve Algorithm for Lattice-...

引用

International Conference on Information Security and Cryptology (ISCTURKEY)

作者： Satilmis, Hami Akleylek, Sedat Ondokuz Mayis Univ Dept Comp Engn Samsun Turkey

ISBN: (纸本)9780738125060

The security of lattice-based cryptosystems that are secure for the post-quantum period is based on the difficulty of the shortest vector problem (SVP) and the closest vector problem (CVP). In the literature, many sieving algorithms are proposed to solve these hard problems. In this paper, efficient implementation of HashSieve sieving algorithm is discussed. A modular software library to have an efficient implementation of HashSieve algorithm is developed. Modular software library is used as an infrastructure in order for the HashSieve efficient implementation to be better than the sample in the literature (Laarhoven's standard HashSieve implementation). According to the experimental results, it is observed that HashSieve efficient implementation has a better running time than the example in the literature. It is concluded that both implementations are close to each other in terms of the memory space used.

关键词： lattice-based cryptography sieving algorithms HashSieve SVP modular software

来源：评论

学校读者我要写书评

暂无评论

Letters to the editor: On practicality of sieving techniques vs. the sieving algorithm

引用

Communications of the ACM 1968年第3期11卷 149-149页

作者： Howland, John E. Univ. of Oklahoma Norman United States

No abstract available.

关键词： indexing techniques prime numbers sieving algorithms sieving techniques

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：