A detailed analysis of primal attack and its variants  

作　　者：Xue ZHANG Zhongxiang ZHENG Xiaoyun WANG 

机构地区：[1]Institute for Advanced Study,Tsinghua University,Beijing 100084,China [2]Key Laboratory of Cryptologic Technology and Information Security,Ministry of Education,Shandong University,Jinan 250100,China

出　　处：《Science China(Information Sciences)》2022年第3期178-191,共14页中国科学（信息科学）（英文版）

基　　金：supported by National Key Research and Development Program of China (Grant Nos.2017YFA0303903, 2018YFA0704701);Major Program of Guangdong Basic and Applied Research (Grant No. 2019B030302008);Major Scientific and Technological Innovation Project of Shandong Province (Grant No. 2019JZZY010133)。

摘　　要：Primal attack is a typically considered strategy to estimate the hardness of cryptosystem based on learning with errors problem(LWE),it reduces the LWE problem to the unique-SVP by embedding technique and then employs lattice reduction such as BKZ to find the shortest vector.The main reason for the popularity of primal attack is its conservative estimation,in general,the complexity of primal attack is estimated by the hardness of core-SVP as T=20.292 b.In this work,we first revisit primal attack and give supplemental proof of the scaling factor in Bai-Galbraith embedding,whose value was given according to the experimental results.Then we refine primal attack in two special cases and analyze the variants in detail.One is that,for sparse secret LWE(or sparse secret-error LWE),primal attack with dropping makes a trade-off between guessing zero components and solving dimension-reduced problems to improve the complexity.The other is that,when TBKZ(b)=poly(d)⋅TSieve(b)holds in practice,primal attack with preprocessing reduces the time complexity by a factor of 26–210 through dividing primal attack into three steps and considering them independently.

关 键 词：CRYPTANALYSIS lattice-based cryptography learning with errors problem primal attack unique-SVP 

分 类 号：TN918.1[电子电信—通信与信息系统]