Comprehensive Explanation

post-quantum

Technical Definition

Post-quantum cryptography (also called quantum-proof, quantum-safe, or quantum-resistant cryptography) encompasses cryptographic algorithms—primarily public-key algorithms—that are designed to remain secure against cryptanalytic attacks performed by quantum computers. In the context of KERI, post-quantum security is achieved not through the use of specialized post-quantum cryptographic primitives for individual key pairs, but rather through the protocol's innovative pre-rotation mechanism.

Formal Definition

A cryptographic system is considered post-quantum secure if it maintains its security properties even when an adversary has access to a large-scale quantum computer capable of running Shor's algorithm (for factoring and discrete logarithm problems) and Grover's algorithm (for symmetric key search). The security level is typically measured in "quantum bits" of security, where n quantum bits of security requires approximately 2^n quantum operations to break.

Purpose in KERI/ACDC

KERI's approach to post-quantum security addresses a fundamental vulnerability in traditional PKI systems: the ability of quantum computers to break current public-key cryptography schemes (RSA, ECDSA, etc.) through Shor's algorithm. Rather than requiring immediate adoption of post-quantum cryptographic algorithms (which are still maturing), KERI provides quantum resistance through its temporal security model based on proactive key rotation.

Type Classification

In KERI's architecture, post-quantum security is a protocol-level property rather than a primitive-level property. This distinguishes it from approaches that rely on quantum-resistant cryptographic algorithms like:

• Lattice-based cryptography (e.g., CRYSTALS-Kyber, CRYSTALS-Dilithium)
• Hash-based signatures (e.g., SPHINCS+, XMSS)
• Code-based cryptography (e.g., Classic McEliece)
• Multivariate cryptography
• Isogeny-based cryptography

KERI's post-quantum security instead leverages the one-way property of cryptographic hash functions, which remain secure against quantum attacks (requiring only a doubling of hash output size to maintain equivalent security).

Cryptographic Properties

The Pre-Rotation Mechanism

KERI achieves post-quantum security through its pre-rotation scheme, which works as follows:

1. Cryptographic Commitment: Each establishment event (inception or rotation) includes a cryptographic digest of the next set of public keys that will be used in the subsequent rotation
2. One-Time Use: These pre-rotated keys are used exactly once—only for the next rotation event
3. Hidden Keys: The actual public keys remain hidden until the rotation event occurs; only their cryptographic digests are exposed
4. Forward Security: Compromise of current signing keys does not compromise the pre-rotated keys, as they are cryptographically hidden behind one-way hash functions

Security Against Quantum Attacks

The quantum resistance of KERI's pre-rotation mechanism relies on several key properties:

Hash Function Security: Cryptographic hash functions like Blake3, SHA-256, and SHA-512 maintain their security properties against quantum computers. While Grover's algorithm provides a quadratic speedup for preimage attacks, this only requires doubling the hash output size (e.g., from 128-bit to 256-bit security) to maintain equivalent security levels.

Temporal Advantage: The security model assumes that keys are rotated before a quantum computer can successfully attack them. As stated in the source documents: "keys are rotated before a brute force quantum attack can be effective." This creates a race condition where the defender (through proactive rotation) stays ahead of the attacker.

Adaptive Security Parameters: As quantum computing technology advances, KERI systems can respond by:

• Shortening rotation intervals: Reducing the time window during which keys are exposed
• Increasing entropy: Using higher-entropy sources for key generation (e.g., moving from 128-bit to 256-bit or higher)
• Upgrading hash functions: Transitioning to stronger hash algorithms as needed

Cryptographic Strength Requirements

KERI's post-quantum security model requires:

• Minimum 128 bits of entropy for key generation (256 bits recommended for long-term security)
• Collision-resistant hash functions with at least 256-bit output (512-bit for conservative deployments)
• CSPRNG (Cryptographically Secure Pseudo-Random Number Generator) for key generation
• One-way functions with computational infeasibility of inversion (approximately 2^128 operations minimum)

Bernstein's Cost Analysis

The theoretical foundation for KERI's post-quantum approach draws on Daniel J. Bernstein's research on the cost of collision attacks. Key findings include:

1. Quantum computers provide no advantage for collision search compared to classical computers
2. Hash collision attacks remain inefficient on quantum computers
3. Factorization and discrete logarithm problems (used in RSA and ECC) are vulnerable to quantum attacks via Shor's algorithm
4. Hash-based commitments maintain their security properties in a post-quantum world

This asymmetry—where signing algorithms are vulnerable but hash functions remain secure—forms the basis for KERI's pre-rotation strategy.

Data Format & Encoding

