Solving LPN using covering codes

DOI10.1007/S00145-019-09338-8zbMath1455.94161OpenAlexW2980561754WikidataQ127022640 ScholiaQ127022640MaRDI QIDQ2303453

Carl Löndahl, Qian Guo, Thomas Johansson

Publication date: 3 March 2020

Published in: Journal of Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00145-019-09338-8

zbMATH Keywords

covering codesBKWHBLapinlearning from parity with noise problem (LPN)LPN-C

Mathematics Subject Classification ID

Cryptography (94A60) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Related Items (8)

Making the BKW algorithm practical for LWE ⋮ Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS ⋮ Pseudorandom correlation functions from variable-density LPN, revisited ⋮ Upper bounds on the length function for covering codes with covering radius \(R\) and codimension \(tR+1\) ⋮ A non-heuristic approach to time-space tradeoffs and optimizations for BKW ⋮ Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms ⋮ Correlated pseudorandomness from expand-accumulate codes ⋮ Correlated pseudorandomness from the hardness of quasi-abelian decoding

Cites Work

• Unnamed Item
• Unnamed Item
• On solving LPN using BKW and variants, Implementation and analysis
• Memoryless near-collisions via coding theory
• LPN decoded
• Memoryless near-collisions, revisited
• Coded-BKW with sieving
• On probability of success in linear and differential cryptanalysis
• Faster Algorithms for Solving LPN
• Never Trust a Bunny
• Message Authentication, Revisited
• Solving LPN Using Covering Codes
• Optimization of $$\mathsf {LPN}$$ Solving Algorithms
• A New Algorithm for Solving Ring-LPN With a Reducible Polynomial
• Efficient Authentication from Hard Learning Problems
• Coded-BKW: Solving LWE Using Lattice Codes
• An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
• How to Encrypt with the LPN Problem
• An Improved LPN Algorithm
• Parallel and Concurrent Security of the HB and HB +  Protocols
• Lapin: An Efficient Authentication Protocol Based on Ring-LPN
• HELEN: A Public-Key Cryptosystem Based on the LPN and the Decisional Minimal Distance Problems
• Lazy Modulus Switching for the BKW Algorithm on LWE
• Authenticating Pervasive Devices with Human Protocols
• : Increasing the Security and Efficiency of
• Noise-tolerant learning, the parity problem, and the statistical query model

This page was built for publication: Solving LPN using covering codes