Improved low-memory subset sum and LPN algorithms via multiple collisions

DOI10.1007/978-3-030-35199-1_9MaRDI QIDQ2177659zbMATH OpenOpenAlexFDO

Authors Claire Delaplace, Andre Esser, Alexander May

Publication date 6 May 2020

Full work available at URL https://doi.org/10.1007/978-3-030-35199-1_9

zbMATH Keywords

parallel collision searchrepresentationstime-memory trade-off

Mathematics Subject Classification ID

Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Recommendations

• Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory
• Dissection-BKW
• Improved classical and quantum algorithms for subset-sum
• On iterative collision search for LPN and subset sum
• LPN decoded

Cited in

(13)

• On iterative collision search for LPN and subset sum
• Tight time-space lower bounds for finding multiple collision pairs and their applications
• Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory
• Making the BKW algorithm practical for LWE
• Improved classical and quantum algorithms for subset-sum
• New time-memory trade-offs for subset sum -- improving ISD in theory and practice
• 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
• Parallel isogeny path finding with limited memory
• Memory-efficient attacks on small LWE keys
• Memory-efficient attacks on small LWE keys
• Memory-efficient BKW algorithm for solving the LWE problem
• Quantum time-space tradeoff for finding multiple collision pairs

This page was built for publication: Improved low-memory subset sum and LPN algorithms via multiple collisions

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