筛子(范畴论)
算法
格子(音乐)
格点问题
晶格还原
基于格的密码学
数学
还原(数学)
计算机科学
组合数学
密码学
物理
几何学
电信
量子密码学
频道(广播)
多输入多输出
量子力学
声学
量子信息
量子
作者
Jinzheng Cao,Qingfeng Cheng,Xinghua Li,Yanbin Pan
标识
DOI:10.1007/978-3-031-15777-6_1
摘要
The Shortest Vector Problem is a crucial part of the lattice theory and a central lattice problem in analyzing lattice-based cryptography. This work provides a new algorithm that finds a short vector by calling the sieve oracle in projected sublattices orthogonal to each other. We first propose the Block Sieve algorithm. With blockwise sieving, proper insertion and reduction, the coordinates of the right end of vector v can be recovered. The algorithm moves the block to recover the other coordinates. We continue to optimize the algorithm and propose the Progressive Block Sieve algorithm, employing techniques such as skipping to accelerate the procedure. In a d-dimensional lattice, smaller sieve calls in ( $$d-\varTheta ({d}/\ln {d})$$ )-dimensional sublattices are enough to find a short vector. We compare the experimental results on different lattices to test the performance of the new approach. On challenge lattices, our algorithm takes less time and fewer tours than original reduction algorithms to reach a similar outcome. As an application of the new algorithm, we test the performance of solving Learning With Errors problem. Our algorithm is able to solve the instances about 5% faster than sieving.
科研通智能强力驱动
Strongly Powered by AbleSci AI