Tight Quantum-Security Bounds and Parameter Optimization for SPHINCS+ and NTRU

2025/08/06 by Xu, Ruopengyu, Liu, Chenglian
#06B99 #60E15 #68Q12 #81P94 #94A60 #B.8.0 #Cryptography and Security (cs.CR) #Discrete Mathematics (cs.DM) #E.3 #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #G.2.0 #Number Theory (math.NT) #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2508.19250

Abstract

The imminent threat of quantum computing necessitates quantum-resistant cryptosystems. This paper establishes tight security bounds for two NIST PQC finalists: SPHINCS+ (hash-based) and NTRU (lattice-based). Our key contributions include: (1) A quantum attack model incorporating decoherence effects (τ_d) and parallelization limits; (2) Improved entropy concentration inequalities reducing SPHINCS+ parameters by 15-20%; (3) Optimized NTRU lattice parameters via quantum lattice entropy H_Q(Λ); (4) Tightened NTRU-to-LWE reduction with polynomial-factor improvement. Theoretical results demonstrate significant security enhancement over existing constructions, providing implementable parameters for standardization.

Citations

• Quantum Computing in the NISQ era and beyond
• Quantum Lower Bounds by Polynomials
• A Topological Oracle Model for Proving P ≠ NP
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Related

• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems
• On the Semantic Security of NTRU -- with a gentle introduction to cryptography
• Enhancing NTRUEncrypt Security Using Markov Chain Monte Carlo Methods: Theory and Practice
• Post-Quantum Cryptography: Securing Digital Communication in the Quantum Era
• Post-Quantum Cryptography and Quantum-Safe Security: A Comprehensive Survey