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.

SchemeAssumptionPublic keySignatureVerify time
Dilithium3MLWE1952 B3309 B~35 µs
Falcon-512NTRU897 B666 B~20 µs
SPHINCS+-128fHash32 B17088 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.

ComponentSignature schemeVerification location
TransactionsDilithium3Mempool + block validation
Wallet authenticationDilithium3Relying party
DID operationsDilithium3Crest store write
Verifiable credentialsDilithium3Presentation verification
DWN recordsDilithium3Storage acceptance
Proof worker attestationsDilithium3Batch-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.