A secure implementation of a (t, n)-threshold ElGamal cryptosystem with Chaum-Pedersen zero-knowledge proofs for verifiable distributed decryption. This project demonstrates how multiple parties can collaboratively decrypt a message, where a threshold number of participants must cooperate to successfully recover the plaintext.
Academic Project: This was developed as a final project for an Applied Cryptography course. The cryptographic parameters (3072-bit safe prime, subgroup order, and generator) were provided by the course instructor to ensure consistency and security.
- Overview
- Features
- System Architecture
- Cryptographic Components
- Installation
- Usage Guide
- Testing
- Security Considerations
- Project Structure
- Technical Decisions
- Limitations & Future Work
- Dependencies
- Contributing
- License
This implementation showcases modern threshold cryptography techniques, allowing secure message encryption that requires collaboration among multiple parties for decryption. The system enforces a minimum threshold of participants (t+1 out of n) and uses zero-knowledge proofs to ensure honest behavior during the decryption process.
- Threshold Cryptography: (t, n)-threshold scheme with configurable parameters
- Zero-Knowledge Proofs: Chaum-Pedersen protocol ensures verifiable partial decryptions
- Hybrid Encryption: ElGamal key exchange combined with AES-256-GCM for efficiency
- Lagrange Interpolation: Mathematically sound secret reconstruction
- Interactive CLI: User-friendly menu-driven interface
- Comprehensive Testing: Full test suite validating all cryptographic operations
- Configurable (t, n) threshold where t+1 players are required to decrypt
- Successfully tested with various combinations (e.g., 5 players with threshold 2, 6 players with threshold 3)
- Enforces threshold requirement — fewer than t+1 players cannot decrypt
Implements the Chaum-Pedersen protocol to prove correct partial decryption without revealing secrets.
What each player proves: "I know my secret share aᵢ such that g^(aᵢ) = Aᵢ and B^(aᵢ) = hᵢ"
Protocol Steps:
- Commitment: Player generates random r, computes t₁ = g^r and t₂ = B^r
- Challenge: c = Hash(g, B, Aᵢ, hᵢ, t₁, t₂) using Fiat-Shamir heuristic
- Response: z = c·aᵢ + r (mod q)
- Verification: Verifier checks g^z = Aᵢ^c · t₁ and B^z = hᵢ^c · t₂
Rather than encrypting messages directly with ElGamal (which has size limitations), the system uses hybrid encryption:
- Key Exchange: ElGamal establishes shared secret S = g^(ab) mod p
- Key Derivation: K = SHA256(S) derives AES key
- Message Encryption: AES-256-GCM encrypts the actual message
- Benefits: Can encrypt messages of any length, provides authentication
Uses Lagrange interpolation to reconstruct the master secret from threshold shares:
- Coefficient Formula: wᵢ = ∏(j≠i) (0-xⱼ)/(xᵢ-xⱼ) mod q
- Reconstruction: S = ∏ hᵢ^(wᵢ) mod p, where S = B^a is the shared secret
┌─────────────────────────────────────────────────────────┐
│ KEY GENERATION │
│ (Trusted Dealer or DKG Simulation) │
│ • Master keypair (a, A=g^a) │
│ • Secret shares (a₁, a₂, ..., aₙ) via Shamir's SS │
│ • Public verification keys (A₁, A₂, ..., Aₙ) │
└─────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────┐
│ ENCRYPTION │
│ • Choose random b │
│ • Compute B = g^b, S = A^b │
│ • Derive K = SHA256(S) │
│ • Encrypt message: C = AES-GCM(K, plaintext) │
│ • Output: (B, C, nonce) │
└─────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────┐
│ THRESHOLD DECRYPTION (Phase 1) │
│ Each participating player i: │
│ • Computes hᵢ = B^(aᵢ) mod p │
│ • Generates ZKP using Chaum-Pedersen protocol │
│ • Outputs (hᵢ, proof_i) │
└─────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────┐
│ THRESHOLD DECRYPTION (Phase 2) │
│ Combiner: │
│ • Collects t+1 partial decryptions (hᵢ, proof_i) │
│ • Verifies all ZKPs │
│ • Computes Lagrange coefficients wᵢ │
│ • Reconstructs S = ∏ hᵢ^(wᵢ) mod p │
│ • Derives K = SHA256(S) │
│ • Decrypts: plaintext = AES-GCM-Decrypt(K, C) │
└─────────────────────────────────────────────────────────┘
The system uses cryptographic parameters provided by the course instructor:
- Prime p: 3072-bit safe prime
- Subgroup order q: 3071-bit prime where p = 2q + 1
- Generator g: Generator of the subgroup of order q
These parameters are hardcoded in parameters.rs for consistency and have been validated to ensure:
- p - 1 = 2q (safe prime structure)
- g^q ≡ 1 (mod p) (correct subgroup)
- g^(p-1) ≡ 1 (mod p) (Fermat's Little Theorem)
- Single trusted party generates master secret and distributes shares
- Uses Shamir's Secret Sharing with polynomial of degree t
- Security Model: Requires trust in the dealer during setup phase
- Status: Fully functional and production-ready
- Attempts to eliminate the trusted dealer
- Status: Mathematical simulation only
- Important Note: Current DKG implementation runs in a single process, providing the same security model as the Trusted Setup. True DKG would require:
- Multiple independent processes/machines
- Peer-to-peer network communication
- Verifiable Secret Sharing with commitments
- Complaint and exclusion mechanisms
Recommendation: Use Trusted Dealer Setup for actual deployments. The DKG code demonstrates understanding of the algorithm but does not provide distributed trust properties.
- Rust 1.70 or later
- Cargo (included with Rust installation)
# Clone the repository
git clone https://github.com/HeyPromaRoy/Threshold-ELGamal.git
cd Threshold-ELGamal
# Build the project
cargo build --release
# Run the program
cargo run
# Run tests
cargo run test
# Validate parameters
cargo run checkparamscargo runInitial Configuration:
========================================
WELCOME TO THRESHOLD ELGAMAL SYSTEM
WITH ZKP
========================================
--- Step 1: System Parameters ---
Loading parameters...
>> Parameters Loaded Successfully.
>> Prime P bit length: 3072
>> Prime Q bit length: 3071
>> Generator G bit length: 3072
Choose Key Generation Method:
========================================
KEY GENERATION METHOD
========================================
1. Distributed Key Generation (DKG)
2. Trusted Setup
Select option (1 or 2): 2 ← Recommended
Configure System Parameters:
Enter number of players (e.g., 5): 6
Enter threshold t (need t+1 players to decrypt, e.g., 2): 2
Generated Files:
public_keys.json— Master public key and player public keys (safe to share)keys/player_1_secret.jsonthroughkeys/player_6_secret.json— Secret shares (keep secure!)
From the main menu, select Option 1:
========================================
MAIN MENU
========================================
1. Encrypt message
2. Decrypt message (Phase 1 - Generate shares)
3. Decrypt message (Phase 2 - Combine shares)
4. Exit
Select option (1-4): 1
Choose Input Method:
--- Encryption ---
1. Type message
2. Read from file (message.txt)
Select option (1 or 2): 1
Enter message to encrypt: This is a secret message!
Result:
>> Encryption successful!
>> Ciphertext saved to 'ciphertext.json'
Select Option 2 from the main menu:
--- Decryption Phase 1: Generate Shares ---
Enter player IDs to participate (e.g., 1,3,5): 2,4,6
>> Participating players: [2, 4, 6]
>> Generating partial decryptions...
-> Player 2 share saved to 'player_2_share.json'
-> Player 4 share saved to 'player_4_share.json'
-> Player 6 share saved to 'player_6_share.json'
>> Phase 1 Complete. 3 shares generated.
Each JSON file contains:
- Partial decryption value (hᵢ = B^(aᵢ) mod p)
- Zero-knowledge proof (challenge and response)
Select Option 3 from the main menu:
--- Decryption Phase 2: Combine Shares ---
>> System requires at least 3 player(s) to decrypt (threshold + 1)
>> You have 3 shares available
Which player are you? (enter player ID): 2
>> You are Player 2
Enter the OTHER player IDs who will merge with you (comma-separated): 4,6
Decryption Process:
========================================
INITIATING DECRYPTION
========================================
>> Players merging: [2, 4, 6]
>> Total players: 3 (threshold requires 3)
>> Combining partial decryptions...
>> Verifying ZKPs...
[OK] ZKP verified for Player 2
[OK] ZKP verified for Player 4
[OK] ZKP verified for Player 6
========================================
DECRYPTION SUCCESSFUL!
========================================
Decrypted Message: "This is a secret message!"
========================================
The project includes a comprehensive test suite that validates all cryptographic operations.
cargo run test-
** Lagrange Coefficient Calculation**
- Verifies Lagrange interpolation with players {1, 3, 5}
- Confirms reconstruction property holds
-
** Encryption/Decryption with Small Parameters**
- Uses toy parameters (p=23, q=11, g=2) for manual verification
- Tests complete encrypt-decrypt cycle
-
** Trusted Dealer — Full Workflow**
- Uses instructor-provided parameters
- Tests 5 players with threshold 2
- Verifies decryption with players {1, 3, 5}
-
** DKG Simulation — Full Workflow**
- Demonstrates DKG mathematical algorithm
- Successfully completes encrypt-decrypt cycle
-
** All Player Combinations**
- Tests multiple combinations of threshold+1 players
- Verifies that threshold players (t, not t+1) cannot decrypt
- Confirms threshold enforcement works correctly
All tests pass successfully!
Insufficient Players: Fewer than t+1 players cannot decrypt
Dishonest Decryption: ZKPs ensure players provide correct partial shares
Eavesdropping: ElGamal-based key exchange protects against passive observers
Message Tampering: AES-GCM provides authenticated encryption
Trusted Dealer: In Trusted Setup mode, the dealer knows the master secret initially
DKG Simulation: Current DKG doesn't provide true distributed trust (runs in one process)
Side Channels: No protection against timing attacks or physical observation
Post-Quantum: Vulnerable to quantum computers (discrete log assumption)
- Implement true DKG with network communication between independent parties
- Add secure channels (TLS) for share distribution
- Implement more robust error handling and logging
- Consider post-quantum alternatives (lattice-based schemes)
- Add protection against side-channel attacks
- Implement secure key erasure after use
threshold-elgamal/
├── src/
│ ├── main.rs # Interactive menu system and main flow
│ ├── parameters.rs # Cryptographic parameters (from instructor)
│ ├── keygenerator.rs # Key generation (Trusted Setup + DKG simulation)
│ ├── encryption.rs # Hybrid ElGamal-AES encryption
│ ├── decryption.rs # Threshold decryption with ZKP verification
│ ├── utilis.rs # Lagrange coefficient calculation
│ ├── test_mode.rs # Comprehensive test suite
│ └── check_params.rs # Parameter validation utility
├── keys/ # Generated secret shares (gitignored)
├── Cargo.toml # Project dependencies
└── README.md # This file
project-root/
├── keys/
│ ├── player_1_secret.json # Player 1's secret share (KEEP SECURE)
│ ├── player_2_secret.json # Player 2's secret share (KEEP SECURE)
│ └── ... # One file per player
├── public_keys.json # Master & player public keys (safe to share)
├── ciphertext.json # Encrypted message with B value
├── player_1_share.json # Player 1's partial decryption + ZKP
├── player_2_share.json # Player 2's partial decryption + ZKP
└── ... # One share file per participating player
I chose hybrid encryption (ElGamal + AES) rather than pure ElGamal because:
- Size Limitation: Pure ElGamal can only encrypt messages smaller than the group size
- Efficiency: Symmetric encryption (AES) is much faster for large messages
- Standard Practice: This is how modern cryptosystems work (e.g., PGP, TLS)
I selected this protocol because:
- Perfect Fit: Proves knowledge of discrete log in two bases simultaneously
- Non-Interactive: Using Fiat-Shamir heuristic, no back-and-forth needed
- Efficient: Only requires modular exponentiations
- Well-Studied: Standard protocol with proven security
- Security: SHA-256 is a cryptographically secure hash function
- Standard: Commonly used in key derivation (e.g., HKDF uses SHA-256)
- Compatibility: Well-supported in Rust crypto libraries
I separated decryption into two phases to simulate real-world usage:
- Phase 1: Each player independently computes their partial share with ZKP
- Phase 2: A combiner collects shares, verifies ZKPs, and reconstructs the message
- Rationale: In practice, players might be at different locations/times
- DKG Implementation: Not truly distributed — runs in a single process
- No Network Layer: No peer-to-peer communication implemented
- Stateless: Player state not maintained between runs
- CLI Only: Command-line interface, no GUI
- Limited Error Recovery: Minimal handling of malicious behavior
- Implement true DKG with networking (using tokio for async I/O)
- Add Feldman VSS with polynomial commitments
- Implement complaint mechanism for dishonest players
- Add session management and state persistence
- Create web interface for easier demonstration
- Support dynamic threshold changes
- Implement proactive secret sharing for long-term security
- Add post-quantum cryptography alternatives
[dependencies]
rand = "0.8" # Cryptographically secure random number generation
sha2 = "0.10" # SHA-256 hashing for key derivation
aes-gcm = "0.10" # AES-256-GCM authenticated encryption
num-bigint = "0.4" # Arbitrary precision arithmetic for large numbers
num-traits = "0.2" # Numeric traits (One, Zero, etc.)
serde = "1.0" # Serialization framework
serde_json = "1.0" # JSON serialization for file I/O
hex = "0.4" # Hexadecimal encoding utilitiesAll dependencies are from crates.io and are well-maintained by the Rust community.
This is an academic project, but suggestions and improvements are welcome! Feel free to:
- Fork the repository
- Create a feature branch (
git checkout -b feature/amazing-feature) - Commit your changes (
git commit -m 'Add amazing feature') - Push to the branch (
git push origin feature/amazing-feature) - Open a Pull Request
This project is licensed under the MIT License - see the LICENSE file for details.
- Course Instructor: For providing the cryptographic parameters and project guidance
- Rust Community: For excellent cryptographic libraries and documentation
- Academic Resources: Various papers and textbooks on threshold cryptography and zero-knowledge proofs
- Shamir, A. (1979). "How to Share a Secret"
- Pedersen, T. P. (1991). "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing"
- Chaum, D., & Pedersen, T. P. (1992). "Wallet Databases with Observers"
- ElGamal, T. (1985). "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms"
Proma Roy
Applied Cryptography Student | Pursuing MS in Cybersecurity
For questions or feedback about this project, please open an issue on GitHub.
⭐ If you found this project helpful, please consider giving it a star! ⭐
Made with ❤️ using Rust