- Complete Authentication Flow
- Step-by-Step Mathematical Example
- Code Walkthrough
- Verification Process
- Security Properties in Practice
┌─────────────┐ ┌─────────────┐
│ Client │ │ Server │
└──────┬──────┘ └──────┬──────┘
│ │
│ REGISTRATION PHASE │
│ │
│ 1. User enters: alice, password123 │
│ │
│ 2. Generate salt (random 256-bit) │
│ salt = "A7F9...B2C4" │
│ │
│ 3. Derive secret x: │
│ x = SHA256(alice||password123||salt) mod q │
│ x = 1234567... (secret, never sent) │
│ │
│ 4. Compute public keys: │
│ y₁ = g^x mod p │
│ y₂ = h^x mod p │
│ │
│ 5. Send (alice, y₁, y₂, salt) ─────────────> │
│ │
│ 6. Store in DB:
│ users[alice] = {
│ y1: y₁,
│ y2: y₂,
│ salt: salt
│ }
│ │
│ AUTHENTICATION PHASE │
│ │
│ 7. User enters: alice, password123 │
│ │
│ 8. Re-derive x (same as step 3) │
│ │
│ 9. Generate random k ∈ [1, q-1] │
│ k = 9876543... (ephemeral secret) │
│ │
│ 10. Compute commitments: │
│ a₁ = g^k mod p │
│ a₂ = h^k mod p │
│ │
│ 11. Request challenge (nonce): │
│ send {username} to /challenge │
│ receive {y₁, y₂, salt, nonce} │
│ │
│ 12. Compute challenge (Fiat-Shamir): │
│ c = SHA256(hex(a₁)|hex(a₂)|hex(y₁)| │
│ hex(y₂)|nonce) mod q │
│ │
│ 13. Compute response: │
│ s = k - c·x mod q │
│ │
│ 14. Send Proof(a₁, a₂, s, nonce) ──────────> │
│ │
│ 15. Fetch from DB:
│ (y₁, y₂, salt)
│ │
│ 16. Validate nonce:
│ single-use & not expired
│ │
│ 17. Recompute challenge:
│ c' = SHA256(hex(a₁)|hex(a₂)|
│ hex(y₁)|hex(y₂)|nonce)
│ │
│ 18. Verify equations:
│ ✓ g^s · y₁^c' ≟ a₁ mod p
│ ✓ h^s · y₂^c' ≟ a₂ mod p
│ │
│ 19. Create session:
│ token = random(256-bit)
│ sessions[token] = {
│ user: alice,
│ expiry: now + 3600s
│ }
│ │
│ <───────────── 20. Send token ─────────────── │
│ │
│ 21. Use token for authenticated requests │
│ │
Let's work through a simplified example with smaller numbers for clarity.
p = 23 (prime, in reality 2048 bits)
q = 11 (= (p-1)/2, in reality 2047 bits)
g = 5 (generator)
h = 10 (another generator, h ≠ g)
Verification that g and h are valid generators:
g = 5:
5^2 mod 23 = 25 mod 23 = 2 ≠ 1 ✓
5^11 mod 23 = 22 ≠ 1 ✓
h = 10:
10^2 mod 23 = 100 mod 23 = 8 ≠ 1 ✓
10^11 mod 23 = 22 ≠ 1 ✓
User Input:
username = "alice"
password = "secret123"
Step 1: Generate Salt
salt = "A7B9" (in reality, 256-bit hex string)
Step 2: Derive Secret x
combined = "alice" + "secret123" + "A7B9"
= "alicesecret123A7B9"
hash = SHA256("alicesecret123A7B9")
= 0x7a3b2c... (256-bit hash)
x = hash mod q
= [large number] mod 11
= 7 (example value)
SECRET: x = 7 (never revealed!)
Step 3: Compute Public Keys
y₁ = g^x mod p
= 5^7 mod 23
= 78125 mod 23
= 17
y₂ = h^x mod p
= 10^7 mod 23
= 10000000 mod 23
= 14
Step 4: Send to Server
Send: (username="alice", y₁=17, y₂=14, salt="A7B9")
Step 5: Server Stores
Database:
alice -> {
y1: 17,
y2: 14,
salt: "A7B9"
}
User Input (Same Credentials):
username = "alice"
password = "secret123"
Step 1: Re-derive Secret x
Fetch salt from server: "A7B9"
x = SHA256("alice" + "secret123" + "A7B9") mod 11
= 7 (same as registration!)
Step 2: Generate Random k
k = random(1, q-1)
= random(1, 10)
= 4 (example ephemeral value)
SECRET: k = 4 (used once, then discarded)
Step 3: Compute Commitments
a₁ = g^k mod p
= 5^4 mod 23
= 625 mod 23
= 6
a₂ = h^k mod p
= 10^4 mod 23
= 10000 mod 23
= 18
Step 4: Request Nonce and Compute Challenge (Fiat-Shamir)
nonce = "A1B2" (example; real server nonce is 256-bit hex)
challenge_input = hex(a₁) + "|" + hex(a₂) + "|" + hex(y₁) + "|" + hex(y₂) + "|" + nonce
c = SHA256(challenge_input) mod q
= [hash value] mod 11
= 3 (example challenge)
Step 5: Compute Response
s = k - c·x mod q
= 4 - 3·7 mod 11
= 4 - 21 mod 11
= -17 mod 11
= -17 + 22 (add 2q to make positive)
= 5
Detailed modular arithmetic:
-17 mod 11:
-17 = -2·11 + 5
Therefore: -17 mod 11 = 5
Step 6: Create Proof
Proof = {
a₁: 6,
a₂: 18,
s: 5
}
Step 7: Send to Server
Send: Proof(a₁=6, a₂=18, s=5, t=1633024800)
Server receives: Proof(a₁=6, a₂=18, s=5, nonce="A1B2")
Step 1: Fetch User Data
From DB: y₁ = 17, y₂ = 14, salt = "A7B9"
Step 2: Validate Nonce
Check server-side nonce store:
- Nonce belongs to username
- Nonce not used yet
- Nonce not expired
If any check fails → Reject (possible replay)
Step 3: Recompute Challenge
c' = SHA256(hex(a₁)|hex(a₂)|hex(y₁)|hex(y₂)|nonce) mod 11
= 3 (same as prover's c)
Step 4: Verify First Equation
Verify: g^s · y₁^c' ≟ a₁ mod p
Left side:
g^s · y₁^c' = 5^5 · 17^3 mod 23
= 3125 · 4913 mod 23
= (3125 mod 23) · (4913 mod 23) mod 23
= 16 · 14 mod 23
= 224 mod 23
= 17
Wait, this should equal a₁ = 6. Let me recalculate...
Actually: 5^5 mod 23 = 3125 mod 23
= 135·23 + 20 = 20
17^3 mod 23 = 4913 mod 23
= 213·23 + 14 = 14
20 · 14 mod 23 = 280 mod 23
= 12·23 + 4 = 4
Hmm, let me recalculate from s computation...
s = k - c·x mod q
= 4 - 3·7 mod 11
Let me verify step by step:
3·7 = 21
4 - 21 = -17
-17 mod 11: -17 + 2·11 = -17 + 22 = 5 ✓
So s = 5
Now verify:
g^s = 5^5 mod 23 = 3125 mod 23
3125 ÷ 23 = 135 remainder 20
So 5^5 mod 23 = 20
y₁^c = 17^3 mod 23
17^2 = 289 = 12·23 + 13 = 13
17^3 = 17·13 mod 23 = 221 mod 23 = 9·23 + 14 = 14
g^s · y₁^c = 20 · 14 mod 23 = 280 mod 23 = 12·23 + 4 = 4
But a₁ = 6...
Let me recalculate a₁:
a₁ = g^k mod p = 5^4 mod 23
5^2 = 25 mod 23 = 2
5^4 = 2^2 mod 23 = 4
So a₁ = 4 (not 6, I made an error)
Now: g^s · y₁^c = 4 = a₁ ✓ VERIFIED!
Let me redo with corrected values:
Corrected Step 3 (Authentication): Compute Commitments
a₁ = g^k mod p
= 5^4 mod 23
= 4 (corrected)
a₂ = h^k mod p
= 10^4 mod 23
= 10000 mod 23
10^2 = 100 mod 23 = 8
10^4 = 64 mod 23 = 18 ✓
So a₂ = 18
Updated Challenge:
c = SHA256("4" + "18" + "17" + "14") mod 11
= 3 (for this example)
Verification Equation 1:
Verify: g^s · y₁^c ≟ a₁ mod p
5^5 · 17^3 ≟ 4 mod 23
Left side:
5^5 mod 23 = 20 (calculated above)
17^3 mod 23 = 14 (calculated above)
20 · 14 mod 23 = 280 mod 23 = 4 ✓
Right side:
a₁ = 4 ✓
4 = 4 ✓ EQUATION 1 VERIFIED!
Verification Equation 2:
Verify: h^s · y₂^c ≟ a₂ mod p
10^5 · 14^3 ≟ 18 mod 23
Left side:
10^5 mod 23:
10^2 = 100 mod 23 = 8
10^4 = 64 mod 23 = 18
10^5 = 10·18 mod 23 = 180 mod 23 = 19
14^3 mod 23:
14^2 = 196 mod 23 = 12
14^3 = 14·12 mod 23 = 168 mod 23 = 7
19 · 7 mod 23 = 133 mod 23
= 5·23 + 18 = 18 ✓
Right side:
a₂ = 18 ✓
18 = 18 ✓ EQUATION 2 VERIFIED!
Step 5: Accept and Create Session
✅ Both equations verified!
✅ Nonce valid and consumed!
Create session:
token = generate_random_token()
= "7F3A9C..."
sessions["7F3A9C..."] = {
username: "alice",
expiry: current_time + 3600
}
Return: {"token": "7F3A9C...", "message": "Authentication successful"}
File: python/zkp/chaum_pedersen.py
def register_user(self, username: str, password: str) -> UserPublicKey:
"""
Register a new user and return public keys
ZKP Property: Server never sees password or x
"""
# Input validation
if len(username) < 3 or len(username) > 50:
raise ValueError("Username must be 3-50 characters")
# Generate random salt (256 bits)
salt = self._generate_salt() # Returns 64-char hex string
# Derive secret x from password
x = self._derive_x(username, password, salt)
# Compute public keys
# y1 = g^x mod p
y1 = pow(self.g, x, self.p)
# y2 = h^x mod p
y2 = pow(self.h, x, self.p)
# Return public keys (x never leaves this function!)
return UserPublicKey(y1=y1, y2=y2, salt=salt)Key Points:
xis computed but never returned- Only
y1,y2,saltare sent to server - Python's
pow(base, exp, mod)is efficient (uses fast modular exponentiation)
def generate_proof(
self,
username: str,
password: str,
salt: str,
y1: int,
y2: int,
nonce_hex: str,
) -> Proof:
"""
Generate zero-knowledge proof of knowledge of x
Returns: Proof that can be verified without revealing x
"""
# Re-derive x from password (same as registration)
x = self._derive_x(username, password, salt)
# Generate ephemeral random k
k = secrets.randbelow(self.q - 1) + 1 # k ∈ [1, q-1]
# Compute commitments
a1 = pow(self.g, k, self.p) # a1 = g^k mod p
a2 = pow(self.h, k, self.p) # a2 = h^k mod p
# Compute Fiat-Shamir challenge (nonce-bound)
c = self._compute_challenge(a1, a2, y1, y2, nonce_hex)
# Compute response: s = k - c*x mod q
s = (k - c * x) % self.q
return Proof(a1=a1, a2=a2, s=s, timestamp=int(time.time())) # timestamp optionalKey Points:
kis random for each proof (prevents correlation)sis computed moduloq(subgroup order)cis deterministic (hash-based), making proof non-interactive- Nonce binding prevents replay attacks
def verify_proof(self, proof: Proof, y1: int, y2: int, nonce_hex: str) -> bool:
"""
Verify zero-knowledge proof
Returns: True if proof is valid, False otherwise
Never learns the secret x!
"""
# Recompute challenge using same hash function (nonce-bound)
c = self._compute_challenge(proof.a1, proof.a2, y1, y2, nonce_hex)
# Verify equation 1: g^s * y1^c ≟ a1 (mod p)
left1 = (pow(self.g, proof.s, self.p) * pow(y1, c, self.p)) % self.p
if left1 != proof.a1:
return False
# Verify equation 2: h^s * y2^c ≟ a2 (mod p)
left2 = (pow(self.h, proof.s, self.p) * pow(y2, c, self.p)) % self.p
if left2 != proof.a2:
return False
# Both equations hold!
return TrueKey Points:
- Challenge recomputed identically to prover (nonce-bound)
- Both equations must hold for proof to be valid
- Never uses or learns
xork
File: cpp/src/zkp/chaum_pedersen.cpp
UserPublicKey ChaumPedersenZKP::registerUser(
const std::string& username,
const std::string& password
) {
// Input validation
if (username.length() < 3 || username.length() > 50) {
throw std::runtime_error("Username must be 3-50 characters");
}
// Generate random salt
std::string salt = generateSalt();
// Derive secret x
Integer x = deriveX(username, password, salt);
// Compute public keys using Crypto++ modular exponentiation
Integer y1 = a_exp_b_mod_c(g_, x, p_); // y1 = g^x mod p
Integer y2 = a_exp_b_mod_c(h_, x, p_); // y2 = h^x mod p
// Return public key structure
UserPublicKey pk;
pk.y1 = y1;
pk.y2 = y2;
pk.salt = salt;
return pk; // x is destroyed when function returns
}C++ Advantages:
- Type safety (
Integerclass from Crypto++) - Automatic memory cleanup (RAII)
- Fast modular exponentiation (optimized assembly)
The verification equations work because of the algebraic structure:
Prover computes:
s = k - c·x mod q
Verifier checks:
g^s · y1^c ≟ a1 (mod p)
Substituting s = k - c·x:
g^(k - c·x) · (g^x)^c
= g^(k - c·x) · g^(x·c)
= g^(k - c·x + x·c)
= g^k
= a1 ✓
Same logic for second equation with h instead of g.
-
Prover's Perspective:
- Knows: x, k
- Computes: s = k - c·x
- Reveals: a1, a2, s (but NOT x or k)
-
Verifier's Perspective:
- Knows: y1, y2 (public keys)
- Receives: a1, a2, s
- Cannot extract x from this information
-
Why x Cannot Be Extracted:
Given: s, a1, a2, c, y1, y2 Need: x From s = k - c·x: x = (k - s) / c But k is unknown and random! Equation has two unknowns (x, k) and one equation Infinitely many solutions → cannot solve for x -
Simulator Proof: A simulator can create indistinguishable proofs without knowing x:
Simulator (no knowledge of x): 1. Choose random s', c' 2. Compute a1' = g^s' · y1^c' 3. Compute a2' = h^s' · y2^c' 4. Output (a1', a2', s', c') This transcript is statistically identical to real proof! Therefore, real proof reveals no information about x.
Test:
def test_completeness():
zkp = ChaumPedersenZKP()
# Register user with password
pk = zkp.register_user("alice", "password123")
# Generate proof with correct password
nonce = "00" * 32
proof = zkp.generate_proof("alice", "password123",
pk.salt, pk.y1, pk.y2, nonce)
# Verify proof
result = zkp.verify_proof(proof, pk.y1, pk.y2, nonce)
assert result == True # Always accepts valid proofMathematical Guarantee:
∀ valid (username, password):
P(verify_proof(generate_proof(...)) = True) = 1
Test:
def test_soundness():
zkp = ChaumPedersenZKP()
# Register with correct password
pk = zkp.register_user("alice", "password123")
# Try to authenticate with wrong password
nonce = "00" * 32
proof = zkp.generate_proof("alice", "WRONG_PASSWORD",
pk.salt, pk.y1, pk.y2, nonce)
# Verify proof
result = zkp.verify_proof(proof, pk.y1, pk.y2, nonce)
assert result == False # Rejects invalid proofMathematical Guarantee:
∀ invalid password:
P(verify_proof(...) = True) ≤ 1/q ≈ 2^-2047
Demonstration: Even after seeing 1000 valid proofs, attacker cannot:
- Extract the password
- Extract the secret x
- Forge a new valid proof
- Distinguish from simulator's output
Why?
- Each proof uses fresh random k
- Response s is masked by k
- No correlation between proofs
- Transcript is simulatable without x
Mechanism:
- Server issues a one-time nonce per login attempt via
/challenge - Proof binds to the nonce; server rejects reused/expired nonces
Client libraries include the nonce in the challenge computation to ensure uniqueness.
The implementation maintains ZKP properties through:
- ✅ Completeness: Valid credentials always authenticate
- ✅ Soundness: Invalid credentials never authenticate (negligible probability)
- ✅ Zero-Knowledge: Server learns nothing about password
- ✅ Replay Protection: One-time, short-lived nonces
- ✅ Non-Interactive: Fiat-Shamir transform
- ✅ Efficient: Fast modular exponentiation
All while never transmitting or storing passwords!
- ZKP_THEORY.md - Theoretical foundation
- CHAUM_PEDERSEN.md - Protocol specification
- API.md - REST API documentation