Memory-efficient attacks on small LWE keys

DOI10.1007/978-981-99-8730-6_3MaRDI QIDQ6604868zbMATH OpenFDO

Authors Andre Esser, Rahul Girme, Arindam Mukherjee, Santanu Sarkar

Publication date 13 September 2024

zbMATH Keywords

learning with errorsrepresentation techniquenested collision searchpolynomial memory

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Data encryption (aspects in computer science) (68P25) Cryptography (94A60) Quantum cryptography (quantum-theoretic aspects) (81P94)

Recommendations

• Memory-efficient attacks on small LWE keys
• How to meet ternary LWE keys
• How to enumerate LWE keys as narrow as in \textsc{Kyber}/\textsc{Dilithium}
• Quantum key search for ternary LWE
• Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS

Cites work

• scientific article; zbMATH DE number 1186948 (Why is no real title available?)
• A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU
• A Subfield Lattice Attack on Overstretched NTRU Assumptions
• Advanced lattice sieving on GPUs, with tensor cores
• Efficient public key encryption based on ideal lattices (extended abstract)
• Faster enumeration-based lattice reduction: root Hermite factor \(k^{1/(2k)}\) time \(k^{k/8+o(k)}\)
• Fully homomorphic encryption using ideal lattices
• High-speed key encapsulation from NTRU
• How to meet ternary LWE keys
• Hybrid dual and meet-LWE attack
• Implementing Joux-Vitse's crossbred algorithm for solving \(\mathcal M\mathcal Q\) systems over \(\mathbb F_2\) on GPUs
• Improved Generic Algorithms for Hard Knapsacks
• Improved classical and quantum algorithms for subset-sum
• Improved low-memory subset sum and LPN algorithms via multiple collisions
• Lattice enumeration using extreme pruning
• Lattice signatures and bimodal Gaussians
• Lattice signatures without trapdoors
• Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory
• McEliece needs a break -- solving McEliece-1284 and quasi-cyclic-2918 with modern ISD
• Memory-Efficient Algorithms for Finding Needles in Haystacks
• NTRU prime: reducing attack surface at low cost
• New generic algorithms for hard knapsacks
• New time-memory trade-offs for subset sum -- improving ISD in theory and practice
• On ideal lattices and learning with errors over rings
• On lattices, learning with errors, random linear codes, and cryptography
• On the cost of computing isogenies between supersingular elliptic curves
• Parallel collision search with cryptanalytic applications
• Parallel isogeny path finding with limited memory
• Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems
• Public-key cryptosystems from the worst-case shortest vector problem
• Reduced memory meet-in-the-middle attack against the NTRU private key
• Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction
• Ternary Syndrome Decoding with large weight

Cited in

(3)

• Memory-efficient attacks on small LWE keys
• Low memory attacks on small key CSIDH
• How to enumerate LWE keys as narrow as in \textsc{Kyber}/\textsc{Dilithium}

This page was built for publication: Memory-efficient attacks on small LWE keys

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