搜索结果: 1-9 共查到“军事学 lattice sieving”相关记录9条 . 查询时间(0.124 秒)
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...
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...
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 ...
Efficient (ideal) lattice sieving using cross-polytope LSH
shortest vector problem sieving algorithms locality-sensitive hashing
2015/12/23
Combining the efficient cross-polytope locality-sensitive hash family of Terasawa and Tanaka with the heuristic lattice sieve algorithm of Micciancio and Voulgaris, we show how to obtain heuristic and...
New directions in nearest neighbor searching with applications to lattice sieving
Lattices Cryptanalysis
2015/12/21
To solve the approximate nearest neighbor search problem
(NNS) on the sphere, we propose a method using
locality-sensitive filters (LSF), with the property that
nearby vectors have a higher probabi...