autohandai Implementing Zero-Knowledge Proof for Authentication
Overview
Zero-Knowledge Proofs (ZKPs) allow a prover to demonstrate knowledge of a secret (such as a password or private key) without revealing the secret itself. This skill implements the Schnorr identification protocol and a simplified ZKPP (Zero-Knowledge Password Proof) using the discrete logarithm problem, enabling authentication where the server never learns the user's password.
Objectives
- Implement Schnorr's identification protocol for ZKP authentication
- Build a non-interactive ZKP using Fiat-Shamir heuristic
- Implement zero-knowledge password proof (ZKPP)
- Demonstrate completeness, soundness, and zero-knowledge properties
- Compare ZKP authentication with traditional password verification
Key Concepts
ZKP Properties
| Property | Description |
|---|---|
| Completeness | Honest prover always convinces honest verifier |
| Soundness | Dishonest prover cannot convince verifier (except negligible probability) |
| Zero-Knowledge | Verifier learns nothing beyond the statement's truth |
Schnorr Protocol
- Setup: Public generator g, prime p, q (order of g)
- Registration: Prover computes y = g^x mod p (public key from secret x)
- Commitment: Prover sends t = g^r mod p (random r)
- Challenge: Verifier sends random c
- Response: Prover sends s = r + c*x mod q
- Verify: Check g^s == t * y^c mod p
Security Considerations
- Use cryptographically secure random number generators
- Challenge must be unpredictable (from verifier's perspective)
- For non-interactive proofs, use Fiat-Shamir with collision-resistant hash
- ZKP alone does not provide forward secrecy; combine with TLS
Validation Criteria
- Honest prover always verifies successfully (completeness)
- Random response without secret does not verify (soundness)
- Server never receives the secret value
- Non-interactive proof is verifiable offline
- Multiple authentications produce different transcripts
- Protocol resists replay attacks