sp1-ntt-gadget

High-performance NTT/INTT implementation for Dilithium (ML-DSA-65) verification in SP1 zkVM with 60-bit soundness.

Features

• 🔐 CRYSTALS-Dilithium Compatible: 100% compatible with FIPS 204 (ML-DSA-65) parameters
• ⚡ Optimized Montgomery Arithmetic: Constant-time operations for side-channel resistance
• 🛡️ 60-bit Soundness: Polynomial Identity Check (PIC) with Fiat-Shamir challenges
• 🔧 SP1 zkVM Ready: Native integration with SP1 precompile syscalls
• 📦 no_std Compatible: Works in embedded and zkVM environments

Quick Start

Add to your Cargo.toml:

[dependencies]
sp1-ntt-gadget = "0.1"

Basic NTT/INTT

use sp1_ntt_gadget::{ntt::forward::ntt, ntt::inverse::intt, params::N};

fn main() {
    // 256 coefficients in Z_q (q = 8,380,417)
    let mut coeffs = [0u32; N];
    coeffs[0] = 42;
    coeffs[1] = 59;

    // Forward NTT
    let original = coeffs;
    ntt(&mut coeffs);

    // Inverse NTT (roundtrip)
    intt(&mut coeffs);

    assert_eq!(coeffs, original);
}

Verified NTT (with PIC)

use sp1_ntt_gadget::{
    ntt::forward::ntt,
    pic::verifier::verify_ntt_simple,
    params::N,
};

fn main() {
    let mut coeffs = [0u32; N];
    for i in 0..N {
        coeffs[i] = (i as u32 * 12345) % 8_380_417;
    }

    let original = coeffs;
    ntt(&mut coeffs);

    // Verify NTT correctness (60-bit soundness)
    let context = b"my-application-context";
    assert!(verify_ntt_simple(&original, &coeffs, context).is_ok());
}

SP1 Precompile Integration

use sp1_ntt_gadget::precompile::sp1_hook::{
    NttInput, execute_ntt_with_verification
};

fn main() {
    let input = NttInput {
        coefficients: [42u32; 256],
        context: *b"sp1-ntt-gadget-context-v1\0\0\0\0\0\0\0",
    };

    let output = execute_ntt_with_verification(&input);

    assert!(output.verified);
    println!("NTT output: {:?}", &output.ntt_coefficients[..4]);
}

Parameters

Modules

Performance

Native Benchmarks (Apple M1)

SP1 Network Proof (Groth16)

Testing

# Run all tests (104 tests)
cargo test

# Run with specific test suite
cargo test --test ntt_gate1      # Gate 1: NTT correctness
cargo test --test pic_gate2      # Gate 2: PIC soundness
cargo test --test fuzz_ntt       # Fuzzing (100k+ iterations)

Security

• Soundness: 60-bit (NUM_CHALLENGES=4, each with ~15-bit security)
• Side-channel Resistance: Constant-time Montgomery arithmetic
• Tested: 132,731+ fuzzing iterations, 104 unit tests

References

• FIPS 204 (ML-DSA) Specification
• CRYSTALS-Dilithium Reference
• SP1 zkVM Documentation

License

MIT License - see LICENSE-MIT for details.

Contributing

Contributions welcome! Please open an issue or PR.

Part of the PQ Wallet project - Post-Quantum Cryptography for Web3