This paper presents a novel framework for enhancing the quantum resistance of NTRUEncrypt using Markov Chain Monte Carlo (MCMC) methods. We establish formal bounds on sampling efficiency and provide security reductions to lattice problems, bridging theoretical guarantees with practical implementations. Key contributions include: a new methodology for exploring private key vulnerabilities while maintaining quantum resistance, provable mixing time bounds for high-dimensional lattices, and concrete metrics linking MCMC parameters to lattice hardness assumptions. Numerical experiments validate our approach, demonstrating improved security guarantees and computational efficiency. These findings advance the theoretical understanding and practical adoption of NTRU- Encrypt in the post-quantum era.
Journal reference
Global Journal of Engineering Innovations and Interdisciplinary Research, 2025, GJEIIR, Vol 2 (Issue 1), p. 1-6
This paper presents a novel framework for enhancing the quantum resistance of NTRUEncrypt using Markov Chain Monte Carlo (MCMC) methods. We establish formal bounds on sampling efficiency and provide security reductions to lattice problems, bridging theoretical guarantees with practical implementations. Key contributions include: a new methodology for exploring private key vulnerabilities while maintaining quantum resistance, provable mixing time bounds for high-dimensional lattices, and concrete metrics linking MCMC parameters to lattice hardness assumptions. Numerical experiments validate our approach, demonstrating improved security guarantees and computational efficiency. These findings advance the theoretical understanding and practical adoption of NTRU- Encrypt in the post-quantum era.
This paper presents a novel framework for enhancing the quantum resistance of NTRUEncrypt usingMarkov Chain Monte Carlo (MCMC) methods. We establish formal bounds on sampling efficiencyand provide security reductions to lattice problems, bridging theoretical guarantees with practicalimplementations. Key contributions include: a new methodology for exploring private key vulnerabilitieswhile maintaining quantum resistance, provable mixing time bounds for high-dimensional lattices, andconcrete metrics linking MCMC parameters to lattice hardness assumptions. Numerical experimentsvalidate our approach, demonstrating improved security guarantees and computational efficiency.These findings advance the theoretical understanding and practical adoption of NTRU- Encrypt in thepost-quantum era.
Over the past decades, the problem of classical Gibbs sampling has led to one of the most powerful algorithmic families of the computer age: the Markov Chain Monte Carlo algorithms. Recent theoretical advances in quantum Gibbs sampling have, understandably, sparked considerable excitement. A recent breakthrough provided the first Lindbladians that provably drive a general quantum system to its Gibbs state, efficiently up to the mixing time. In this thesis, we bridge the gap between theory and implementation, with both analytical and numerical contributions. We work out every detail -- from transition rate choices, through quadrature, Trotter, and generator-splitting errors, to quantum circuits that could run on early fault-tolerant quantum computers. Using our fast Krylov-based Lindblad simulators and analysers, we numerically confirm existing theoretical Gibbs sampling results, cross-check our theoretical contributions, and do extrapolatory simulations to understand how the structure of these Gibbs samplers affects convergence rates. Our open-source framework, QuantumFurnace.jl, is built to work hand in hand with theory, providing the community with a tool to further advance quantum Gibbs sampling.
Sampling from complicated probability distributions is a hard computational problem arising in many fields, including statistical physics, optimization, and machine learning. Quantum computers have recently been used to sample from complicated distributions that are hard to sample from classically, but which seldom arise in applications. Here we introduce a quantum algorithm to sample from distributions that pose a bottleneck in several applications, which we implement on a superconducting quantum processor. The algorithm performs Markov chain Monte Carlo (MCMC), a popular iterative sampling technique, to sample from the Boltzmann distribution of classical Ising models. In each step, the quantum processor explores the model in superposition to propose a random move, which is then accepted or rejected by a classical computer and returned to the quantum processor, ensuring convergence to the desired Boltzmann distribution. We find that this quantum algorithm converges in fewer iterations than common classical MCMC alternatives on relevant problem instances, both in simulations and experiments. It therefore opens a new path for quantum computers to solve useful--not merely difficult--problems in the near term.
Lattice-based cryptography has emerged as a leading approach for post-quantum secure communication, particularly in key exchange mechanisms such as Key Encapsulation Mechanisms (KEMs). Prominent schemes based on Learning with Errors (LWE), Ring-LWE, Module-LWE, and NTRU lattices provide strong resistance to quantum attacks while maintaining practical efficiency. A key factor influencing their performance and security is polynomial sampling, which controls noise generation, randomness, and key distribution. This systematic review examines advancements in lattice-based key exchange mechanisms with a focus on optimized polynomial sampling techniques, based on 30 peer-reviewed studies. The approaches are categorized into algorithmic improvements, hardware acceleration, side-channel resistant sampling, and emerging intelligent optimization methods. Efficient polynomial arithmetic, Number Theoretic Transform (NTT)-based multiplication, and structured lattices significantly enhance performance. Optimized sampling techniques reduce computational cost and energy consumption while preserving statistical accuracy. However, polynomial sampling remains vulnerable to side-channel attacks such as timing and power analysis, prompting the use of countermeasures like constant-time and masked sampling. Hardware implementations further improve efficiency, though challenges persist in balancing scalability, security, and performance, highlighting the need for adaptive and robust solutions.
The advent of large-scale quantum computers poses an existential threat to the security of current public-key cryptosystems, such as RSA and Elliptic Curve Cryptography (ECC), which rely on the computational intractability of integer factorization and discrete logarithms. This paper explores lattice-based cryptography as a promising candidate for post-quantum security. We delve into the mathematical foundations of lattices, specifically focusing on hard problems like the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Small Integer Solution (SIS), and Learning With Errors (LWE) problems, which are believed to remain intractable even for quantum computers. We provide a comprehensive review of prominent lattice-based constructions, including NTRU, Kyber, and Dilithium, highlighting their security proofs, efficiency considerations, and suitability for various cryptographic primitives such as public-key encryption, key-exchange mechanisms, and digital signatures. Furthermore, we discuss the challenges and opportunities associated with their deployment, including parameter selection, resistance to side-channel attacks, and integration into existing cryptographic infrastructures. By examining the theoretical underpinnings and practical implications, this work aims to solidify understanding of lattice-based methods as a robust and essential component of the cryptographic landscape in the quantum era, moving beyond the traditional RSA frontier.
Since the presentation of NTRU public-key cryptosystem by Hoffstein, Pipher and Silverman, its favorable properties, such as easily created keys, high speed, excellent performance and conjectured resistance to quantum computers, have made it to be of great use. This paper proposes an enhanced scheme based on the hard learning with error over ring (R-LWE) problem to improve the security of the modified NTRUEncrypt presented by Stehle and Steinfled. We used part of the padding ideas of Fujisaki and Okamoto to obtain this scheme. It is semantically secure in strong sense of indistinguishability against adaptive chosen-ciphertext attacks in the random oracle model assuming the quantum hardness of standard worst-case problem over ideal lattices. It is also possible to arbitrarily decrease the error probability, and even to eliminate it completely. We gave the detailed analysis using the known results from classic works. Furthermore, this scheme owns many advantages such as the uniformity of public key, usual assumptions and the freedom for coding messages.