Theoretical Approaches to Solving the Shortest Vector Problem in NP-Hard Lattice-Based Cryptography with Post-SUSY Theories of Quantum Gravity in Polynomial Time by Orch-Or

Trevor Nestor

IPI LettersMar 10, 20251 citation

ACM SIGACT News

Complexity theory

Lane A. Hemaspaandra

Published Sep 1, 2001• 12 citations

Publisher

Abstract

We present high-level technical summaries of five recent results on the computational complexity of the shortest lattice vector problem.

DOI: 10.1145/500559.500560

Related papers

Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search

Thijs Laarhoven, Michele Mosca, Joop van de Pol

arXiv:1301.6176Lecture notes in computer scienceJan 1, 201327 citations

Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven, Michele Mosca, Joop van de Pol

Abstract By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time 21.799n+o(n), improving upon the classical time complexities of 22.465n+o(n) of Pujol and Stehle ́ and the 22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.286n+o(n), improving upon the classical time complexity of 20.337n+o(n) of Laarhoven. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem. Keywords lattices · shortest vector problem · sieving · quantum search 1Abstract By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time 21.799n+o(n), improving upon the classical time complexities of 22.465n+o(n) of Pujol and Stehle ́ and the 22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.286n+o(n), improving upon the classical time complexity of 20.337n+o(n) of Laarhoven. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem. Keywords lattices · shortest vector problem · sieving · quantum search 1

Jan 1, 20141 citation

Quantum Complexity for Vector Domination Problem

Andris Ambainis, Ansis Zvirbulis

Lecture notes in computer scienceDec 19, 20220 citations

Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven, Michele Mosca, Joop van de Pol

By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time $2^{1.799n + o(n)}$ , improving upon the classical time complexities of $2^{2.465n + o(n)}$ of Pujol and Stehlé and the $2^{2n + o(n)}$ of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time $2^{0.268n + o(n)}$ , improving upon the classical time complexity of $2^{0.298n + o(n)}$ of Laarhoven and De Weger. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time $$2^{1.799n + o(n)}$$ , improving upon the classical time complexities of $$2^{2.465n + o(n)}$$ of Pujol and Stehlé and the $$2^{2n + o(n)}$$ of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time $$2^{0.268n + o(n)}$$ , improving upon the classical time complexity of $$2^{0.298n + o(n)}$$ of Laarhoven and De Weger. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.

Designs Codes and CryptographyApr 13, 201591 citations

Hard combinatorial problems and minor embeddings on lattice graphs

Andrew Lucas

Quantum Information ProcessingMay 16, 201922 citations

Theoretical Approaches to Solving the Shortest Vector Problem in NP-Hard Lattice-Based Cryptography with Post-SUSY Theories of Quantum Gravity in Polynomial Time by Orch-Or

Trevor Nestor

The Shortest Vector Problem (SVP) is a cornerstone of lattice-based cryptography, underpinning the security of numerous cryptographic schemes like NTRU. Given its NP-hardness, efficient solutions to SVP have profound implications for both cryptography and computational complexity theory. This paper presents an innovative framework that integrates concepts from quantum gravity, non-commutative geometry, spectral theory, and post-supersymmetry (post-SUSY) particle physics to address SVP. By mapping high-dimensional lattice points to spinfoam networks and by means of Hamiltonian engineering, it is theoretically possible to devise new algorithms that leverage the interactions topologically protected Majorana fermionparticles have with the gravitational field through the spectral action principle to loop through these spinfoam networks where SVP vectors could then be encoded onto the spectrum of the corresponding Dirac-like dilation operators within the system. We establish a novel approach that leverages post-SUSY physics and theories of quantum gravity to achieve algorithmic speedups beyond those expected by conventional quantum computers. This interdisciplinary methodology not only proposes potential polynomial-time algorithms for SVP, but also bridges gaps between theoretical physics and cryptographic applications, providing further insights into the Riemann Hypothesis (RH) and the Hilbert-P ´olya Conjecture. Possible directions for experimental realization through biologically inspired hardware or biological tissues by orchestrated objective reduction (Orch-Or) theory are discussed.The Shortest Vector Problem (SVP) is a cornerstone of lattice-based cryptography, underpinning the security of numerous cryptographic schemes like NTRU. Given its NP-hardness, efficient solutions to SVP have profound implications for both cryptography and computational complexity theory. This paper presents an innovative framework that integrates concepts from quantum gravity, non-commutative geometry, spectral theory, and post-supersymmetry (post-SUSY) particle physics to address SVP. By mapping high-dimensional lattice points to spinfoam networks and by means of Hamiltonian engineering, it is theoretically possible to devise new algorithms that leverage the interactions topologically protected Majorana fermionparticles have with the gravitational field through the spectral action principle to loop through these spinfoam networks where SVP vectors could then be encoded onto the spectrum of the corresponding Dirac-like dilation operators within the system. We establish a novel approach that leverages post-SUSY physics and theories of quantum gravity to achieve algorithmic speedups beyond those expected by conventional quantum computers. This interdisciplinary methodology not only proposes potential polynomial-time algorithms for SVP, but also bridges gaps between theoretical physics and cryptographic applications, providing further insights into the Riemann Hypothesis (RH) and the Hilbert-P ´olya Conjecture. Possible directions for experimental realization through biologically inspired hardware or biological tissues by orchestrated objective reduction (Orch-Or) theory are discussed.

IPI LettersMar 10, 20251 citation

2^{1.799n + o(n)}

, improving upon the classical time complexities of

2^{2.465n + o(n)}

of Pujol and Stehlé and the

2^{2n + o(n)}

of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time

2^{0.268n + o(n)}

, improving upon the classical time complexity of

2^{0.298n + o(n)}

of Laarhoven and De Weger. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.