ECC vs SLH DSA

This document explores the comparison between Elliptic Curve Cryptography (ECC) - specifically ECDSA and EdDSA - and Stateless Hash-based Digital Signature Algorithm (SLH DSA).

Introduction

In the ever-evolving landscape of blockchain technology, security remains a paramount concern. We'll delve into how traditional blockchains use ECC and how Quranium's adoption of SLH DSA(post Quantum Cryptography) provides quantum-resistant security.

Elliptic Curve Cryptography (ECC)

Historical Context

ECC was first proposed in 1985 by Neal Koblitz and Victor S. Miller. At the time of its invention, the computational power available was significantly limited compared to today's standards.

The maximum computational power available in 1985 was significantly lower than today's standards. While personal computers were becoming more common, supercomputers of that era represented the pinnacle of computing capability. Some notable examples include:

• Cray-2: One of the fastest supercomputers in 1985, with a peak performance of about 1.9 GFLOPS (billion floating-point operations per second)

• NEC SX-2: Another leading supercomputer, capable of approximately 1.3 GFLOPS

• IBM 3090: A mainframe computer used by large organizations, with performance in the range of hundreds of MFLOPS (million floating-point operations per second)

To put this in perspective, a modern smartphone in 2024 can easily achieve performance in the range of tens to hundreds of GFLOPS, surpassing the most powerful supercomputers of 1985 by orders of magnitude.

Computational Power in 1985

In 1985, personal computers were just becoming mainstream. The average PC had:

• Processor speed: 4-8 MHz

• RAM: 256 KB - 640 KB

• Storage: 10-20 MB hard drives

Theory and Functionality

ECC operates on the algebraic structure of elliptic curves over finite fields. The security of ECC is based on the elliptic curve discrete logarithm problem (ECDLP), which is believed to be difficult to solve with classical computers.

How ECC Works

1. Define an elliptic curve over a finite field

2. Choose a base point G on the curve

3. Generate a private key (random number) and public key (point on the curve)

4. Use these keys for encryption, digital signatures, or key agreement

Let's delve deeper into how Elliptic Curve Cryptography (ECC) works, exploring each aspect with detailed explanations and diagrams.

1. Elliptic Curve Definition

An elliptic curve over a finite field is defined by the equation:

y² = x³ + ax + b

Where a and b are constants that define the shape of the curve, and x and y are coordinates on the curve.

graph TD
    A[Elliptic Curve] --> B[Equation: y² = x³ + ax + b]
    B --> C[a and b are constants]
    B --> D[x and y are coordinates]
    A --> E[Defined over a finite field]

2. Point Operations on the Curve

ECC relies on two fundamental operations on the curve: point addition and point multiplication.

Point Addition

Given two points P and Q on the curve, we can define a third point R as their sum (P + Q = R).

graph LR
    A[Point P] --> C[Point R]
    B[Point Q] --> C
    C --> D[R = P + Q]

Point Multiplication

Given a point P on the curve and an integer k, we can compute kP (P added to itself k times).

graph LR
    A[Point P] --> B[kP]
    C[Integer k] --> B
    B --> D[P added to itself k times]

3. Key Generation

ECC uses these operations for key generation:

graph TD
    A[Choose base point G] --> B[Select private key d]
    B --> C[Compute public key Q = dG]
    C --> D[Public key Q is a point on the curve]

4. ECDSA (Elliptic Curve Digital Signature Algorithm)

ECDSA is used for digital signatures in many blockchain systems. Here's a simplified view of how it works:

Signing & Verification

graph TD
    A[Message m] --> B[Hash message: e = HASH(m)]
    B --> C[Generate random k]
    C --> D[Compute R = kG]
    D --> E[Compute r = x-coordinate of R]
    E --> F[Compute s = k⁻¹(e + dr) mod n]
    F --> G[Signature = (r, s)]

    H[Verify] --> I[Receive message m and signature (r,s)]
    I --> J[Compute e = HASH(m)]
    J --> K[Compute u1 = es⁻¹ mod n]
    J --> L[Compute u2 = rs⁻¹ mod n]
    K --> M[Compute P = u1G + u2Q]
    L --> M
    M --> N[Check if x-coordinate of P equals r]
    N --> O{Signature valid?}
    O -->|Yes| P[Accept]
    O -->|No| Q[Reject]

5. Security Principle

The security of ECC is based on the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP).

graph TD
    A[Given P and Q = kP] --> B[Find k]
    B --> C[Computationally infeasible]
    C --> D[Forms basis of ECC security]

Security Principle

ECC's security relies on the computational infeasibility of solving the ECDLP, even with significant classical computing power.

ECC in Bitcoin and Other Blockchains

Bitcoin, introduced in 2009, uses the secp256k1 curve for its cryptographic operations. This curve was defined in the Standards for Efficient Cryptography (SEC) document published by Certicom Research in 2000.

Computational Power: 2000-2010

When secp256k1 was introduced (2000):

• Average CPU speed: 600 MHz - 1 GHz

• RAM: 64-256 MB

When Bitcoin launched (2009):

• Average CPU speed: 2-3 GHz

