搜索结果: 1-15 共查到“密码学 Sieving”相关记录22条 . 查询时间(0.093 秒)
Quantum Algorithms for the Approximate k-List Problem and their Application to Lattice Sieving
approximate k-list problem cryptanalysis distributed computation
2019/9/16
The Shortest Vector Problem (SVP) is one of the mathematical foundations of lattice based cryptography. Lattice sieve algorithms are amongst the foremost methods of solving SVP. The asymptotically fas...
Faster Sieving Algorithm for Approximate SVP with Constant Approximation Factors
foundations lattice techniques
2019/9/16
Abstract. There is a large gap between theory and practice in the complexities of sieving algorithms for solving the shortest vector problem in an arbitrary Euclidean lattice. In this paper, we work t...
On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving
public-key cryptography LWE
2019/1/9
The Learning with Errors problem (LWE) has become a central topic in recent cryptographic research. In this paper, we present a new solving algorithm combining important ideas from previous work on im...
Higher dimensional sieving for the number field sieve algorithms
public-key cryptography exTNFS
2018/11/6
Since 2016 and the introduction of the exTNFS (extended Tower Number Field Sieve) algorithm, the security of cryptosystems based on non- prime finite fields, mainly the paring and torus-based one, is ...
Progressive lattice sieving
lattice-based cryptography lattice sieving shortest vector problem (SVP)
2018/1/24
In this work we consider a progressive approach to lattice sieving, where we gradually introduce new basis vectors only when the sieve has stabilized on the previous basis vectors. This leads to impro...
Speed-ups and time-memory trade-offs for tuple lattice sieving
lattice-based cryptography shortest vector problem (SVP) nearest neighbor algorithms
2017/12/25
Our results extend and improve upon previous work of Bai-Laarhoven-Stehlé [ANTS'16] and Herold-Kirshanova [PKC'17], with better complexities for arbitrary tuple sizes and offering tunable time-memory ...
Shortest Vector from Lattice Sieving: a Few Dimensions for Free
Cryptanalysis Lattice Sieving
2017/10/12
Asymptotically, the best known algorithms for solving the Shortest Vector Problem (SVP) in a lattice of dimension nn are sieve algorithms, which have heuristic complexity estimates ranging from (4/3)n...
Randomized lattice sieving for the closest vector problem (with preprocessing)
lattices sieving algorithms nearest neighbor searching
2016/12/9
In practice, the large memory footprint makes it problematic to run sieving directly on high-dimensional lattices, and perhaps the most promising application of such algorithms is as part of a hybrid ...
Lattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving SVP require space which (heuristica...
Sieving for shortest vectors in lattices using angular locality-sensitive hashing
lattices shortest vector problem (SVP) sieving algorithms
2016/1/7
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 ...
Sieving for Shortest Vectors in Ideal Lattices: a Practical Perspective
Lattice cryptanalysis parallel Gauss sieve ideal lattices
2016/1/6
The security of many lattice-based cryptographic schemes relies on the hardness of
finding short vectors in integral lattices. We propose a new variant of the parallel Gauss sieve
algorithm to compu...
Parallel (probable) lock-free HashSieve: a practical sieving algorithm for the SVP
spin-locks compare-and-swap
2016/1/4
In this paper, we assess the practicability of HashSieve, a recently proposed sieving algorithm for the Shortest Vector Problem (SVP) on lattices, on multi-core shared memory systems. To this end, we ...
Use of SIMD-Based Data Parallelism to Speed up Sieving in Integer-Factoring Algorithms
Integer Factorization Sieving Multiple-Polynomial Quadratic Sieve Method
2016/1/4
Many cryptographic protocols derive their security from the apparent
computational intractability of the integer factorization problem. Currently,
the best known integer-factoring algorithms run in ...
Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
shortest vector problem (SVP), sieving algorithms, nearest neighbor problem
2016/1/3
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 probl...
Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search
Nearest neighbor search lattice sieve
2015/12/30
We give a simple heuristic sieving algorithm for the m-dimensional
exact shortest vector problem (SVP) which runs in time 20.3112m+o(m)
. Unlike
previous time-memory trade-offs, we do not increase ...
