Quantum-Secure Key Exchange Using Heisenberg Lie Algebras: Design, Analysis and Implementation

Abstract

This work introduces a new post-quantum key exchange protocol based on the computational hardness of the Nilpotent Commutator Inversion Problem (NCIP) in Heisenberg Lie algebras over GF(p), where p ≈ 2256. Unlike traditional methods employing integer factorization or discrete logarithms, our scheme capitalizes on the non-linear algebraic nature of nilpotent matrices for quantum resistance. The protocol demonstrates exceptional efficiency in resource-constrained environments, generating 64-byte public keys in 0.024 ms for 3×3 matrices while maintaining 128-bit post-quantum security.
Through comprehensive comparison with NIST-standardized schemes (Kyber, SPHINCS+), we show superior performance in memory footprint (0.01 KB) and computational overhead, particularly for IoT applications. Experimental evaluation confirms 95.1% success rates for 8 × 8 matrices (256-bit security) with sub-millisecond latency, while security analysis establishes resistance to both classical linear algebra attacks and quantum algorithms (Shors, Grovers) through the NCIP hardness assumption. The work provides concrete parameter recommendations aligned with NIST security levels and demonstrates practical implementation in Python using optimized matrix operations over GF(pn). This Lie algebra-based approach offers a mathematically distinct alternative to existing post-quantum primitives, with particular advantages for scalable, lightweight deployments in edge computing and large-scale networks.