CHOAM is a custom zero-knowledge proof implementation of the Chaum-Pedersen protocol, a challenge-and-response Sigma protocol

The Chaum-Pedersen protocol demonstrates the elegant power of zero-knowledge cryptography. What appears as simple modular arithmetic actually enables profound security guarantees: proving knowledge without revelation.

Building CHOAM in Rust revealed several valuable lessons:

  • Rust’s Type Safety: The borrow checker prevented several potential security bugs around integer handling
  • Async Architecture: Tokio’s gRPC implementation scales beautifully for cryptographic workloads
  • Mathematical Principles: Zero-knowledge protocols showcase how pure mathematics solves real-world security problems

This implementation proves that sophisticated cryptographic protocols can be both secure and practical. The combination of Rust’s performance and safety guarantees with the mathematical elegance of zero-knowledge proofs creates a compelling foundation for next-generation authentication systems.

Whether you’re interested in cryptography, Rust development, or just curious about authentication alternatives, I encourage you to explore the full implementation. The mathematical foundations may seem complex, but the resulting security properties are worth the investment.

The full code is available on GitHub.

*The spice must flow.*or acquiring authentication tokens. Built in Rust, it distributes JWT (JSON Web Tokens) upon successful authentication without ever requiring the client to reveal their secret credentials.

This project demonstrates how zero-knowledge protocols can revolutionize authentication by eliminating the need to transmit passwords or secrets over the network. Unlike traditional authentication where credentials must be sent (even if encrypted), zero-knowledge protocols prove identity mathematically without revealing any sensitive information.

Why Zero-Knowledge Authentication Matters#

Traditional authentication systems have inherent vulnerabilities:

  • Passwords can be intercepted during transmission
  • Server breaches expose user credentials
  • Password reuse across services compounds security risks

Zero-knowledge authentication solves these problems by ensuring secrets never leave the client device. Even if an attacker intercepts the entire authentication exchange, they learn nothing about the user’s secret.

CHOAM is a custom zero-knowledge proof implementation of the Chaum-Pedersen protocol, a challenge-and-response Sigma protocol, for acquiring authentication tokens. It’s written in Rust and distributes a JWT (JSON web token) upon a successful authentication response to the provided challenge.

Zero-knowledge protocols have interesting and even counter-intuitive properties that show up in even simpler exchanges like Chaum-Pedersen. The Chaum-Pedersen protocol, though relatively straightforward, is a powerful primitive that can be applied in many useful ways.

Chaum-Pedersen Primer#

The Chaum-Pedersen protocol is a Sigma protocol that enables zero-knowledge authentication. While it requires a challenge-response exchange (adding some latency), it provides the powerful guarantee that the prover never reveals their secret.

How the Protocol Works#

The protocol involves two parties: a prover (client) and a verifier (server). Here’s the step-by-step process:

  1. Setup: Both parties agree on two public parameters:

    • A very large prime number p
    • A generator g (typically 2)

  2. Registration: The prover chooses a secret x and computes their public key h = g^x mod p, which they share with the verifier.

  3. Challenge Phase:

    • Prover generates a random number r and sends t = g^r mod p to the verifier
    • Verifier responds with a random challenge c

  4. Response Phase:

    • Prover computes s = r + c * x and sends it back
    • Verifier checks if g^s ≡ t * h^c (mod p)

The beauty is that the verifier can confirm the prover knows x without ever learning what x is.

Simulation & Zero-Knowledge#

Zero knowledge is the ability to prove that you know some number, x, without ever revealing x. A key property of zero-knowledge protocols is that their transcripts can be simulated, meaning they must be indistinguishable from a fake or real prover generating a possible solution for the secret.

Very Large Prime Numbers#

The security of modern cryptography is built on the difficulty of factoring very large prime numbers. If a solution is ever discovered to this problem, there will be massive social implications.

To generate a very large prime number, use OpenSSL:

openssl prime -generate -bits 2048

Generators#

A generator in cryptography refers to a specific finite group of numbers that can all be represented as g^K for some integer K. For our purposes, 2 is a perfectly good choice for a generator number.

Implementation Example#

Now that we understand the theory, let’s see how this works in practice. Here’s a complete example in Rust that demonstrates the Chaum-Pedersen protocol:

use num_bigint::BigUint;
use rand::Rng;

