Cryptology ePrint Archive: Report 2021/152

Hybrid Dual Attack on LWE with Arbitrary Secrets

Lei Bi and Xianhui Lu and Junjie Luo and Kunpeng Wang and Zhenfei Zhang

Abstract: In this paper, we study the {\em hybrid dual attack} over Learning with Errors (LWE) problems for {\em any} secret distribution. Prior to our work, hybrid attacks are only considered for sparse and/or small secrets. A new and interesting result from our analysis shows that for most cryptographic use cases a hybrid dual attack outperforms a standalone dual attack, regardless of the secret distribution. We formulate our results into a framework of predicting the performance of the hybrid dual attacks. We also present a few tricks that further improve our attack. To illustrate the effectiveness of our result, we re-evaluate the security of {\em all} LWE related proposals in round 3 of NIST's post-quantum cryptography process, and improve the state-of-the-art cryptanalysis results by 2-14 bits, under the BKZ-core-SVP model.

Category / Keywords: public-key cryptography / Learning with Errors, Lattice-based Cryptography, Cryptanalysis, Dual Attack, Hybrid attack, NIST PQC

Date: received 11 Feb 2021, last revised 24 Feb 2021

Contact author: bilei121 at outlook com

Available format(s): PDF | BibTeX Citation

Version: 20210225:032029 (All versions of this report)

Short URL: ia.cr/2021/152


[ Cryptology ePrint archive ]