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.
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.
We introduce NTRU-VRF, the first verifiable random function (VRF) constructed directly from the NTRU lattice hardness assumption, and instantiated concretely using the NIST-standardized Falcon-512 (FN-DSA) signature scheme. A VRF is a pseudorandom function that produces a publicly verifiable proof of correctness for each output. All currently deployed VRFs (IETF RFC 9381, Algorand, Ethereum) rely on elliptic-curve assumptions broken by Shor's algorithm. Prior post-quantum VRF constructions either require only a few-time security guarantee (Esgin et al., ePrint 2020/1222), rely on symmetric primitives that lack a worst-case lattice hardness reduction (Buser et al., ePrint 2021/302), or are based on Module-LWE/Module-SIS rather than NTRU. No prior work constructs a many-time, lattice-based VRF from NTRU hardness with a formal security proof. Our construction exploits a fundamental and previously unformalized property of Falcon's deterministic signing mode: for any fixed public key and input, there exists exactly one valid short-norm signature. This unique-signature property is the key structural feature that transforms a lattice signature into a VRF. We prove three theorems: Uniqueness: For any input, the NTRU-VRF output is unique. This follows directly from the unique-short-coset-vector property of the NTRU lattice. Pseudorandomness: If the Short Integer Solution (SIS) problem on NTRU lattices is hard and the hash function is modelled as a random oracle, then the VRF output is computationally indistinguishable from a uniformly random value. Provability: The Falcon signature is an efficient, publicly verifiable proof, checkable by any party holding the public key. As a concrete application, we define PQ-Sortition, a post-quantum proof-of-stake leader-election protocol that replaces ECVRF-based sortition with our NTRU-VRF construction. We provide the entropy-chain design, stake-weighted win condition, adaptive liveness mechanism, equivocation slashing, and a formal security analysis of the resulting consensus protocol. Instantiated with Falcon-512, NTRU-VRF achieves a VRF output of 32 bytes, a proof size of <= 666 bytes, evaluation time of ~0.8 ms, and verification time of ~0.1 ms on standard hardware—significantly outperforming all existing post-quantum VRF constructions and making it the first many-time, compact, lattice-based VRF suitable for high-throughput blockchain consensus.
A verifiable random function (VRF in short) is a powerful pseudo-random function that provides a non-interactively public verifiable proof for the correctness of its output. Recently, VRFs have found essential applications in blockchain design, such as random beacons and proof-of-stake consensus protocols. To our knowledge, the first generation of blockchain systems used inherently inefficient proof-of-work consensuses, and the research community tried to achieve the same properties by proposing proof-of-stake schemes where resource-intensive proof-of-work is emulated by cryptographic constructions. Unfortunately, those most discussed proof-of-stake consensuses (e.g., Algorand and Ouroborous family) are not future-proof because the building blocks are secure only under the classical hard assumptions; in particular, their designs ignore the advent of quantum computing and its implications. In this paper, we propose a generic compiler to obtain the post-quantum VRF from the simple VRF solution using symmetric-key primitives (e.g., non-interactive zero-knowledge system) with an intrinsic property of quantum-secure. Our novel solution is realized via two efficient zero-knowledge systems ZKBoo and ZKB++, respectively, to validate the compiler correctness. Our proof-of-concept implementation indicates that even today, the overheads introduced by our solution are acceptable in real-world deployments. We also demonstrate potential applications of a quantum-secure VRF, such as quantum-secure decentralized random beacon and lottery-based proof of stake consensus blockchain protocol.
The long-term security of public blockchains strictly depends on the hardness assumptions of the underlying digital signature schemes. In the current scenario, most deployed cryptocurrencies and blockchain platforms rely on elliptic-curve cryptography, which is vulnerable to quantum attacks due to Shor's algorithm. Therefore, it is important to understand how post-quantum (PQ) digital signatures behave when integrated into real blockchain systems. This report presents a blockchain prototype that supports multiple quantum-secure signature algorithms, focusing on CRYSTALS-Dilithium, Falcon and Hawk as lattice-based schemes. This report also describes the design of the prototype and discusses the performance metrics, which include key generation, signing, verification times, key sizes and signature sizes. This report covers the problem, background, and experimental methodology, also providing a detailed comparison of quantum-secure signatures in a blockchain context and extending the analysis to schemes such as HAETAE.
Conventional public-key cryptographic systems are increasingly threatened by advances in quantum computing, accelerating the need for robust post-quantum cryptographic solutions. Among these, Falcon, a compact lattice-based digital signature scheme, has emerged as a leading candidate in the NIST post-quantum standardization process due to its efficiency and theoretical security grounded in hard lattice problems. This work introduces Falcon-M, a modified version of the Falcon algorithm that significantly reduces implementation complexity. It does so by replacing Falcon’s intricate trapdoor-based key-generation mechanism with a simplified approach that utilizes randomized polynomial Gaussian sampling and fast Fourier transform (FFT) operations. Falcon-M incorporates SHA-512 hashing and discrete Gaussian sampling to preserve cryptographic soundness and statistical randomness while maintaining the core structure of Falcon’s signing and verification processes. We formally specify the Falcon-M algorithm, provide an updated pseudocode, and offer a comparative analysis with the original Falcon in terms of algorithmic complexity, security assumptions, and implementation overhead. Additionally, we present formal lemmas and theorems to ensure correctness and define theoretical bounds on forgery resistance. Although Falcon-M does not rely on a formal cryptographic trapdoor, we demonstrate that it achieves strong practical security based on assumptions related to the Short Integer Solution (SIS) problem. Falcon-M is thus well-suited for lightweight post-quantum applications, particularly in resource-constrained environments, such as embedded systems and Internet-of-Things (IoT) platforms.
A trustworthy source of randomness is a crucial component of many decentralized and crypto-based application systems, especially blockchain consensus. A decentralized random beacon (DRB) periodically outputs a new source of randomness generated using a distributed technique, such as publicly verifiable secret sharing (PVSS) or distributed verifiable random functions (VRFs). These protocols offer a variety of efficiency versus randomness quality tradeoffs, but guarantee security under a variety of configurations, assumptions, and adversarial models. This article aims to provide a future-proof unbiased decentralized randomness (abbreviated as Funder) via a post-quantum threshold VRF for sustainable proof-of-stake blockchain. We also provide a generic compiler for achieving post-quantum VRF from a classical VRF solution, but our approach makes use of symmetric-key primitives Our novel compiler is validated and evaluated using the ZKBoo and ZKB++ quantum-secure zero-knowledge systems, respectively. The implementation of the proof-of-concept demonstrates that the overheads introduced by our solution are acceptable for real-world deployments even in the present day. In addition, we demonstrate the protocol’s possible application in lottery-based proof-of-stake consensus protocols.
Quantum Random Number Generators (QRNGs) produce high-quality randomness derived from quantum phenomena, offering strong security assurances. However, relying on a single QRNG device centralizes trust and creates a single point of failure. This paper presents a decentralized architecture integrating multiple geographically distributed QRNG nodes using the Kirk network's quantum and classical channels. We incorporate Post-Quantum Verifiable Random Functions (PQ-VRFs), threshold secret sharing, and Byzantine Fault Tolerant (BFT) consensus protocols to ensure unbiased, verifiable, and tamper-resistant randomness. We detail a blockchain oracle system that transforms quantum-secure keys into various blockchain-compatible formats (Ethereum, Bitcoin, Polkadot), creating a future-proof, monetizable service for quantum-era blockchain infrastructures.