Dilithium Cryptography

This page provides a technical deep-dive into the cryptographic foundations of Dilithium, the post-quantum signature scheme used by BTQ Core.

CRYSTALS-Dilithium

Dilithium is part of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) family, which also includes the Kyber key encapsulation mechanism. It was selected by NIST as the primary post-quantum signature standard.

Design Goals

1. Quantum Resistance: Secure against both classical and quantum adversaries
2. Efficiency: Fast signing and verification
3. Small Signatures: Compact compared to other post-quantum schemes
4. Simplicity: Based on well-studied lattice problems

Mathematical Foundation

Module Learning with Errors (MLWE)

Dilithium's security is based on the Module Learning with Errors (MLWE) problem:

Given a random matrix A in R_q^(k x l) and vectors:

• s in R_q^l (secret)
• e in R_q^k (small error)

The MLWE problem asks to distinguish between:

1. (A, As + e) - MLWE sample
2. (A, u) - uniformly random

Where R_q = Z_q[X]/(X^n + 1) is the polynomial ring.

Why MLWE is Hard

• Classical hardness: Reducible to worst-case lattice problems (LWE)
• Quantum hardness: No known polynomial-time quantum algorithm
• Conservative parameters: Dilithium uses parameters with large security margins

Dilithium2 Parameters

BTQ uses Dilithium2 (NIST Security Level 2):

Resulting Sizes

Key Generation

KeyGen():
1. A <- Expand(rho)           // Generate matrix from seed rho
2. (s1, s2) <- Sample(rho')   // Sample secret vectors
3. t := As1 + s2              // Compute public key component
4. (t1, t0) := Power2Round(t)
5. pk := (rho, t1)
6. sk := (rho, K, tr, s1, s2, t0)
7. return (pk, sk)

Where:

• rho is a 256-bit seed for matrix generation
• K is a 256-bit seed for signing
• tr is a hash of the public key
• t1 is the high-order bits of t

Signing Algorithm

Sign(sk, M):
1. A := Expand(rho)
2. mu := CRH(tr || M)         // Hash message with public key binding
3. kappa := 0
4. (z, h) := null
5. while (z, h) = null:
   a. y <- ExpandMask(K, kappa)   // Generate masking vector
   b. w := Ay
   c. w1 := HighBits(w)
   d. c := H(mu || w1)            // Challenge
   e. z := y + c*s1               // Response
   f. (r0, r1) := Decompose(w - c*s2)
   g. if ||z||_inf >= gamma1 - beta or ||r0||_inf >= gamma2 - beta:
      kappa++; continue           // Rejection sampling
   h. h := MakeHint(w - c*s2 + c*t0, w - c*s2)
   i. if ||c*t0||_inf >= gamma2 or count(h) > omega:
      kappa++; continue
6. return sigma := (c_tilde, z, h)

Rejection Sampling

The while loop implements rejection sampling to ensure signatures don't leak information about the secret key. This is crucial for security.

Verification Algorithm

Verify(pk, M, sigma):
1. A := Expand(rho)
2. mu := CRH(tr || M)
3. c := SampleInBall(c_tilde)
4. w1_prime := UseHint(h, Az - c*t1 * 2^d)
5. return ||z||_inf < gamma1 - beta and c_tilde = H(mu || w1_prime)

Verification is simpler than signing:

1. Reconstruct the commitment w1_prime using the hint
2. Recompute the challenge hash
3. Check that it matches and bounds are satisfied

Security Levels

BTQ uses Dilithium2, providing security equivalent to AES-128.

Implementation in BTQ

C Wrapper

BTQ uses a C wrapper to isolate Dilithium's C implementation from the C++ codebase:

// dilithium_wrapper.h
int dilithium_keypair(unsigned char *pk, unsigned char *sk);
int dilithium_sign(unsigned char *sig, size_t *siglen,
                   const unsigned char *m, size_t mlen,
                   const unsigned char *sk);
int dilithium_verify(const unsigned char *sig, size_t siglen,
                     const unsigned char *m, size_t mlen,
                     const unsigned char *pk);

C++ Classes

class CDilithiumKey {
private:
    std::vector<unsigned char> keydata;  // 2,560 bytes
    
public:
    void MakeNewKey();
    bool Sign(const uint256& hash, std::vector<unsigned char>& sig);
    CDilithiumPubKey GetPubKey() const;
    bool IsValid() const;
};

class CDilithiumPubKey {
private:
    std::vector<unsigned char> keydata;  // 1,312 bytes
    
public:
    bool Verify(const uint256& hash, const std::vector<unsigned char>& sig);
    CKeyID GetID() const;  // RIPEMD160(SHA256(pubkey))
    size_t size() const { return 1312; }
};

Comparison with Other Schemes

Why Dilithium over Falcon?

• Simpler implementation (no floating-point arithmetic)
• Easier to implement securely
• Better side-channel resistance
• NIST primary recommendation

Why Not SPHINCS+?

• Much larger signatures (7.8KB vs 2.4KB)
• Slower signing
• Hash-based (different security assumptions)

Quantum Attacks

Grover's Algorithm

Grover's algorithm provides quadratic speedup for searching:

• Classical: O(N) to find target in N items
• Quantum: O(sqrt(N))

Impact: Effectively halves key security bits

• 256-bit classical becomes 128-bit quantum

Shor's Algorithm

Shor's algorithm breaks:

• RSA (factoring)
• ECDSA (discrete log)
• DH key exchange

Impact: Complete break in polynomial time

Dilithium's defense: Based on MLWE, not affected by Shor's algorithm

Hash Functions

Dilithium uses several hash functions internally:

All based on SHAKE (SHA-3 family), providing quantum resistance.

Random Number Generation

Key generation requires secure randomness:

void CDilithiumKey::MakeNewKey() {
    // Use BTQ's secure RNG (same as Bitcoin)
    GetStrongRandBytes(seed, 32);
    
    // Generate keypair
    dilithium_keypair_from_seed(pubkey, seckey, seed);
    
    // Clear seed
    memory_cleanse(seed, 32);
}

Side-Channel Considerations

Timing Attacks

The reference implementation includes protections:

• Constant-time polynomial operations
• Rejection sampling independent of secret

Memory Access Patterns

• Avoid secret-dependent branches
• Avoid secret-dependent memory access

Power Analysis

Hardware implementations need additional protections (masking, shuffling).

Future Work

1. Dilithium3/5: Higher security levels for critical applications
2. Hybrid Signatures: Combine with ECDSA for defense-in-depth
3. HD Derivation: Hierarchical deterministic key derivation for Dilithium
4. Hardware Acceleration: Optimized implementations for specific platforms

References

• CRYSTALS-Dilithium Specification
• NIST FIPS 204
• Dilithium Security Analysis
• NIST Post-Quantum Cryptography Project