NTRU-VRF Reference Implementation

This repository contains the reference implementation and empirical validation suite for NTRU-VRF, a post-quantum verifiable random function based on the Falcon signature scheme (NTRU lattice hardness assumptions). It also includes a simulation of PQ-Sortition, a leader election protocol built on NTRU-VRF.

Overview

The codebase provides a functional prototype used to validate the theoretical claims of the NTRU-VRF construction. It wraps the liboqs C implementation of Falcon-512 to provide realistic cryptographic performance characteristics.

Critical Implementation Requirement: Deterministic Salt

Standard APIs for Falcon (such as NIST API, PQClean, and liboqs) securely inject a random salt via a system CSPRNG during signature generation to randomize the Gaussian sampling. This default behavior violates the uniqueness property required by a VRF.

To achieve the zero-equivocation guarantee required by NTRU-VRF, the underlying Falcon C implementation must be modified to derive this salt deterministically. In our validation environment, the randombytes() calls inside pqclean_falcon-512_clean were replaced with deterministic extraction using inner_shake256, seeded by the concatenation of the secret key and the input message: SHAKE256(sk || message). All benchmarks and uniqueness tests below assume this modified deterministic behavior.

Directory Structure

• ntru_vrf.py: Core logic for VRF key generation, evaluation, and verification.
• pq_sortition.py: Blockchain sortition simulator demonstrating proportional win rates and zero bias.
• tests/: Comprehensive test suite verifying uniqueness, pseudorandomness, and correctness.
• benchmarks/run_all.py: Master benchmarking script to generate empirical data.
• run_tests.py: Quick start script to run all tests and benchmarks.

Dependencies

• Python 3.10+
• liboqs-python (with underlying liboqs binaries)
• numpy, scipy (for statistical tests)

Empirical Results

The following metrics were generated on an Intel Core CPU running Windows 10, single-threaded, using the deterministic Falcon-512 modification.

Performance

• Key Generation: 18.3 ms
• Evaluation (Sign + SHA3): 0.67 ms
• Verification (Verify + SHA3): 0.17 ms
• Verification Throughput: Approx. 6000 ops/sec

Sizes

• VRF Output: 32 bytes (SHA3-256)
• Maximum Proof Size: 662 bytes
• Mean Proof Size: 655.2 bytes
• Public Key: 897 bytes
• Secret Key: 1281 bytes

Statistical Validation

• Uniqueness: 0 violations over 10,000 iterations (deterministic mode).
• Bit Frequency: 0.49918 (Ideal: 0.5).
• Avalanche Effect: 128.2 bits changed per 1-bit input flip (Ideal: 128).
• Sortition Bias: 0.0748 maximum deviation from expected proportional stake across 500 slots.