Lazy modulus switching for the BKW algorithm on LWE

DOI10.1007/978-3-642-54631-0_25MaRDI QIDQ5402986zbMATH OpenOpenAlexFDO

Authors Martin R. Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, Ludovic Perret

Publication date 25 March 2014

Published in Public-Key Cryptography – PKC 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-54631-0_25

zbMATH Keywords

learning with errors (LWE)Blum-Kalai-Wasserman (BKW) algorithmshort integer solution (SIS) problem

Mathematics Subject Classification ID

Cryptography (94A60)

Recommendations

• An improved BKW algorithm for LWE with applications to cryptography and lattices
• On the complexity of the BKW algorithm on LWE
• Making the BKW algorithm practical for LWE
• On the asymptotic complexity of solving LWE
• Lattice decoding attacks on binary LWE

Cited in

(20)

• Memory-efficient BKW algorithm for solving the LWE problem
• Solving LWR via BDD Strategy: Modulus Switching Approach
• On solving LPN using BKW and variants, Implementation and analysis
• On the asymptotic complexity of solving LWE
• An improved BKW algorithm for LWE with applications to cryptography and lattices
• Lattice decoding attacks on binary LWE
• SoK: on the security of cryptographic problems from linear algebra
• Making the BKW algorithm practical for LWE
• Predicting the concrete security of LWE against the dual attack using binary search
• Solving LPN using covering codes
• On the complexity of the BKW algorithm on LWE
• LP solutions of vectorial integer subset sums -- cryptanalysis of Galbraith's binary matrix LWE
• A quasi-polynomial time algorithm for the extrapolated dihedral coset problem over power-of-two moduli
• Assessing the impact of a variant of MATZOV's dual attack on Kyber
• Wagner's algorithm provably runs in subexponential time for \(\mathrm{SIS}^\infty \)
• Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms
• On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL
• Further improvements of the estimation of key enumeration with applications to solving LWE
• (In)security of ring-LWE under partial key exposure
• Coded-BKW: solving LWE using lattice codes

This page was built for publication: Lazy modulus switching for the BKW algorithm on LWE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5402986)