• RAM: 2-4 GB

Current State of ECC (2024)

While ECC has served well for over a decade, the rapid advancement in computational power, especially with the advent of quantum computing, poses significant threats.

Computational Power in 2024

• Average CPU speed: 3-5 GHz (multi-core)

• RAM: 16-64 GB

• Quantum computers: 1000+ qubits available

Vulnerabilities of ECC

1. Shor's algorithm on quantum computers can solve the ECDLP efficiently

2. Practical demonstrations have shown up to 60% success in breaking ECC under certain conditions

3. The National Institute of Standards and Technology (NIST) has called for quantum-resistant cryptographic standards

NIST has approved several post-quantum cryptographic standards as part of their Post-Quantum Cryptography Standardization process. Here's a list of the approved algorithms:

• Public-key Encryption and Key-establishment Algorithms:

  • CRYSTALS-Kyber

• Digital Signature Algorithms:

  • CRYSTALS-Dilithium

  • FALCON

  • SPHINCS+

These algorithms are designed to resist attacks from both classical and quantum computers, ensuring long-term security for sensitive data and communications.

<aside> Conclusion: The security of cryptocurrencies using ECC, including Bitcoin, is at risk in the face of advancing quantum computing technology.

</aside>

Stateless Hash-based Digital Signature Algorithm (SLH DSA)

Introduction to Quranium's Approach

Quranium addresses the quantum threat by implementing SLH DSA, a post-quantum cryptographic solution.

SLH DSA can be seen as a variant or implementation of the general principles that SPHINCS+ embodies, tailored for specific use cases or performance requirements.

Quranium's choice of SLH DSA aligns with the post-quantum cryptography direction set by NIST's approval of SPHINCS+, demonstrating a commitment to using cutting-edge, quantum-resistant cryptographic techniques in its blockchain architecture.

Theory and Functionality of SLH DSA

SLH DSA is based on the security of cryptographic hash functions, which are believed to be resistant to quantum attacks.

How SLH DSA Works

1. Generate a large set of one-time key pairs

2. Create a Merkle tree from the public keys

3. Sign messages using the one-time private keys

4. Verify signatures using the corresponding public keys and Merkle tree path

1. Generate a large set of one-time key pairs

SLH DSA starts by generating numerous one-time key pairs. Each pair consists of a private key and a corresponding public key.

graph TD
    A[Generate Key Pairs] --> B[Private Key 1]
    A --> C[Public Key 1]
    A --> D[Private Key 2]
    A --> E[Public Key 2]
    A --> F[...]
    A --> G[Private Key n]
    A --> H[Public Key n]

2. Create a Merkle tree from the public keys

The public keys are then used to construct a Merkle tree. This tree structure allows for efficient verification of the keys.

graph TD
    A[Root Hash] --> B[Hash 1-2]
    A --> C[Hash 3-4]
    B --> D[Hash 1]
    B --> E[Hash 2]
    C --> F[Hash 3]
    C --> G[Hash 4]
    D --> H[Public Key 1]
    E --> I[Public Key 2]
    F --> J[Public Key 3]
    G --> K[Public Key 4]

3. Sign messages using the one-time private keys

When signing a message, SLH DSA uses one of the private keys from the generated set. Each private key is used only once to maintain security.

sequenceDiagram
    participant M as Message
    participant PK as Private Key
    participant S as Signature
    M->>PK: Input
    PK->>S: Sign
    Note right of S: One-time use

4. Verify signatures using the corresponding public keys and Merkle tree path

Verification involves using the corresponding public key and the Merkle tree path to authenticate the signature.

graph TD
    A[Signature] --> B[Verify]
    C[Public Key] --> B
    D[Merkle Tree Path] --> B
    B --> E{Valid?}
    E -->|Yes| F[Accept]
    E -->|No| G[Reject]

This process ensures the integrity and authenticity of the signed message while maintaining quantum resistance through the use of hash-based cryptography and the one-time nature of the keys.

Practical Example: ECC vs SLH DSA

Let's compare ECC and SLH DSA in a practical scenario of signing and verifying a transaction in a blockchain network.

Scenario: Signing a 1 KB transaction

Aspect	ECC (ECDSA)	SLH DSA
Key generation time	~0.1 seconds	~1 second
Signature size	64 bytes	~41 KB
Signing time	~0.5 ms	~10 ms
Verification time	~1 ms	~5 ms
Quantum resistance	No	Yes

Note: These are approximate values and may vary based on specific implementations and hardware.

Analysis

1. Key Generation: SLH DSA takes longer due to the creation of multiple one-time key pairs and the Merkle tree.

2. Signature Size: SLH DSA signatures are significantly larger, which may impact network bandwidth and storage requirements.

3. Signing and Verification: While SLH DSA is slower, the difference is negligible for most practical applications.

4. Quantum Resistance: The major advantage of SLH DSA lies in its resistance to quantum attacks, ensuring long-term security.

Real-world Implications

1. Storage: For a blockchain with 1 million transactions, ECC would require ~64 MB for signatures, while SLH DSA would need ~41 GB.

