PQ-Sortition: A Post-Quantum Cryptographic Sortition Protocol from NTRU Lattices with Applications to Proof-of-Stake Blockchains

Abstract

PQ-Sortition is a post-quantum cryptographic sortition protocol constructed from the NTRU lattice hardness assumption and instantiated using Falcon-512 (FN-DSA). The construction uses deterministic Falcon signing to obtain a reproducible, publicly verifiable proof and combines it with a consensus-layer commit-then-reveal mechanism to address the lack of unconditional uniqueness inherent in GPV-style lattice signatures. The work introduces NTRU-Sortition, a many-time lattice-based verifiable random function construction, and provides formal analyses of third-party uniqueness, pseudorandomness under the NTRU-SIS assumption in the Random Oracle Model, and provability. The paper further defines PQ-Sortition as a post-quantum proof-of-stake leader-election protocol using a historical randomness beacon, stake-weighted sortition, adaptive difficulty, equivocation slashing, and grinding resistance. The Falcon-512 instantiation provides a 32-byte output and proofs of up to 666 bytes. The paper also presents concrete performance measurements, security parameters, consensus integration details, comparisons with prior post-quantum VRF constructions, and open research problems.