The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors

2019/01/19 by Mårtensson, Erik · 1 citation
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1901.06558

Abstract

The Learning with Errors problem (LWE) is one of the main candidates for post-quantum cryptography. At Asiacrypt 2017, coded-BKW with sieving, an algorithm combining the Blum-Kalai-Wasserman algorithm (BKW) with lattice sieving techniques, was proposed. In this paper, we improve that algorithm by using different reduction factors in different steps of the sieving part of the algorithm. In the Regev setting, where q = n² and σ= n^1.5/(√(2π)log₂² n), the asymptotic complexity is 2^0.8917n, improving the previously best complexity of 2^0.8927n. When a quantum computer is assumed or the number of samples is limited, we get a similar level of improvement.

Cited by

• A Non-leveled and Reliable Approximate FHE Framework through Binarized Polynomial Rings

Related

• On the Sample Complexity of solving LWE using BKW-Style Algorithms
• An Improved BKW Algorithm for LWE with Applications to Cryptography and\n Lattices
• On lattices, learning with errors, random linear codes, and cryptography
• The Quantum Decoding Problem
• Learning With Errors and Extrapolated Dihedral Cosets