Memory-sample lower bounds for LWE

DOI10.1007/978-3-031-68388-6_7MaRDI QIDQ6652965zbMATH OpenFDO

Authors Mingqi Lu, Junzhao Yang

Publication date 13 December 2024

Full work available at URL https://doi.org/10.1007/978-3-031-68388-6_7

zbMATH Keywords

branching programlearning with errorsmemory-sample tradeoffsspace lower bound

Mathematics Subject Classification ID

Cryptography (94A60)

Recommendations

• Extractor-based time-space lower bounds for learning
• Fast learning requires good memory: a time-space lower bound for parity learning
• Classical hardness of learning with errors
• Revisiting the hardness of binary error LWE
• Time-space lower bounds for two-pass learning

Cites work

• Extractor-based time-space lower bounds for learning
• Fast learning requires good memory: a time-space lower bound for parity learning
• Memory-sample tradeoffs for linear regression with small error
• Pseudorandom functions and lattices
• Simple schemes in the bounded storage model
• Time-space hardness of learning sparse parities
• Time-space lower bounds for two-pass learning

Cited in

(2)

• Time-space lower bounds for two-pass learning
• Refined attack on LWE with hints: constructing lattice via Gaussian elimination

This page was built for publication: Memory-sample lower bounds for LWE

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