2. Network Load: SLH DSA's larger signatures may increase network traffic, potentially affecting transaction speed in high-volume scenarios.

3. Future-proofing: While ECC is currently faster and more space-efficient, SLH DSA provides protection against future quantum attacks, which could potentially compromise ECC-based systems.

<aside> Conclusion: While SLH DSA introduces some performance overhead, its quantum resistance makes it a crucial choice for long-term blockchain security, especially as quantum computing advances.

</aside>

Security Principle

SLH DSA's security is rooted in the difficulty of inverting cryptographic hash functions, a problem that remains hard even for quantum computers.

Comparison: ECC vs SLH DSA

Key differences:

• Signature size: ECC (256 bits) vs SLH DSA (41,000 bits)

• Quantum resistance: ECC (vulnerable) vs SLH DSA (resistant)

• Computational requirements: ECC (lower) vs SLH DSA (higher)

Detailed Comparison: secp256k1, ECDSA, EdDSA vs SLH DSA

Aspect	secp256k1 (ECDSA)	EdDSA (Ed25519)	SLH DSA (Quranium)
Curve Type	Koblitz curve over prime field	Twisted Edwards curve	N/A (Hash-based)
Key Size	256 bits	256 bits	Variable, typically larger
Signature Size	64 bytes	64 bytes	~41 KB
Security Level	128 bits	128 bits	256 bits (adjustable)
Quantum Resistance	No	No	Yes
Speed (Signing)	Fast	Very Fast	Slower
Speed (Verification)	Fast	Very Fast	Moderate
Blockchain Usage	Bitcoin, Ethereum	Cardano, Polkadot	Quranium

Key Points:

1. Curve Type:

   • secp256k1: Uses a specific Koblitz curve, optimized for efficiency in Bitcoin.

   • EdDSA: Uses a twisted Edwards curve, offering improved performance and security properties.

   • SLH DSA: Doesn't use elliptic curves, instead relying on hash functions for security.

2. Signature Size:

   • ECDSA and EdDSA: Compact 64-byte signatures, efficient for blockchain transactions.

   • SLH DSA: Much larger signatures (~41 KB), potentially impacting blockchain storage and transmission.

3. Quantum Resistance:

   • secp256k1 and EdDSA: Vulnerable to quantum attacks using Shor's algorithm.

   • SLH DSA: Designed to resist quantum attacks, providing long-term security.

4. Performance:

   • ECDSA and EdDSA: Generally faster for signing and verification.

   • SLH DSA: Slower, but the trade-off is increased security against quantum threats.

5. Blockchain Adoption:

   • secp256k1: Widely used in Bitcoin and many other cryptocurrencies.

   • EdDSA: Adopted by newer blockchains for its improved properties.

   • SLH DSA: Currently unique to Quranium, offering a forward-looking approach to blockchain security.

Diagrams and Blockchain Usage

1. secp256k1 (ECDSA)

graph TD
    A[Generate Key Pair] --> B[Private Key]
    A --> C[Public Key]
    D[Message] --> E[Sign with Private Key]
    E --> F[Signature]
    F --> G[Verify with Public Key]
    G --> H{Valid?}
    H -->|Yes| I[Accept]
    H -->|No| J[Reject]

Used in:

• Bitcoin

• Ethereum

• Litecoin

• Dogecoin

2. EdDSA (Ed25519)

graph TD
    A[Generate Key Pair] --> B[Private Key]
    A --> C[Public Key]
    D[Message] --> E[Sign with Private Key]
    E --> F[Signature]
    F --> G[Verify with Public Key]
    G --> H{Valid?}
    H -->|Yes| I[Accept]
    H -->|No| J[Reject]

Used in:

• Cardano

• Polkadot

• Solana

• Algorand

3. SLH DSA (Quranium)

graph TD
    A[Generate Multiple Key Pairs] --> B[Private Keys]
    A --> C[Public Keys]
    C --> D[Build Merkle Tree]
    E[Message] --> F[Sign with One-Time Private Key]
    F --> G[Signature + Merkle Path]
    G --> H[Verify with Public Key and Merkle Path]
    H --> I{Valid?}
    I -->|Yes| J[Accept]
    I -->|No| K[Reject]

Used in:

• Quranium (currently the only blockchain using this specific implementation)

Quranium's Implementation

Quranium leverages SLH DSA to provide quantum-resistant security for its blockchain, ensuring long-term protection against emerging computational threats.

Architecture Diagrams

ECC-based Blockchain Architecture

graph TD;
    A[User Wallet] -->|Transaction| B[Network];
    B -->|Verify Signature| C[ECC Verification];
    C -->|Add to Mempool| D[Mining Node];
    D -->|Create Block| E[Blockchain];
    F[Attacker] -.->|Quantum Computer| C;

Quranium's SLH DSA-based Architecture

graph TD;
    A[User Wallet] -->|Transaction| B[Network];
    B -->|Verify Signature| C[SLH DSA Verification];
    C -->|Add to Mempool| D[Validation Node];
    D -->|Create Block| E[Blockchain];
    F[Attacker] -.->|Quantum Computer| C;
    C -->|Resist| F;