Quantum search-to-decision reduction for the LWE problem

DOI10.1007/978-3-031-37679-5_17MaRDI QIDQ6186362

Kyohei Sudo, Keisuke Hara, Yusuke Yoshida, Masayuki Tezuka

Publication date: 2 February 2024

Published in: Progress in Cryptology - AFRICACRYPT 2023 (Search for Journal in Brave)

zbMATH Keywords

learning parity with noisequery complexitysample complexitylearning with errorsquantum reductionGoldreich-Levin theoremsearch-to-decision reduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Artificial neural networks and deep learning (68T07) Cryptography (94A60) Quantum cryptography (quantum-theoretic aspects) (81P94)

Cites Work

• Unnamed Item
• Unnamed Item
• Quantum algorithms for the Goldreich-Levin learning problem
• Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
• Low Noise LPN: KDM Secure Public Key Encryption and Sample Amplification
• Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
• Public-Key Encryption Schemes with Auxiliary Inputs
• Trapdoors for hard lattices and new cryptographic constructions
• Bonsai Trees, or How to Delegate a Lattice Basis
• Efficient Lattice (H)IBE in the Standard Model
• Parallel and Concurrent Security of the HB and HB +  Protocols
• Local Decoding and Testing for Homomorphisms
• A Framework for Efficient and Composable Oblivious Transfer
• Cryptography with Constant Input Locality
• Public-key cryptosystems from the worst-case shortest vector problem
• Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Classical hardness of learning with errors
• On lattices, learning with errors, random linear codes, and cryptography
• Constructive post-quantum reductions

This page was built for publication: Quantum search-to-decision reduction for the LWE problem