Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IPI Letters

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

Published Mar 10, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.59973/ipil.171

Related papers

A Number Theoretic Investigation Of The Hardness Assumptions Underlying The Shortest Vector Problem In Lattice Cryptography

Jitendra Sharma

The lattice-based encryption paradigm (LBE) represents a new security model emphasizing flexible development, high levels of security, and efficient computations. It is now becoming more commonly seen as an alternative to other systems of post-quantum cryptography due to its foundations for both security (i.e., there is a high degree of confidence that lattice-based cryptography is secure) and efficiency with respect to computation. The theoretical basis for this report is related to the difficulty of solving the short vector problem (SVP) and other cryptographic hard problems concerning lattices. The report focuses on the hardness of lattice-based cryptography relative to three sub-components of the theoretical work: the relationship between geometric number theory and lattice-based systems, the application of AI to help determine parameters and the efficiencies of finding new lattice reduction algorithms, and finally estimating the difficulty to solve lattice problems. This report reviews the inherent difficulty of short vector problems (SVPs) and other kinds of SVPs, such as the closest vector problem. The report analyzes how to reduce both the time and space complexities for classical and quantum computing solutions through the discovery of new techniques based upon number-theoretic concepts. The report also discusses a number of examples, including digital signature products, encryption systems and homomorphic encryption systems as primitive constructions of cryptography based on lattices or through the properties of the lattice structures. Finally, based on number-theoretical relationships among complex numbers, the report provides a new theoretical approach to the construction of lattice-based systems and their strength relative to other types of cryptographic systems via the provision of theoretical bounds related to the lengths of lattice basis vectors.As a result of this research into bridging the divide between theoretical and practical cryptography, the results show that lattice-based systems have the capability of providing the strength to withstand quantum attacks. Through this research study, there is an improvement in how we understand mathematically the difficulty of lattices and how to create post-quantum secure cryptographic techniques through the use of lattices...

International Journal on Science and Technology•Mar 31, 2026•0 citations

Finding dense sublattices as low energy states of a Hamiltonian

Júlia Barberà-Rodríguez, Nicolas Gama, Anand Kumar Narayanan +1 more

Lattice-based cryptography has emerged as one of the most prominent candidates for postquantum cryptography, projected to be secure against the imminent threat of large-scale fault-tolerant quantum computers. The Shortest Vector Problem (SVP) is to find the shortest nonzero vector in a given lattice. It is fundamental to lattice-based cryptography and believed to be hard even for quantum computers. We study a natural generalization of the SVP known as the K -Densest Sublattice Problem ( K -DSP): to find the densest K -dimensional sublattice of a given lattice. We formulate K -DSP as finding the first excited state of a Z -basis Hamiltonian, making K -DSP amenable to investigation via an array of quantum algorithms, including Grover search, quantum Gibbs sampling, adiabatic, and variational quantum algorithms. The complexity of the algorithms depends on the basis through which the input lattice is presented. We present a classical polynomial-time algorithm that takes an arbitrary input basis and preprocesses it into inputs suited to quantum algorithms. With preprocessing, we prove that O ( K N 2 ) qubits suffice for solving K -DSP for N -dimensional input lattices. We empirically demonstrate the performance of a quantum approximate optimization algorithm K -DSP solver for low dimensions, highlighting the influence of a good preprocessed input basis. We then discuss the hardness of K -DSP in relation to the SVP, to see if there is a reason to build postquantum cryptography on K -DSP. We devise a quantum algorithm that solves K -DSP with runtime exponent ( 5 K N log 2 N ) / 2 . Therefore, for fixed K , K -DSP is no more than polynomially harder than the SVP. The central insight we use is similar in spirit to those underlying the best-known classical K -DSP algorithm due to Dadush and Micciancio. Whether the exponential dependence on K can be lowered remains an open question. Published by the American Physical Society 2024

arXiv:2309.16256•Physical Review Research•Dec 16, 2024•1 citation

Security and privacy in post-quantum blockchain using hybrid approach of subsets in SVP within lattice-based cryptography

Ram Kumar, Monica Sankat, Nyasha Ojha

This article addresses the challenges in improving the efficiency of solving the lattice-based cryptographic, Shortest Vector Problem (SVP), which is a crucial element to improve the security against the potential quantum attacks. We present a novel algorithm that integrates the concept of subsets generation with the SVP to enhance the efficiency of the lattice-based cryptographic schemes. This research delivers advancement by providing a more efficient method of solving the SVP. The method in this paper contributes towards the development of the security and privacy in cryptographic systems in the post-quantum era, surfacing the way for a vigorous encryption protocol.

Journal of Discrete Mathematical Sciences and Cryptography•Jan 1, 2025•0 citations

Variational quantum solutions to the Shortest Vector Problem

Martin R. Albrecht, Miloš Prokop, Yixin Shen +1 more