Pre-Rotation Digest Representation

In KERI, post-quantum security is implemented through the next key digest field in establishment events. These digests are encoded using CESR (Composable Event Streaming Representation) with specific derivation codes.

CESR Encoding Format

Pre-rotated key digests appear in the n field of establishment events:

Single Next Key (Basic Format):

{
  "v": "KERI10JSON00011c_",
  "t": "icp",
  "d": "EL1L56LyoKrIofnn0oPChS4EyzMHEEk75INJohDS_Bug",
  "i": "EL1L56LyoKrIofnn0oPChS4EyzMHEEk75INJohDS_Bug",
  "s": "0",
  "kt": "1",
  "k": ["DL1L56LyoKrIofnn0oPChS4EyzMHEEk75INJohDS_Bug"],
  "nt": "1",
  "n": ["ETNZH3ULvYawyZ-i0d8JZU6JR2nmAoAfSVPzhzS6b5CM"],
  "bt": "0",
  "b": [],
  "c": [],
  "a": []
}

Multiple Next Keys (Multi-sig Format):

{
  "n": [
    "ETNZH3ULvYawyZ-i0d8JZU6JR2nmAoAfSVPzhzS6b5CM",
    "EYAfSVPzhzaU6JR2nmoTNZH3ULvwyZb6b5CMi0d8JZAS",
    "EnmwyZdi0d8JZAoTNZYAfSVPzhzaU6JR2H3ULvS6b5CM"
  ]
}

Derivation Codes for Hash Digests

CESR uses specific derivation codes to indicate the hash algorithm used for next key digests:

• E: Blake3-256 digest (44 characters total in Base64)
• F: Blake2b-256 digest (44 characters total)
• G: Blake2s-256 digest (44 characters total)
• H: SHA3-256 digest (44 characters total)
• I: SHA2-256 digest (44 characters total)

The choice of hash algorithm affects the quantum security level:

• 256-bit hashes: Provide 128 bits of quantum security (sufficient for most applications)
• 512-bit hashes: Provide 256 bits of quantum security (recommended for high-security applications)

Text and Binary Representations

Text Domain (Base64 URL-safe):

ETNZH3ULvYawyZ-i0d8JZU6JR2nmAoAfSVPzhzS6b5CM

Binary Domain (raw bytes):

0x13 0x35 0x87 0xDD 0x42 0xEF 0x61 0xAC 0x32 0x67 0xE8 0xB4 0x77 0xC2 0x49 0x53
0xA2 0x51 0xD8 0x79 0x80 0x20 0x1F 0x49 0x53 0xF3 0x87 0x34 0xBA 0x6F 0x90 0xC8

Raw Domain (code, raw) tuple:

("E", <32-byte Blake3-256 digest>)

Usage in KERI/ACDC

In Establishment Events

Post-quantum security through pre-rotation is implemented in two types of establishment events:

1. Inception Events (icp):

The inception event creates an AID and establishes the initial key state, including the first pre-rotated key commitment:

{
  "v": "KERI10JSON00011c_",
  "t": "icp",
  "d": "EL1L56LyoKrIofnn0oPChS4EyzMHEEk75INJohDS_Bug",
  "i": "EL1L56LyoKrIofnn0oPChS4EyzMHEEk75INJohDS_Bug",
  "s": "0",
  "kt": "1",
  "k": ["DL1L56LyoKrIofnn0oPChS4EyzMHEEk75INJohDS_Bug"],
  "nt": "1",
  "n": ["ETNZH3ULvYawyZ-i0d8JZU6JR2nmAoAfSVPzhzS6b5CM"],
  "bt": "0",
  "b": [],
  "c": [],
  "a": []
}

Key fields for post-quantum security:

• k: Current signing keys (exposed)
• n: Next key digests (quantum-protected through one-way hash)
• nt: Next threshold (number of signatures required from next keys)

2. Rotation Events (rot):

Rotation events change the key state and establish new pre-rotated commitments:

{
  "v": "KERI10JSON00011c_",
  "t": "rot",
  "d": "E0d8JZU6JR2nmAoAfSVPzhzS6b5CMTNZH3ULvYawyZ-i",
  "i": "EL1L56LyoKrIofnn0oPChS4EyzMHEEk75INJohDS_Bug",
  "s": "1",
  "p": "EL1L56LyoKrIofnn0oPChS4EyzMHEEk75INJohDS_Bug",
  "kt": "1",
  "k": ["DTNZH3ULvYawyZ-i0d8JZU6JR2nmAoAfSVPzhzS6b5CM"],
  "nt": "1",
  "n": ["EYAfSVPzhzaU6JR2nmoTNZH3ULvwyZb6b5CMi0d8JZAS"],
  "bt": "0",
  "br": [],
  "ba": [],
  "a": []
}

