Week 13: Anonymous Authentication
🎯 Learning Goals
By the end of this week, you should understand:
- The concept and applications of anonymous authentication
- Anonymous credentials and attribute-based systems
- Zero-knowledge proof systems for authentication
- Privacy-preserving identity verification mechanisms
📖 Theoretical Content
Introduction to Anonymous Authentication
Traditional Authentication Problems:
- Identity Disclosure: Traditional systems require revealing full identity
- Linkability: Multiple authentications can be linked to the same user
- Over-disclosure: Users must reveal more information than necessary
- Tracking: Service providers can build detailed user profiles
Anonymous Authentication Goals:
- Selective Disclosure: Reveal only necessary attributes
- Unlinkability: Different authentications cannot be linked
- Minimal Information: Prove only what’s required for access
- Privacy Preservation: Protect user identity and behavior patterns
Use Cases and Applications
Age Verification:
- Prove age ≥ 18 without revealing exact birthdate
- Access age-restricted content anonymously
- No identity disclosure to service provider
Access Control:
- Prove membership in organization without revealing identity
- Employee access without tracking individual activity
- Student discounts without university knowing purchases
Anonymous Voting:
- Prove eligibility to vote without revealing identity
- Prevent vote buying and coercion
- Enable verifiable elections with voter privacy
Healthcare Privacy:
- Prove insurance coverage without revealing medical history
- Access medical services with minimal identity disclosure
- Research participation with privacy guarantees
Anonymous Credential Systems
Basic Concept: Anonymous credentials allow users to prove possession of certified attributes without revealing their identity or enabling linkability across different uses.
Key Components:
- Issuer: Authority that grants credentials (government, employer, etc.)
- User: Individual who receives and uses credentials
- Verifier: Service that checks credential validity
- Attributes: Properties certified by the credential (age, membership, etc.)
Credential Lifecycle:
1. Registration: User proves identity to Issuer
2. Issuance: Issuer grants anonymous credential
3. Presentation: User proves attributes to Verifier
4. Verification: Verifier checks proof validity
Idemix (Identity Mixer) System
IBM’s Idemix Architecture:
1. Credential Structure:
- Based on Camenisch-Lysyanskaya signatures
- Supports multiple attributes per credential
- Enables selective disclosure and range proofs
2. Zero-Knowledge Proofs:
- Prove knowledge of valid credential without revealing it
- Show specific attributes while hiding others
- Demonstrate predicates (age ≥ 18) without exact values
3. Unlinkability:
- Each credential presentation uses fresh randomness
- Multiple uses cannot be correlated
- Perfect forward privacy
Microsoft U-Prove System
Alternative Approach:
- Based on brands signatures and discrete logarithm assumptions
- Minimal disclosure credential system
- Efficient verification and presentation
Key Features:
- Token-based: Each use consumes a token
- Selective Disclosure: Choose which attributes to reveal
- Predicate Proofs: Prove relationships between attributes
Attribute-Based Credentials (ABC)
IRMA (I Reveal My Attributes): Modern implementation of privacy-preserving authentication
Attribute Types:
# Example attribute structure
credential_attributes = {
'personal': {
'age': 25,
'nationality': 'Portuguese',
'city': 'Porto'
},
'academic': {
'university': 'University of Porto',
'degree': 'MSc Computer Science',
'student_id': 'encrypted_value'
},
'professional': {
'employer': 'Tech Company',
'role': 'Software Engineer',
'clearance_level': 'confidential'
}
}
Selective Disclosure Example:
# User wants to prove age ≥ 18 for online service
proof_request = {
'required_predicates': ['age >= 18'],
'optional_attributes': [],
'revealed_attributes': [] # Nothing else revealed
}
# System generates zero-knowledge proof
zkp = generate_age_proof(user_credential, proof_request)
# Verifier confirms age requirement without learning exact age
🔍 Detailed Explanations
Zero-Knowledge Proof Fundamentals
Definition: A zero-knowledge proof allows one party (prover) to convince another party (verifier) that they know a secret without revealing the secret itself.
Three Properties:
- Completeness: If statement is true, honest verifier will be convinced
- Soundness: If statement is false, no cheating prover can convince verifier
- Zero-Knowledge: Verifier learns nothing beyond the truth of the statement
Interactive vs Non-Interactive:
Interactive ZKP:
Prover Verifier
| |
|---- Commitment -------->|
|<----- Challenge --------|
|---- Response ---------->|
| |
Non-Interactive ZKP (using Fiat-Shamir):
def non_interactive_proof(secret, public_params):
# Generate commitment
commitment = generate_commitment(secret, random_nonce)
# Generate challenge using hash function
challenge = hash(commitment, public_params, statement)
# Generate response
response = compute_response(secret, random_nonce, challenge)
return (commitment, response) # Proof
Schnorr Identification Protocol
Basic Protocol for Proving Knowledge of Discrete Logarithm:
Setup: Public parameters (g, p, q), public key y = g^x mod p
Protocol:
class SchnorrProof:
def __init__(self, x, g, p, q):
self.x = x # Private key (secret)
self.g = g # Generator
self.p = p # Prime modulus
self.q = q # Prime order
self.y = pow(g, x, p) # Public key
def generate_proof(self):
# Step 1: Commitment
r = random.randint(1, self.q - 1)
commitment = pow(self.g, r, self.p)
# Step 2: Challenge (non-interactive)
challenge = self.hash_challenge(commitment)
# Step 3: Response
response = (r + challenge * self.x) % self.q
return (commitment, response)
def verify_proof(self, commitment, response, public_key):
challenge = self.hash_challenge(commitment)
# Verify: g^response = commitment * y^challenge
left = pow(self.g, response, self.p)
right = (commitment * pow(public_key, challenge, self.p)) % self.p
return left == right
Range Proofs
Proving Age ≥ 18 without revealing exact age:
class RangeProof:
def __init__(self, value, min_value, max_value):
self.value = value
self.min_value = min_value
self.max_value = max_value
def prove_in_range(self):
"""Prove that min_value ≤ value ≤ max_value"""
# Method 1: Bit decomposition
# Prove each bit of (value - min_value)
difference = self.value - self.min_value
bit_proofs = []
for i in range(self.bit_length(self.max_value - self.min_value)):
bit = (difference >> i) & 1
bit_proof = self.prove_bit(bit)
bit_proofs.append(bit_proof)
return bit_proofs
def prove_bit(self, bit):
"""Prove that a value is 0 or 1"""
# Using quadratic constraint: bit * (bit - 1) = 0
return self.generate_quadratic_proof(bit)
Anonymous Credential Protocols
Camenisch-Lysyanskaya Signature Scheme:
class CLSignature:
def __init__(self):
self.setup_params()
def setup_params(self):
# Generate strong RSA modulus and generators
self.n = self.generate_rsa_modulus()
self.S = self.random_qr(self.n) # Random quadratic residue
self.Z = self.random_qr(self.n)
self.R = [] # Generators for each attribute
def sign_attributes(self, attributes, secret_key):
"""Sign a set of attributes"""
# Choose random prime e and random value s
e = self.random_prime()
s = random.randint(1, self.n)
# Compute signature: A = (Z / (S^s * ∏R_i^{m_i}))^{1/e} mod n
product = pow(self.S, s, self.n)
for i, attr in enumerate(attributes):
product = (product * pow(self.R[i], attr, self.n)) % self.n
A = self.mod_inverse(product, self.n)
A = pow(A, self.mod_inverse(e, self.phi_n), self.n)
return (A, e, s)
def prove_knowledge(self, signature, revealed_attrs, hidden_attrs):
"""Generate zero-knowledge proof of signature knowledge"""
A, e, s = signature
# Randomize signature to prevent linkability
r = random.randint(1, self.n)
A_prime = (A * pow(self.S, r, self.n)) % self.n
e_prime = e
s_prime = (s + r * e) % self.order
# Generate ZK proof for the randomized signature
return self.generate_signature_proof(A_prime, e_prime, s_prime,
revealed_attrs, hidden_attrs)
💡 Practical Examples
Example 1: Anonymous Age Verification
Scenario: Online alcohol purchase requiring age ≥ 21
class AgeVerificationSystem:
def __init__(self):
self.min_age = 21
def request_age_proof(self):
return {
'requirement': f'age >= {self.min_age}',
'challenge': self.generate_challenge(),
'no_linkability': True
}
def verify_age_proof(self, proof, challenge):
# Verify zero-knowledge proof of age
if self.verify_zkp(proof, challenge):
return {'access_granted': True, 'age_disclosed': False}
else:
return {'access_granted': False, 'reason': 'Invalid proof'}
class User:
def __init__(self, age, credential):
self.age = age
self.credential = credential
def generate_age_proof(self, requirement, challenge):
if self.age >= requirement['min_age']:
# Generate ZK proof without revealing exact age
return self.create_range_proof(
value=self.age,
min_value=requirement['min_age'],
challenge=challenge
)
else:
return None # Cannot prove, insufficient age
# Usage
alice = User(age=25, credential=age_credential)
store = AgeVerificationSystem()
proof_request = store.request_age_proof()
age_proof = alice.generate_age_proof(proof_request, proof_request['challenge'])
result = store.verify_age_proof(age_proof, proof_request['challenge'])
print(f"Access granted: {result['access_granted']}")
print(f"Age disclosed: {result.get('age_disclosed', 'N/A')}")
Example 2: Anonymous Employee Access
Scenario: Company cafeteria with employee discounts
class EmployeeAccessSystem:
def __init__(self, company_name):
self.company_name = company_name
self.valid_departments = ['Engineering', 'Marketing', 'Sales', 'HR']
def request_employee_proof(self):
return {
'required_attributes': {
'employer': self.company_name,
'status': 'active'
},
'optional_attributes': ['department', 'hire_date'],
'selective_disclosure': True
}
class EmployeeCredential:
def __init__(self, employee_data):
self.attributes = employee_data
self.signature = self.get_company_signature()
def generate_selective_proof(self, request):
proof = {}
# Required attributes - must prove possession
for attr, value in request['required_attributes'].items():
if attr in self.attributes and self.attributes[attr] == value:
proof[attr] = self.prove_attribute_equality(attr, value)
else:
return None # Cannot satisfy requirement
# Optional attributes - user chooses what to reveal
for attr in request.get('optional_attributes', []):
if attr in self.attributes:
# User can choose to reveal or keep private
reveal = self.user_choice_to_reveal(attr)
if reveal:
proof[attr] = self.attributes[attr]
else:
proof[attr] = self.prove_attribute_possession(attr)
return proof
# Example usage
employee = EmployeeCredential({
'name': 'Bob Smith',
'employer': 'TechCorp',
'department': 'Engineering',
'status': 'active',
'hire_date': '2020-01-15',
'salary': 75000
})
cafeteria = EmployeeAccessSystem('TechCorp')
access_request = cafeteria.request_employee_proof()
employee_proof = employee.generate_selective_proof(access_request)
# Result: Proves employment at TechCorp with active status
# Optional: May reveal department but keeps salary private
Example 3: Anonymous Survey Participation
Scenario: Academic research requiring verified student participation
class AnonymousResearchSystem:
def __init__(self, university, study_requirements):
self.university = university
self.requirements = study_requirements
def generate_participation_token(self, student_proof):
if self.verify_student_eligibility(student_proof):
# Generate unlinkable token for survey participation
token = self.create_anonymous_token()
return {
'token': token,
'survey_url': self.get_survey_url(),
'expires': self.get_expiration_date(),
'linkable': False
}
return None
def verify_student_eligibility(self, proof):
# Check proof shows:
# 1. Valid student at this university
# 2. Meets study criteria (age, program, etc.)
# 3. Has not participated before (without linking to identity)
return True # Simplified for example
class StudentCredential:
def __init__(self, student_data):
self.attributes = student_data
self.university_signature = None
self.participation_nonce = random.randint(1, 2**128)
def prove_eligibility(self, requirements):
proof = {}
# Prove university enrollment
proof['university'] = self.prove_attribute_value(
'university', requirements['university']
)
# Prove age in required range
if 'age_range' in requirements:
proof['age_range'] = self.prove_age_in_range(
requirements['age_range']['min'],
requirements['age_range']['max']
)
# Prove program eligibility
if 'eligible_programs' in requirements:
proof['program'] = self.prove_program_membership(
requirements['eligible_programs']
)
# Prove non-participation (without revealing identity)
proof['fresh_participation'] = self.prove_fresh_participation()
return proof
# Usage example
student = StudentCredential({
'name': 'Carol Johnson',
'university': 'University of Porto',
'program': 'Computer Science',
'age': 22,
'student_id': 'encrypted_id_12345'
})
research_study = AnonymousResearchSystem(
university='University of Porto',
study_requirements={
'age_range': {'min': 18, 'max': 30},
'eligible_programs': ['Computer Science', 'Mathematics', 'Physics']
}
)
eligibility_proof = student.prove_eligibility(research_study.requirements)
participation_token = research_study.generate_participation_token(eligibility_proof)
if participation_token:
print("Anonymous participation granted")
print(f"Token: {participation_token['token'][:20]}...")
print(f"Identity revealed: No")
print(f"Can be linked to other responses: {participation_token['linkable']}")