Dilithium
CRYSTALS-Dilithium3 — the post-quantum signature scheme used for every transaction, every DID operation, and every credential attestation in Sahyadri. Security rests on the Module-Learning-With-Errors problem, which no known classical or quantum algorithm solves in polynomial time.
1. Formal Definition
A signature scheme is a triple of algorithms. Dilithium3 instantiates this triple over module-lattice arithmetic, with security resting on the hardness of MLWE.
Definition 1.1 (Signature scheme)
A signature scheme is (KeyGen, Sign, Verify) where:
KeyGen(1^λ) → (pk, sk)
Sign(sk, m) → σ
Verify(pk, m, σ) → {⊤, ⊥}
satisfying:
Correctness:
∀ (pk, sk) ← KeyGen(1^λ), ∀ m:
Verify(pk, m, Sign(sk, m)) = ⊤
Existential unforgeability under chosen-message attack (EUF-CMA):
∀ PPT adversary A:
Pr[
(pk, sk) ← KeyGen(1^λ)
(m*, σ*) ← A^{Sign(sk, ·)}(pk)
: Verify(pk, m*, σ*) = ⊤ ∧ m* ∉ queried_messages
] ≤ negl(λ)Sahyadri uses Dilithium3, which achieves EUF-CMA security under the MLWE assumption in the random-oracle model. Every transaction signature in the network is a Dilithium3 signature over a SHA3-256 hash of the transaction fields.
2. The MLWE Assumption
All security of Dilithium reduces to the hardness of MLWE. The assumption is stated precisely because it is the foundation, and it is the only thing that must not be broken for the protocol to remain sound.
Definition 2.1 (Module-Learning-With-Errors)
Parameters:
n, k, ℓ ∈ ℕ (module dimensions)
q ∈ ℕ (modulus, typically prime)
R_q = ℤ_q[X]/(X^n + 1) (quotient ring)
Distribution χ: a small noise distribution over R_q.
Sample:
A ← R_q^(k × ℓ) uniform random matrix
s_1 ← χ^ℓ small secret vector
s_2 ← χ^k small noise vector
b = A · s_1 + s_2 (matrix-vector product in R_q)
MLWE problem:
Given (A, b), distinguish b = A·s_1 + s_2 from uniform.
Advantage:
Adv_MLWE(A) = | Pr[A(A, b) = 1] - Pr[A(A, u) = 1] |
where u ← R_q^k uniform.
Assumption:
∀ PPT adversary A (classical or quantum):
Adv_MLWE(A) ≤ negl(λ)MLWE is a lattice problem. Best-known attacks are algebraic (BKZ-style lattice reduction), and the parameters for Dilithium3 are chosen so that both classical and quantum algorithms require infeasible time.
Crucially, MLWE is not based on a hidden-subgroup problem. Shor's algorithm — the algorithm that breaks RSA, ECDSA, and Diffie-Hellman — solves the abelian hidden-subgroup problem. MLWE is not abelian hidden-subgroup. Shor's algorithm does not apply. No known quantum algorithm solves MLWE faster than classical best-known algorithms.
3. Dilithium3 Construction
Dilithium3 is one parameter set in the Dilithium family. The construction uses Fiat-Shamir with aborts: the signer produces a candidate signature, hashes it to derive a challenge, and aborts (retries with fresh randomness) if the challenge would leak information about the secret.
KeyGen(1^λ) → (pk, sk):
A ← R_q^(k × ℓ) (derived from public seed ρ)
s_1 ← χ^ℓ, s_2 ← χ^k (small secret vectors)
t = A · s_1 + s_2
pk = (ρ, t) (matrix seed + result vector)
sk = (ρ, t, s_1, s_2) (public data + secret vectors)
Sign(sk, m) → σ:
μ = H(tr ‖ m) (message digest with public seed hash)
κ ← {0,1}^256 (per-signature randomness)
y ← Expand(κ) (candidate nonce, uniform over R_q^ℓ)
w = A · y
c = H(μ ‖ w) (challenge, small polynomial)
z = y + c · s_1
// Rejection sampling — abort if z too large
if ||z||_∞ > γ_1: return ⊥ (retry with fresh κ)
// Abort if challenge-dependent hash leaks
if H(μ ‖ w - c · s_2) ≠ c: return ⊥
σ = (z, c)
Verify(pk, m, σ) → {⊤, ⊥}:
μ = H(tr ‖ m)
w' = A · z - c · t
c' = H(μ ‖ w')
return (c' = c) ∧ (||z||_∞ ≤ γ_1)The rejection-sampling structure is what makes the signature security analysis go through. Each signing attempt has a ~1/5 chance of being rejected (for Dilithium3 parameters); the signer loops until a non-rejected attempt succeeds. Expected number of iterations is 4-5.
4. NIST Standardization
Dilithium was selected by NIST in the post-quantum cryptography standardization competition and published as FIPS 204 in August 2024. The three Dilithium parameter sets — Dilithium2, Dilithium3, Dilithium5 — correspond to NIST security levels 2, 3, and 5.
Timeline: 2016 NIST initiates PQC standardization 2017-2018 Round 1 candidates submitted (~70 in total) 2019 Round 2 (26 candidates) 2020 Round 3 (7 finalist candidates for signatures) 2022 Dilithium selected as one of two KEM/SIG standards 2024.08 FIPS 204 published — CRYSTALS-Dilithium official NIST security levels (2024 definition): Level 1: ~128-bit classical, ~AES-128 equivalent Level 2: ~192-bit classical, SHA3-256 collision equivalent Level 3: ~192-bit classical, AES-192 equivalent Level 5: ~256-bit classical, AES-256 equivalent Note on interpretation: NIST's "Level 2" is the weakest threshold — it corresponds to the security level of SHA3-256 collision resistance (128-bit classical, 2^128 operations to find a collision). "Level 3" (Sahyadri's choice) is roughly the same security margin against classical adversaries as AES-192. This is substantially stronger than Level 2 and is the recommended level for long-lived cryptographic systems. Sahyadri chose Level 3 rather than Level 2 because the protocol is designed for multi-decade operation. The performance overhead of Level 3 over Level 2 is small (~10-15% on signature verification), while the security margin is meaningfully larger.
5. Parameter Sizes
Dilithium3 key and signature sizes are larger than ECDSA's. The cost is a consequence of the underlying lattice structure: secure lattices require vectors of significant dimension, and the signature is a pair of small polynomials whose aggregate size is large.
Dilithium3 sizes (from FIPS 204):
Public key: 1952 bytes
Secret key: 4032 bytes
Signature: 3309 bytes
Comparison with ECDSA (secp256k1):
Public key: 33 bytes (33× smaller)
Secret key: 32 bytes (126× smaller)
Signature: 72 bytes (46× smaller)
Aggregate per-transaction wire cost:
Dilithium3 transaction: ~5261 bytes
- 1952 public key
- 3309 signature
- transaction fields
ECDSA transaction: ~200 bytes
Factor: Dilithium3 is ~26× larger per transaction.At 10,000 TPS, Dilithium3 signatures alone are ~33 MB/s of network bandwidth. This is why Sahyadri implements AVX2 SIMD and Rayon parallel verification — without hardware-accelerated verification, the verification cost at that throughput would be prohibitive.
6. Signature Verification Cost
Dilithium3 verification is the expensive part. Verification is substantially cheaper than signing (no rejection loop), but still substantial compared to ECDSA.
Measured verification time (single core, AVX2): Device Verify time Signature throughput ───────────────── ─────────── ──────────────────── Modern desktop CPU ~35 µs ~28,500 sig/s Mid-range laptop ~60 µs ~16,600 sig/s Server CPU (Xeon) ~30 µs ~33,300 sig/s Parallel verification (Rayon, 16 cores): Modern desktop ~5 µs/sig ~200,000 sig/s Server CPU ~4 µs/sig ~250,000 sig/s Context for Sahyadri: Target block throughput: 10,000 TPS Signature verify budget: 5,000 sig / block at 1 BPS Single-core capacity: ~28,500 sig/s (exceeds target by 3×) Parallel (16 core): ~200,000 sig/s (20× headroom)
7. Where Dilithium3 Appears
Every signature in Sahyadri is Dilithium3. There is no ECDSA anywhere in the trust path. The algorithm secures five distinct signature categories in the current codebase.
Signature category What it authorizes Flash transaction Transfer of CSM from one account to another Code: consensus/core/src/tx.rs::FlashTransaction::sighash() Input: FLASH_V1 fields + salt Verify: at mempool and at block validation DID operation Create, update, or deactivate a DID Code: crest-model handlers Input: DID document fields + operation type Verify: at Crest store write Credential issuance Sign a verifiable credential Code: verifiable-credentials handlers Input: credential payload + holder DID Verify: at presentation time DWN record Write or update a Decentralized Web Node record Code: DWN handler Input: record fields + controller DID Verify: at storage acceptance Wallet authentication Prove ownership of a Sahyadri address Code: wallet SDK Input: challenge message + address Verify: at relying party
All five categories use the same signing and verification path. There is no separate code path for DIDs or credentials — the primitive is one, and all applications compose it.
8. Why Not ECDSA or EdDSA
ECDSA and EdDSA are secure against classical adversaries under the hardness of the elliptic curve discrete logarithm problem. Both are broken by Shor's algorithm on a sufficiently large quantum computer.
Shor's algorithm:
Given: (G, g, g·x) where G is an abelian group, g is a
generator, x is a scalar.
Finds: x in polynomial time on a quantum computer.
Applies to:
- ECDSA: group is the elliptic curve group mod p.
- EdDSA: same structure (Edwards form).
- RSA: group is the multiplicative group mod N.
- DH: group is the multiplicative group mod p.
Does NOT apply to:
- Lattice problems (MLWE, MSIS, SIS)
- Hash functions (SHA3, Poseidon2)
- Code-based cryptography (McEliece)
Migration cost:
A chain that used ECDSA would need to:
1. Introduce a new signature scheme
2. Support both during a transition period
3. Encourage users to migrate
4. Eventually reject the old scheme
The transition period is when the chain is most vulnerable —
users have both keys, and the attacker can target either.
Sahyadri's choice:
Use Dilithium3 from genesis. No migration period.
No transition window. No exposed old keys.9. Dilithium3 vs Other Post-Quantum Schemes
NIST selected two other signature schemes alongside Dilithium: Falcon (fast, compact, but complex and hard to implement in constant time) and SPHINCS+ (hash-based, largest signatures, strongest trust assumptions). Sahyadri's choice of Dilithium3 follows from protocol-specific requirements.
| Scheme | Assumption | Public key | Signature | Verify time |
|---|---|---|---|---|
| Dilithium3 | MLWE | 1952 B | 3309 B | ~35 µs |
| Falcon-512 | NTRU | 897 B | 666 B | ~20 µs |
| SPHINCS+-128f | Hash | 32 B | 17088 B | ~1000 µs |
Falcon has smaller signatures and faster verification, but constant-time implementation is difficult and the reference implementation has known timing-side-channel concerns. Sahyadri does not use Falcon because constant-time correctness is a hard requirement for a public protocol — a single timing leak in the signature implementation would be exploited before the network noticed.
SPHINCS+ has the strongest trust assumptions (only requires hash collision resistance), but its signatures are 5× larger and its verification is 30× slower. At 10,000 TPS, SPHINCS+ would be infeasible without dedicated hardware.
Dilithium3 sits in the middle: larger signatures than Falcon, smaller than SPHINCS+, straightforward constant-time implementation, and well-understood lattice parameter selection.
10. Security Reduction
The security of Dilithium3 reduces to MLWE plus the Fiat-Shamir transform plus a few supporting primitives. This is what a formal security claim looks like.
Theorem 10.1 (Dilithium3 EUF-CMA security)
For any PPT adversary A making at most q_S signing queries
and q_H hash queries to the random oracle:
Adv_EUF-CMA_Dilithium3(A) ≤
Adv_MLWE(A')
+ Adv_SelfTargetMSIS(A'')
+ q_S · q_H / 2^λ
where A' and A'' are PPT adversaries with runtime approximately
that of A, and λ is the security parameter.
Interpretation:
- If MLWE is hard, and SelfTargetMSIS is hard, and the hash
is modelled as a random oracle, then Dilithium3 is EUF-CMA
secure.
- The λ bound on q_S · q_H / 2^λ prevents a birthday-style
collision attack on the Fiat-Shamir challenge.
For Sahyadri with λ = 192 (Level 3):
A successful forgery requires either:
- Breaking MLWE (infeasible classically and quantumly)
- Breaking SelfTargetMSIS (infeasible)
- Finding a hash collision with probability > 2^-192 (infeasible)11. Quantum Threat Model
What a quantum adversary can and cannot do against Dilithium3.
Attack class Classical Quantum Effect on Dilithium3
──────────────────────── ──────────── ──────────── ─────────────────────
Discrete log (Shor) infeasible polynomial no effect (not EC-based)
Integer factoring (Shor) infeasible polynomial no effect (not RSA)
Lattice reduction (BKZ) exponential poly-reduced Dilithium uses parameters
resistant to quantum BKZ
Grover preimage exponential 2^λ/2 Dilithium signatures
retain ~192-bit classical
security under Grover
Grover collision exponential 2^λ/4 hash functions in
Dilithium use 256-bit
outputs with 128-bit
classical collision bound
Result:
No known quantum algorithm reduces Dilithium3's security below
an infeasible threshold. The scheme is post-quantum in the
precise sense that no quantum attack is known.12. Applications in Sahyadri
Every signed operation in Sahyadri uses Dilithium3. The algorithm is not a side mechanism — it is the primary signature scheme for every category of signed data.
| Component | Signature scheme | Verification location |
|---|---|---|
| Transactions | Dilithium3 | Mempool + block validation |
| Wallet authentication | Dilithium3 | Relying party |
| DID operations | Dilithium3 | Crest store write |
| Verifiable credentials | Dilithium3 | Presentation verification |
| DWN records | Dilithium3 | Storage acceptance |
| Proof worker attestations | Dilithium3 | Batch-STARK verification |
The proof worker attestation is notable. Every transaction's Dilithium3 signature is verified inside a STARK, which produces a batch proof attesting to all signatures in the block. The signature verification cost at the protocol level is amortized across the batch: 35 ms per batch of 2-8 signatures, not 35 ms per signature.
13. Implementations and Constant-Time Concerns
A signature scheme is only as secure as its implementation. Side channels — timing, power, cache — can leak the private key even if the scheme itself is secure. This is why Sahyadri uses the Rust implementation from the dilithium-rs crate, which is designed for constant-time execution.
Constant-time properties (from dilithium-rs):
- No data-dependent branches in signing loop
- No data-dependent memory access patterns
- Fixed iteration count for rejection loop (or abort with
bounded retry — no unbounded timing)
- Comparison routines use constant-time equality
Known timing side channels (research-level):
- Falcon has documented timing side channels in the floating-point
fast Fourier transform used in signing.
- Dilithium does not use floating point; integer arithmetic only.
Sahyadri's choice of Dilithium over Falcon is partly driven by this:
Falcon's floating-point FFT is difficult to implement in constant
time, and the timing leak can be exploited to recover the private
key over many signatures.
Dilithium's integer-only arithmetic is easier to constant-time,
and the reference Rust implementation achieves it.14. Limitations
Limitation 14.1: Larger wire footprint
Dilithium3 signatures are 3309 bytes, versus 72 bytes for
ECDSA. A transaction carries ~5 KB of signature data instead
of ~200 bytes.
This costs bandwidth and disk. At 10,000 TPS, the network
transmits ~33 MB/s of signature data alone.
Limitation 14.2: Slower verification
Dilithium3 verify is ~35 µs per signature, versus ~20 µs for
ECDSA. At 10,000 TPS, verification requires parallel execution.
Sahyadri uses AVX2 SIMD and Rayon parallel verification to
meet the throughput target. Without these optimizations, the
network would not achieve 10,000 TPS on commodity hardware.
Limitation 14.3: Lattice parameter evolution
The MLWE parameters in Dilithium3 (n=256, q=8380417, k=6,
ℓ=5 for Level 3) are fixed for the current NIST standard.
If future cryptanalysis suggests these parameters are weaker
than estimated, a migration to Dilithium5 or a successor
scheme would be required.
No such cryptanalysis is known today. The parameters have
survived 8 years of public analysis.
Limitation 14.4: Post-quantum is a hedge
MLWE is believed secure against both classical and quantum
attacks. It is not proven secure. A mathematical breakthrough
in lattice reduction could break it.
Sahyadri accepts this risk. The alternative — elliptic curves —
has a known quantum break. Lattice problems have no known
classical or quantum break. Between the two, MLWE is the
strictly stronger assumption.
Limitation 14.5: Signature aggregation is protocol-level, not
scheme-level
Multiple Dilithium3 signatures are aggregated in Sahyadri via
a batch-STARK proof, not via a signature-level aggregate.
True signature aggregation (a scheme where n signatures can
be compressed into one short signature) is not provided by
Dilithium3. Sahyadri's aggregation is: prove in a STARK that
each signature verifies, and aggregate the proofs.
This works, but the batch proof is larger than a hypothetical
true aggregate would be.15. Summary
Dilithium3 is the post-quantum signature scheme used for every signed operation in Sahyadri. Security reduces to MLWE, which no known classical or quantum algorithm solves in polynomial time. The scheme is NIST-standardized (FIPS 204), well-analyzed, and has a straightforward constant-time implementation in Rust.
The cost is significant: 1952-byte public keys, 3309-byte signatures, ~35 µs verification. These are 30-50× larger and ~1.7× slower than ECDSA. The cost is accepted because the alternative — elliptic-curve signatures that Shor's algorithm breaks — carries a known-quantum risk that Sahyadri is designed to eliminate.
Every transaction, every DID, every credential, every DWN record, every wallet authentication uses the same signature scheme. There is no legacy path, no transition, no second algorithm. The protocol made a specific cryptographic choice at genesis, and the cost of that choice — in bandwidth, storage, and verification time — is the price of post-quantum security from the first block.