Related papers: Lattice Based Crypto breaks in a Superposition of Spacetimes

Lattice Based Crypto breaks in a Superposition of Spacetimes

URL: http://arxiv.org/abs/2503.21400v2
Date: Tue, 01 Apr 2025 09:08:20 GMT
Title: Lattice Based Crypto breaks in a Superposition of Spacetimes
Authors: Divesh Aggarwal, Shashwat Agrawal, Rajendra Kumar,
Abstract summary: We explore the computational implications of a superposition of spacetimes, a phenomenon hypothesized in quantum gravity theories.<n>The security of lattice based cryptography schemes will be compromised in a computational model based on superposition of spacetimes.
Score: 3.125009120066803
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We explore the computational implications of a superposition of spacetimes, a phenomenon hypothesized in quantum gravity theories. This was initiated by Shmueli (2024) where the author introduced the complexity class $\mathbf{BQP^{OI}}$ consisting of promise problems decidable by quantum polynomial time algorithms with access to an oracle for computing order interference. In this work, it was shown that the Graph Isomorphism problem and the Gap Closest Vector Problem (with approximation factor $\mathcal{O}(n^{3/2})$) are in $\mathbf{BQP^{OI}}$. We extend this result by showing that the entire complexity class $\mathbf{SZK}$ (Statistical Zero Knowledge) is contained within $\mathbf{BQP^{OI}}$. This immediately implies that the security of numerous lattice based cryptography schemes will be compromised in a computational model based on superposition of spacetimes, since these often rely on the hardness of the Learning with Errors problem, which is in $\mathbf{SZK}$.

Related papers

Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z)
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)
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)
A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
arXiv Detail & Related papers (2021-08-19T16:16:48Z)
Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with $mathcal N=2 $ supersymmetry. Our main motivation for studying this is the fact that the ground state energy of a supersymmetric system is exactly zero if and only if a certain cohomology group is nontrivial.
arXiv Detail & Related papers (2021-06-30T18:00:01Z)
Quantum Logarithmic Space and Post-selection [0.4588028371034406]
Post-selection is an influential concept introduced to the field of quantum complexity theory by Aaronson (Proceedings of the Royal Society A, 2005) Our main result shows the identity $sf PostBQL=$, i.e., the class of problems that can be solved by a bounded-error (polynomial-time) logarithmic-space quantum algorithm with post-selection ($sf PostBQL$) We also show that $sf$ coincides with the class of problems that can be solved by bounded-error logarithmic-space quantum algorithms that have no time bound.
arXiv Detail & Related papers (2021-05-06T14:02:01Z)
Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
arXiv Detail & Related papers (2020-12-17T16:43:11Z)
Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
arXiv Detail & Related papers (2020-12-03T14:03:20Z)
On the complexity of zero gap MIP* [0.11470070927586014]
We show that the class $mathsfMIP*$ is equal to $mathsfRE$. In particular this shows that the complexity of approximating the quantum value of a non-local game $G$ is equivalent to the complexity of the Halting problem.
arXiv Detail & Related papers (2020-02-24T19:11:01Z)

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