On Lattices, Learning with Errors, Random Linear Codes, and Cryptography

• URL: http://arxiv.org/abs/2401.03703v1
• Date: Mon, 8 Jan 2024 07:14:54 GMT
• Title: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography
• Authors: Oded Regev
• Abstract summary: Main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. We present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem.
• Score: 0.27195102129094995
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity with error' problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., non-quantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size $\tilde{O}(n^2)$ and encrypting a message increases its size by a factor of $\tilde{O}(n)$ (in previous cryptosystems these values are $\tilde{O}(n^4)$ and $\tilde{O}(n^2)$, respectively). In fact, under the assumption that all parties share a random bit string of length $\tilde{O}(n^2)$, the size of the public key can be reduced to $\tilde{O}(n)$.

Related papers

• From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation [8.093227427119325]
  Indistinguishability obfuscation (iO) has emerged as a powerful cryptographic primitive with many implications.<n>In this work, we initiate a study of the power of quantum iO.
  arXiv  Detail & Related papers  (2025-06-24T11:50:33Z)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth [8.938538037322381]
  We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA. To our knowledge, it is the first mod-time circuit to achieve sublinear qubit count for a classically-hard factoring problem. We build on the quantum algorithm discovered by Li, Peng, Du and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition.
  arXiv  Detail & Related papers  (2024-12-17T05:34:54Z)
• On encoded quantum gate generation by iterative Lyapunov-based methods [0.0]
  The problem of encoded quantum gate generation is studied in this paper. The emphReference Input Generation Algorithm (RIGA) is generalized in this work.
  arXiv  Detail & Related papers  (2024-09-02T10:41:15Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  We solve the $k$-sparse parity problem with sign gradient descent (SGD) on two-layer fully-connected neural networks. We show that this approach can efficiently solve the $k$-sparse parity problem on a $d$-dimensional hypercube. We then demonstrate how a trained neural network with sign SGD can effectively approximate this good network, solving the $k$-parity problem with small statistical errors.
  arXiv  Detail & Related papers  (2024-04-18T17:57:53Z)
• A Quantum Approach for Reducing Communications in Classical Cryptographic Primitives [2.3465488122819123]
  We show that, perhaps surprisingly, it's possible to solve this problem with quantum techniques under much weaker assumptions. Our work conveys an interesting message that quantum cryptography could outperform classical cryptography in a new type of problems.
  arXiv  Detail & Related papers  (2023-10-08T16:07:46Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
  We show that for $q = pm$ where $p$ is small relative to the code block-size $n$, there is a quantum algorithm that solves the problem in time. On the other hand, classical algorithms can efficiently solve the problem only for much smaller inverse factors.
  arXiv  Detail & Related papers  (2022-10-20T19:35:50Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  We study the complexity of PAC learning halfspaces in the presence of Massart noise. We show that no-time Massart halfspace learners can achieve error better than $Omega(eta)$, even if the optimal 0-1 error is small.
  arXiv  Detail & Related papers  (2022-07-28T17:50:53Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Efficient Quantum Public-Key Encryption From Learning With Errors [1.8021287677546958]
  Our main result is a quantum public-key encryption scheme based on the Extrapolated Dihedral Coset problem (EDCP) For limited number of public keys, the proposed scheme is information-theoretically secure.
  arXiv  Detail & Related papers  (2021-05-26T18:48:26Z)
• Lattice sieving via quantum random walks [0.0]
  lattice-based cryptography is one of the leading proposals for post-quantum cryptography. Shortest Vector Problem (SVP) is arguably the most important problem for the cryptanalysis of lattice-based cryptography. We present an algorithm that has a (heuristic) running time of $20.2570 d + o(d)$ where $d$ is the lattice dimension.
  arXiv  Detail & Related papers  (2021-05-12T11:59:30Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  We study the problem of learning one-hidden-layer ReLU networks with $k$ hidden units on $mathbbRd$ under Gaussian marginals. For the case of positive coefficients, we give the first-time algorithm for this learning problem for $k$ up to $tildeOOmega(sqrtlog d)$.
  arXiv  Detail & Related papers  (2020-06-22T17:53:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.