A fundamental computational problem is to find a shortest non-zero vector in Euclidean lattices, a problem known as the Shortest Vector Problem (SVP). This problem is believed to be hard even on quantum computers and thus plays a pivotal role in post-quantum cryptography. In this work we explore how (efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to solve SVP. Specifically, we map the problem to that of finding the ground state of a suitable Hamiltonian. In particular, (i) we establish new bounds for lattice enumeration, this allows us to obtain new bounds (resp. estimates) for the number of qubits required per dimension for any lattices (resp. random q-ary lattices) to solve SVP; (ii) we exclude the zero vector from the optimization space by proposing (a) a different classical optimisation loop or alternatively (b) a new mapping to the Hamiltonian. These improvements allow us to solve SVP in dimension up to 28 in a quantum emulation, significantly more than what was previously achieved, even for special cases. Finally, we extrapolate the size of NISQ devices that is required to be able to solve instances of lattices that are hard even for the best classical algorithms and find that with approximately 103 noisy qubits such instances can be tackled.

arXiv:2202.06757•Quantum•Mar 2, 2023•16 citations

From Factoring to Shortest Vector: A Unified Security Framework for Post-Quantum Cryptography

Revista, Zen, MATH, 10

The advent of quantum computing poses an existential threat to contemporary public-key cryptographic systems, which rely on the computational hardness of problems such as integer factorization and discrete logarithms. Shor's algorithm, capable of solving these problems efficiently on a sufficiently powerful quantum computer, necessitates a paradigm shift towards post-quantum cryptography (PQC). This paper proposes a unified security framework that bridges the conceptual gap between traditional number-theoretic hardness assumptions and the lattice-based problems central to PQC. We delve into the foundational mathematical problems, comparing the security arguments of factoring and discrete logarithm problems with the Shortest Vector Problem (SVP) and its variants in lattices. The framework emphasizes a consistent methodology for assessing quantum resistance, facilitating a more holistic understanding of cryptographic security in the post-quantum era. By analyzing the inherent complexities and interconnections of these hard problems, we aim to provide a structured approach to evaluate and design quantum-resistant cryptographic schemes, fostering robust and future-proof digital security infrastructure. This work contributes to the ongoing efforts in PQC standardization by offering a comparative lens for diverse cryptographic primitives.

•Nov 25, 2025•0 citations

Space-efficient classical and quantum algorithms for the shortest vector problem

Yanlin Chen, Kai-Min Chung, Ching–Yi Lai

A lattice is the integer span of some linearly independent vectors. Lattice problems have many significant applications in coding theory and cryptographic systems for their conjectured hardness. The Shortest Vector Problem (SVP), which asks to find a shortest nonzero vector in a lattice, is one of the well-known problems that are believed to be hard to solve, even with a quantum computer. In this paper we propose space-efficient classical and quantum algorithms for solving SVP. Currently the best time-efficient algorithm for solving SVP takes 2^{n+o(n)} time and 2^{n+o(n)} space. Our classical algorithm takes 2^{2.05n+o(n)} time to solve SVP and it requires only 2^{0.5n+o(n)} space. We then adapt our classical algorithm to a quantum version, which can solve SVP in time 2^{1.2553n+o(n)} with 2^{0.5n+o(n)} classical space and only poly(n) qubits.

arXiv:1709.00378•Quantum Information and Computation•Mar 1, 2018•3 citations
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 lattice-based encryption paradigm (LBE) represents a new security model emphasizing flexible development, high levels of security, and efficient computations. It is now becoming more commonly seen as an alternative to other systems of post-quantum cryptography due to its foundations for both security (i.e., there is a high degree of confidence that lattice-based cryptography is secure) and efficiency with respect to computation. The theoretical basis for this report is related to the difficulty of solving the short vector problem (SVP) and other cryptographic hard problems concerning lattices. The report focuses on the hardness of lattice-based cryptography relative to three sub-components of the theoretical work: the relationship between geometric number theory and lattice-based systems, the application of AI to help determine parameters and the efficiencies of finding new lattice reduction algorithms, and finally estimating the difficulty to solve lattice problems. This report reviews the inherent difficulty of short vector problems (SVPs) and other kinds of SVPs, such as the closest vector problem. The report analyzes how to reduce both the time and space complexities for classical and quantum computing solutions through the discovery of new techniques based upon number-theoretic concepts. The report also discusses a number of examples, including digital signature products, encryption systems and homomorphic encryption systems as primitive constructions of cryptography based on lattices or through the properties of the lattice structures. Finally, based on number-theoretical relationships among complex numbers, the report provides a new theoretical approach to the construction of lattice-based systems and their strength relative to other types of cryptographic systems via the provision of theoretical bounds related to the lengths of lattice basis vectors.As a result of this research into bridging the divide between theoretical and practical cryptography, the results show that lattice-based systems have the capability of providing the strength to withstand quantum attacks. Through this research study, there is an improvement in how we understand mathematically the difficulty of lattices and how to create post-quantum secure cryptographic techniques through the use of lattices...
Lattice-based cryptography has emerged as one of the most prominent candidates for postquantum cryptography, projected to be secure against the imminent threat of large-scale fault-tolerant quantum computers. The Shortest Vector Problem (SVP) is to find the shortest nonzero vector in a given lattice. It is fundamental to lattice-based cryptography and believed to be hard even for quantum computers. We study a natural generalization of the SVP known as the K -Densest Sublattice Problem ( K -DSP): to find the densest K -dimensional sublattice of a given lattice. We formulate K -DSP as finding the first excited state of a Z -basis Hamiltonian, making K -DSP amenable to investigation via an array of quantum algorithms, including Grover search, quantum Gibbs sampling, adiabatic, and variational quantum algorithms. The complexity of the algorithms depends on the basis through which the input lattice is presented. We present a classical polynomial-time algorithm that takes an arbitrary input basis and preprocesses it into inputs suited to quantum algorithms. With preprocessing, we prove that O ( K N 2 ) qubits suffice for solving K -DSP for N -dimensional input lattices. We empirically demonstrate the performance of a quantum approximate optimization algorithm K -DSP solver for low dimensions, highlighting the influence of a good preprocessed input basis. We then discuss the hardness of K -DSP in relation to the SVP, to see if there is a reason to build postquantum cryptography on K -DSP. We devise a quantum algorithm that solves K -DSP with runtime exponent ( 5 K N log 2 N ) / 2 . Therefore, for fixed K , K -DSP is no more than polynomially harder than the SVP. The central insight we use is similar in spirit to those underlying the best-known classical K -DSP algorithm due to Dadush and Micciancio. Whether the exponential dependence on K can be lowered remains an open question. Published by the American Physical Society 2024
This article addresses the challenges in improving the efficiency of solving the lattice-based cryptographic, Shortest Vector Problem (SVP), which is a crucial element to improve the security against the potential quantum attacks. We present a novel algorithm that integrates the concept of subsets generation with the SVP to enhance the efficiency of the lattice-based cryptographic schemes. This research delivers advancement by providing a more efficient method of solving the SVP. The method in this paper contributes towards the development of the security and privacy in cryptographic systems in the post-quantum era, surfacing the way for a vigorous encryption protocol.
A fundamental computational problem is to find a shortest non-zero vector in Euclidean lattices, a problem known as the Shortest Vector Problem (SVP). This problem is believed to be hard even on quantum computers and thus plays a pivotal role in post-quantum cryptography. In this work we explore how (efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to solve SVP. Specifically, we map the problem to that of finding the ground state of a suitable Hamiltonian. In particular, (i) we establish new bounds for lattice enumeration, this allows us to obtain new bounds (resp. estimates) for the number of qubits required per dimension for any lattices (resp. random q-ary lattices) to solve SVP; (ii) we exclude the zero vector from the optimization space by proposing (a) a different classical optimisation loop or alternatively (b) a new mapping to the Hamiltonian. These improvements allow us to solve SVP in dimension up to 28 in a quantum emulation, significantly more than what was previously achieved, even for special cases. Finally, we extrapolate the size of NISQ devices that is required to be able to solve instances of lattices that are hard even for the best classical algorithms and find that with approximately 103 noisy qubits such instances can be tackled.
The advent of quantum computing poses an existential threat to contemporary public-key cryptographic systems, which rely on the computational hardness of problems such as integer factorization and discrete logarithms. Shor's algorithm, capable of solving these problems efficiently on a sufficiently powerful quantum computer, necessitates a paradigm shift towards post-quantum cryptography (PQC). This paper proposes a unified security framework that bridges the conceptual gap between traditional number-theoretic hardness assumptions and the lattice-based problems central to PQC. We delve into the foundational mathematical problems, comparing the security arguments of factoring and discrete logarithm problems with the Shortest Vector Problem (SVP) and its variants in lattices. The framework emphasizes a consistent methodology for assessing quantum resistance, facilitating a more holistic understanding of cryptographic security in the post-quantum era. By analyzing the inherent complexities and interconnections of these hard problems, we aim to provide a structured approach to evaluate and design quantum-resistant cryptographic schemes, fostering robust and future-proof digital security infrastructure. This work contributes to the ongoing efforts in PQC standardization by offering a comparative lens for diverse cryptographic primitives.
A lattice is the integer span of some linearly independent vectors. Lattice problems have many significant applications in coding theory and cryptographic systems for their conjectured hardness. The Shortest Vector Problem (SVP), which asks to find a shortest nonzero vector in a lattice, is one of the well-known problems that are believed to be hard to solve, even with a quantum computer. In this paper we propose space-efficient classical and quantum algorithms for solving SVP. Currently the best time-efficient algorithm for solving SVP takes 2^{n+o(n)} time and 2^{n+o(n)} space. Our classical algorithm takes 2^{2.05n+o(n)} time to solve SVP and it requires only 2^{0.5n+o(n)} space. We then adapt our classical algorithm to a quantum version, which can solve SVP in time 2^{1.2553n+o(n)} with 2^{0.5n+o(n)} classical space and only poly(n) qubits.