Key fields:

• p: Prior event digest (backward chaining)
• k: New current keys (previously committed in prior event's n field)
• n: New next key digests (quantum-protected commitment to future keys)

Common Usage Patterns

Pattern 1: Proactive Rotation Schedule

Organizations implement scheduled key rotations to maintain quantum security:

Time T0: Inception with keys K0, commit to digest(K1)
Time T1: Rotate to K1, commit to digest(K2)
Time T2: Rotate to K2, commit to digest(K3)
...

Rotation frequency depends on:

• Threat assessment: Higher-value identifiers rotate more frequently
• Quantum computing progress: Rotation intervals shorten as quantum capabilities advance
• Operational constraints: Balance security with operational overhead

Pattern 2: Compromise Recovery

If current signing keys (K0) are compromised, the controller can still recover control using the pre-rotated keys (K1) that were never exposed:

1. Attacker compromises K0
2. Controller detects compromise
3. Controller uses K1 (which attacker doesn't have) to rotate to K2
4. Attacker's K0 is now useless

This recovery mechanism works because:

• K1 was never exposed (only digest(K1) was public)
• Quantum computers cannot efficiently invert hash functions
• The attacker cannot derive K1 from digest(K1)

Pattern 3: Multi-Signature Quantum Security

For multi-sig AIDs, post-quantum security scales with the number of signers:

{
  "kt": "2",
  "k": [
    "DL1L56LyoKrIofnn0oPChS4EyzMHEEk75INJohDS_Bug",
    "DTNZH3ULvYawyZ-i0d8JZU6JR2nmAoAfSVPzhzS6b5CM",
    "DYAfSVPzhzaU6JR2nmoTNZH3ULvwyZb6b5CMi0d8JZAS"
  ],
  "nt": "2",
  "n": [
    "ETNZH3ULvYawyZ-i0d8JZU6JR2nmAoAfSVPzhzS6b5CM",
    "EYAfSVPzhzaU6JR2nmoTNZH3ULvwyZb6b5CMi0d8JZAS",
    "EnmwyZdi0d8JZAoTNZYAfSVPzhzaU6JR2H3ULvS6b5CM"
  ]
}

An attacker would need to:

1. Compromise at least 2 of 3 current keys (K0)
2. Quantum-attack at least 2 of 3 next key digests (computationally infeasible)
3. Complete both attacks before the next rotation (temporal constraint)

This creates exponential security scaling where each additional signer multiplies the attack difficulty.

Verification Procedures

Verifying Pre-Rotation Commitments:

1. Extract next key digest from prior establishment event:

   prior_event.n[i] = "ETNZH3ULvYawyZ-i0d8JZU6JR2nmAoAfSVPzhzS6b5CM"
   

2. Extract current key from rotation event:

   rotation_event.k[i] = "DTNZH3ULvYawyZ-i0d8JZU6JR2nmAoAfSVPzhzS6b5CM"
   

3. Compute digest of current key:

   computed_digest = Blake3(rotation_event.k[i])
   

4. Verify commitment:

   assert computed_digest == prior_event.n[i]
   

This verification proves:

• The current key was pre-committed in the prior event
• The controller had possession of the key before the prior event
• No quantum attack could have derived the key from its digest

Verifying Rotation Authority:

1. Check signature on rotation event using current keys
2. Verify pre-rotation commitment (as above)
3. Validate event sequence (sequence number, prior event digest)
4. Check threshold satisfaction (sufficient signatures from current keys)

Only if all checks pass is the rotation considered valid and quantum-secure.

In ACDC Credentials

Post-quantum security extends to ACDC credentials through the issuer's AID:

{
  "v": "ACDC10JSON00011c_",
  "d": "EL1L56LyoKrIofnn0oPChS4EyzMHEEk75INJohDS_Bug",
  "i": "EL1L56LyoKrIofnn0oPChS4EyzMHEEk75INJohDS_Bug",
  "s": "E0d8JZU6JR2nmAoAfSVPzhzS6b5CMTNZH3ULvYawyZ-i",
  "a": {
    "d": "ETNZH3ULvYawyZ-i0d8JZU6JR2nmAoAfSVPzhzS6b5CM",
    "i": "EYAfSVPzhzaU6JR2nmoTNZH3ULvwyZb6b5CMi0d8JZAS",
    "LEI": "254900OPPU84GM83MG36"
  }
}

The credential's quantum security derives from:

• Issuer AID (i field) with post-quantum key management
• SAID (d field) using quantum-resistant hash functions
• Schema SAID (s field) ensuring schema integrity
• Attribute SAIDs providing content integrity

Verifiers can trust the credential's authenticity because:

1. The issuer's AID has quantum-secure key management
2. The credential is signed with keys that can be rotated before quantum attack
3. All integrity commitments use quantum-resistant hash functions

Related Primitives

Cryptographic Hash Functions

Post-quantum security in KERI fundamentally depends on the quantum resistance of cryptographic hash functions:

• Blake3: Primary hash function for KERI, provides 128 bits of quantum security with 256-bit output
• Blake2b-256: Alternative hash function with similar security properties
• SHA3-256: NIST-standardized hash function, quantum-resistant
• SHA2-512: Provides 256 bits of quantum security

These hash functions share the property that quantum computers provide only a quadratic speedup (via Grover's algorithm) rather than the exponential speedup available for factorization and discrete logarithm problems.

Key Derivation Functions

KERI uses key derivation functions (KDFs) to generate keys from high-entropy seeds:

• HKDF (HMAC-based KDF): Extracts and expands entropy
• Argon2: Memory-hard KDF for password-based key derivation
• PBKDF2: Traditional password-based KDF

These KDFs maintain their security properties against quantum attacks when using quantum-resistant hash functions as their underlying primitive.

Digital Signature Schemes

While KERI's current implementations use classical signature schemes (Ed25519, ECDSA), the protocol is designed to support post-quantum signature algorithms:

Current (Quantum-Vulnerable):

• Ed25519: Elliptic curve signatures (vulnerable to Shor's algorithm)
• ECDSA: Elliptic curve signatures (vulnerable to Shor's algorithm)
• RSA: Factorization-based signatures (vulnerable to Shor's algorithm)

Future (Quantum-Resistant):

• CRYSTALS-Dilithium: Lattice-based signatures (NIST PQC standard)
• SPHINCS+: Hash-based signatures (NIST PQC standard)
• Falcon: Lattice-based signatures (NIST PQC standard)

KERI's pre-rotation mechanism provides quantum security regardless of which signature scheme is used, because the next keys are hidden behind quantum-resistant hash functions.

Composition Patterns

Pattern 1: Hash-Based Commitment + Classical Signatures

Current KERI implementations use:

Quantum-Resistant Hash (next key) + Classical Signature (current key)

This provides quantum security through temporal advantage: keys rotate before quantum attack succeeds.

Pattern 2: Hash-Based Commitment + PQC Signatures

Future KERI implementations may use:

Quantum-Resistant Hash (next key) + PQC Signature (current key)

This provides defense-in-depth: both the commitment mechanism and the signature scheme are quantum-resistant.

Pattern 3: Multi-Layer Security

High-security deployments can combine:

Multi-sig (M-of-N) + Pre-rotation + Short rotation intervals + High entropy

This creates multiple independent barriers to quantum attack.

Implementation Considerations

Rotation Interval Selection

The quantum security of KERI depends critically on rotating keys before quantum computers can attack them. Factors to consider:

Quantum Computing Progress:

• Monitor NIST and academic research on quantum computing capabilities
• Track qubit counts, error rates, and gate fidelities in quantum processors
• Adjust rotation intervals as quantum technology advances

Attack Time Estimation:

• Estimate time required for quantum computer to break current key scheme
• Factor in key size (e.g., Ed25519 requires ~2330 logical qubits for Shor's algorithm)
• Consider error correction overhead (physical qubits per logical qubit)

Operational Constraints:

• Balance security with operational overhead of frequent rotations
• Consider witness coordination time for multi-sig rotations
• Account for network latency and event propagation delays

Recommended Intervals (as of 2024):

• High-security identifiers: Rotate every 1-3 months
• Medium-security identifiers: Rotate every 6-12 months
• Low-security identifiers: Rotate annually

These intervals should be shortened as quantum computing advances.

Entropy Requirements

Post-quantum security requires sufficient entropy in key generation:

Minimum Requirements:

• 128 bits of entropy: Provides 64 bits of quantum security (marginal)
• 256 bits of entropy: Provides 128 bits of quantum security (recommended)
• 512 bits of entropy: Provides 256 bits of quantum security (high-security)

Entropy Sources:

• Hardware RNGs: TPM, HSM, or CPU-based random number generators
• OS entropy pools: /dev/urandom (Linux), CryptGenRandom (Windows)
• CSPRNG: ChaCha20, AES-CTR with proper seeding

Entropy Testing:

• Use NIST SP 800-90B entropy assessment tools
• Verify minimum entropy per bit
• Test for bias, correlation, and predictability

Hash Function Selection

Choosing appropriate hash functions for post-quantum security:

Blake3-256 (Recommended):

• Fast (faster than SHA2 and SHA3)
• Quantum-resistant (128 bits of quantum security)
• Well-analyzed cryptographic properties
• Native support in KERI implementations

SHA3-256 (Conservative):

• NIST-standardized
• Quantum-resistant (128 bits of quantum security)
• Different construction than SHA2 (Keccak sponge)
• Slower than Blake3 but more conservative choice

SHA2-512 (High-Security):

• Provides 256 bits of quantum security
• Widely supported and well-analyzed
• Larger output size (64 bytes vs 32 bytes)
• Recommended for long-term high-security applications

Key Storage and Protection

Post-quantum security requires protecting both current and next keys:

Current Signing Keys:

• Store in HSM or secure enclave when possible
• Use encrypted key storage with strong passphrases
• Implement access controls and audit logging
• Consider multi-party computation (MPC) for high-security applications

Next (Pre-Rotated) Keys:

• Critical: These keys provide quantum security and must be protected even more carefully
• Store offline in cold storage when possible
• Use separate storage from current keys (defense-in-depth)
• Consider geographic distribution for disaster recovery
• Implement strict access controls (higher than current keys)

Key Generation Environment:

• Generate keys in air-gapped environment for high-security applications
• Use hardware RNGs for entropy
• Verify entropy quality before key generation
• Securely erase key generation artifacts

Witness and Watcher Configuration

Post-quantum security extends to the witness network:

Witness Pool Size:

• Larger witness pools provide better security against compromise
• Recommended: 5-7 witnesses for production identifiers
• Use geographically distributed witnesses
• Ensure witnesses use quantum-resistant infrastructure

Threshold Configuration:

• Set thresholds to require supermajority (e.g., 4-of-5, 5-of-7)
• Higher thresholds provide better security but reduce availability
• Consider TOAD (Threshold of Accountable Duplicity)

Watcher Networks:

• Deploy watchers to detect duplicity
• Use diverse watcher implementations
• Monitor for conflicting key event logs
• Implement automated alerting for duplicity detection

Migration to PQC Algorithms

While KERI's pre-rotation provides quantum security with classical algorithms, organizations may want to migrate to post-quantum cryptographic algorithms:

Algorithm Selection:

• CRYSTALS-Dilithium: NIST PQC standard, good performance
• SPHINCS+: Hash-based, conservative choice, larger signatures
• Falcon: Compact signatures, more complex implementation

Migration Strategy:

1. Hybrid approach: Use both classical and PQC signatures during transition
2. Gradual rollout: Migrate high-security identifiers first
3. Backward compatibility: Maintain support for classical algorithms during transition
4. Testing: Extensive testing of PQC implementations before production use

CESR Support:

• CESR derivation codes will be defined for PQC algorithms
• Implementations must support multiple algorithm types
• Verifiers must handle both classical and PQC signatures

Performance Considerations

Post-quantum security mechanisms have performance implications:

Hash Function Performance:

• Blake3: ~3-10 GB/s (highly optimized)
• SHA3-256: ~1-2 GB/s
• SHA2-512: ~2-4 GB/s

Key Generation:

• Classical (Ed25519): ~10,000 keys/second
• PQC (Dilithium): ~1,000-5,000 keys/second
• Hash-based (SPHINCS+): ~100-1,000 keys/second

Signature Size:

• Classical (Ed25519): 64 bytes
• PQC (Dilithium): 2,420 bytes (Level 2)
• Hash-based (SPHINCS+): 7,856 bytes (Level 1)

Verification Time:

• Classical (Ed25519): ~50,000 verifications/second
• PQC (Dilithium): ~10,000-20,000 verifications/second
• Hash-based (SPHINCS+): ~5,000-10,000 verifications/second

These performance characteristics should be considered when designing systems with post-quantum security requirements.

Conclusion

KERI's approach to post-quantum security represents a pragmatic and innovative solution to the quantum computing threat. By leveraging the quantum resistance of cryptographic hash functions through the pre-rotation mechanism, KERI provides quantum security today without requiring immediate adoption of post-quantum cryptographic algorithms. This temporal security model, combined with adaptive parameters (rotation intervals, entropy levels, hash functions), ensures that KERI-based systems can maintain security as quantum computing technology advances.

The key insight is that protocol-level security properties can provide quantum resistance even when individual cryptographic primitives may be vulnerable. This approach offers a path forward for securing digital identities in the post-quantum era while allowing the ecosystem to gradually transition to fully post-quantum cryptographic algorithms as they mature and become standardized.