fn main() {
    println!("** Chaum-Pedersen Zero-Knowledge Authentication **");

    // Step 1: Setup - Public parameters (known to both prover and verifier)
    let p = BigUint::parse_bytes(b"296814148071936180783...", 10).unwrap(); // Large prime
    let g = BigUint::from(2u32); // Generator
    
    // Step 2: Registration - Prover's secret and public key
    let x = BigUint::from(42u32); // Prover's secret (never shared!)
    let h = g.modpow(&x, &p);     // Public key: h = g^x mod p
    
    // Step 3: Challenge Phase - Prover commits to random value
    let r = BigUint::from(rand::thread_rng().gen_range(1u32..100)); // Random nonce
    let t = g.modpow(&r, &p);     // Commitment: t = g^r mod p
    
    // Verifier sends random challenge
    let challenge = BigUint::from(rand::thread_rng().gen_range(0u32..10));
    
    // Step 4: Response Phase - Prover responds with proof
    let answer = &r + &challenge * &x; // s = r + c*x
    
    // Step 5: Verification - Check if proof is valid
    let left = g.modpow(&answer, &p);                    // g^s mod p
    let right = (&t * &h.modpow(&challenge, &p)) % &p;   // (t * h^c) mod p
    
    if left == right {
        println!("✅ Authentication successful: {} == {}", left, right);
        println!("Prover knows the secret without revealing it!");
    } else {
        println!("❌ Authentication failed");
    }
}

Key Points About This Implementation#

  • Security: The secret x never leaves the prover’s system
  • Randomness: Each authentication uses a fresh random r to prevent replay attacks
  • Verification: The mathematical relationship g^s ≡ t * h^c (mod p) proves knowledge of x
  • Zero-Knowledge: A transcript of this exchange reveals nothing about the secret x

Schnorr Protocol#

The Chaum-Pedersen protocol is essentially two passes of the Schnorr protocol setup between the prover and verifier. The Schnorr protocol follows a similar approach:

  • Select a very large prime p
  • Select a generator g that is not a multiple of p
  • Create a commitment (h)
  • Create a challenge (t sent from prover to verifier, verifier responds with c)
  • Response: prover computes s = r + cx and sends it to verifier
  • Verification: verifier checks if g^s = t * y ^ c mod p is true

CHOAM: Production-Ready Implementation#

The CHOAM server implements this protocol as a gRPC service with three main endpoints:

Service Definition#

syntax = "proto3";
package zkp_auth;

message RegisterRequest {
    string user = 1;
    int64 y1 = 2;   // First part of public key
    int64 y2 = 3;   // Second part of public key (for enhanced security)
}
message RegisterResponse {}

message AuthenticationChallengeRequest {
    string user = 1;
    int64 r1 = 2;   // First commitment value
    int64 r2 = 3;   // Second commitment value
}
message AuthenticationChallengeResponse {
    string auth_id = 1;  // Session identifier
    int64 c = 2;         // Random challenge from server
}

message AuthenticationAnswerRequest {
    string auth_id = 1;  // Session identifier
    int64 s = 2;         // Proof response
}
message AuthenticationAnswerResponse {
    string session_id = 1;  // JWT token for authenticated session
}

service Auth {
    rpc Register(RegisterRequest) returns (RegisterResponse);
    rpc CreateAuthenticationChallenge(AuthenticationChallengeRequest) returns (AuthenticationChallengeResponse);
    rpc VerifyAuthentication(AuthenticationAnswerRequest) returns (AuthenticationAnswerResponse);
}

Authentication Flow#

  1. Registration: Client generates secret, computes public key, registers with server
  2. Challenge Request: Client requests authentication challenge with commitment values
  3. Challenge Response: Server responds with random challenge and session ID
  4. Proof Submission: Client computes proof and submits for verification
  5. Token Issuance: Server verifies proof and issues JWT token

Real-World Applications#

Zero-knowledge authentication protocols like Chaum-Pedersen have several compelling use cases:

  • Cryptocurrency Wallets: Prove ownership without exposing private keys
  • Enterprise SSO: Authenticate across services without password transmission
  • IoT Devices: Secure authentication with minimal computational overhead
  • Privacy-Preserving Systems: User authentication without revealing identity information

Performance Considerations#

While zero-knowledge proofs provide excellent security properties, they do introduce some trade-offs:

  • Latency: Two-round authentication increases response time
  • Computation: Modular exponentiation operations are CPU-intensive
  • Implementation Complexity: Requires careful handling of large integers and cryptographic primitives

For CHOAM, these trade-offs are mitigated by:

  • Using efficient big integer libraries (num-bigint)
  • Implementing async gRPC for scalability
  • Caching computation-heavy operations where possible

Conclusions#

This was a cool protocol to learn, showcasing extremely interesting properties of simple logarithms. This was actually my first non-trivial Rust project, and it was a great way to learn several production aspects of Rust. Tokio’s gRPC tooling feels intuitive and allows for high confidence in testing.

The spice must flow.#

I named this project CHOAM because Chaum kind of sounds the same and I’ve been reading a lot of Dune.

The full code is available on GitHub.

References#