End-to-End Crypto and Identity Verification Protocols at University College London

Dr George Danezis University College London, UK

LECTURES 5/10 LABS 3/5 End-to-End crypto Anonymous Comms. Private Computations Zero-knowledge Data Protection (Kosta) End-to-end crypto Anonymous Comms. Computations Zero-Knowledge Credentials Credentials Human Aspects (Sasse) Storage Data Anonymization Case Studies Note: Guest topics are examinable!

Given the commitment on secrets x, y, z, o: C = g1x g2y g3z g4o 1. What is the procedure to prove and verify non- interactively the statement: NIZK{(x, y, z, o): C = g1x g2y g3z g4o and z = 10 x - 5 y - 1} 2. What is the procedure to prove and verify non- interactively the statement: NIZK{(x, y, z, o): C = g1x g2y g3z g4o and x=y and z=10}

Identity as a proxy to check credentials Username decides access in Access Control Matrix Sometimes this leaks too much information Real world examples Tickets allow you to use cinema / train Bars require customers to be older than 18 But do you want the barman to know your address?

Usual way: Identity provider certifies attributes of a subject. Relying Party checks those attributes Match credential with live person (biometric) Examples: E-passport: signed attributes, with lightweight access control. Attributes: nationality, names, number, pictures, ... Identity Cards: signatures over attributes Attributes: names, date of birth, picture, address, ... UCL student card: Attributes: Name, status (student, staff), building access rights,

The players: Issuer (I) = Identity provider Prover (P) = Subject Verifier (V) = Relying party Properties: The prover convinces the verifier that he holds a credential with attributes that satisfy some boolean formula: Simple example age=18 AND city=Cambridge Prover cannot lie Verifier cannot infer anything else aside the formula Anonymity maintained despite collusion of V & I

Name=Peggy, age=25, address=Cambridge, Status=single 1. Issuing protocol: Prover gets a certified credential. Cannot learn anything beyond age Issuer Passport Issuing Authority 2. Showing Protocol: Prover makes assertions about some attributes Verifier Prover Victor (Bar staff Checking age) Peggy age=25

Single-show credential (Brands & Chaum) Blind the issuing protocol Show the credential in clear Multiple shows are linkable BAD Multi-show (Camenisch & Lysyanskaya) Random oracle free signatures for issuing (CL) Blinded showing Prover shows that they know a signature over a particular ciphertext. Cannot link multiple shows of the credential More complex BAD Algebraic Message Authentication Codes (MAC) (Meiklejohn et al. 2014) Restriction: Issuer = Verifier Special case Blinded proof of validity of MAC Fast and elegant!

Cryptographic Reminders (see ZK topic!) The discrete logarithm problem Schnorr s Identification protocol Proof of DL representations Linear relations of attributes Algebraic MACs Vanilla KeyGen, MAC, verification no privacy Credential issuing with privacy Credential showing with privacy

Assume multiplicative notation. Exponentiation is computationally easy: Given g and x, easy to compute gx But logarithm is computationally hard: Given g and gx, difficult to find x = logg gx If p is large it is practically impossible Related DH problem Given (g, gx, gy) difficult to find gxy Stronger assumption than DL problem

Schnorrs Identification protocol / Signature Private x, public g, y = gx Prover shows they know x in Zero-Knowledge (ZK) Fiat-Shamir heuristic makes it non-interactive Generalized proofs of DL representation Private xi, public gi, y = gixi Prover shows they know xi in ZK ZK Tricks: Notation: NIZK{(secrets): statements} Proof of equality of secrets (use same witness, response) Proof of linear relations (substitute for equals into repr.)

MAC (Message Authentication Code) Traditionally a symmetric cryptography primitive 2 inputs, 1 output Input 1: a secret key Input 2: a message Output: a tag Security properties: If the adversary does not know the key, the MAC function acts as a random function. Traditional uses: Integrity protection between Alice and Bob. Integrity protection of cookies on remote browsers.

Secret MAC key K 1. Issuing protocol: Prover gets a certified credential. Credential (C), MACK(C) Issuer = Verifier 2. Showing Protocol: Prover makes assertions about some attributes Prover Credential (C), MACK(C) Integrity: Prover cannot forge Credential. No Privacy.

Secret MAC key K 1. Issuing protocol: Prover gets a certified credential. Credential (C), MACK(C) Issuer = Verifier (Victor) 2. Showing Protocol: Prover makes assertions about some attributes Prove in ZK that: (1) You have some attributes; (2) and a valid MAC on them. Anonymous channel Prover (Peggy) Integrity: Prover cannot forge Credential. Privacy!

Prover does not know secret MAC key K Otherwise they could forge credentials! Anonymity Set concerns: Prover need to make sure all credentials use the same MAC key. Otherwise MAC key betrays who Prover is. No bitstring in the issuing must be linkable to any bitstring in the showing protocol. Anonymous channel: Make sure other identifiers cannot link the transactions. Independent concern however important!

Invented by Sarah Meiklejohn (UCL) et al. (2014) MACs with nice properties, allowing: efficient proofs of correct MAC creation (issuing) efficient proofs of correct MAC possession (showing) 3 MAC protocols (in clear): Parameter Generation Key Generation MAC generation, verification Chase, Melissa, Sarah Meiklejohn, and Greg Zaverucha. "Algebraic MACs and keyed-verification anonymous credentials." Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2014.

Assume public g, h that generate a group G of prime order p. DL / DH is assumed hard, etc. Generate secrets: sk = {xo, x1, , xk} Where k: number of attributes to encode Public Issuer parameters: To facilitate proofs later. Publish: iparams = {Xi = hxi}for i > 0

Algebraic MACs take as inputs: The secret sk = {xo, x1, , xk} A sequence of k attributes m = { mi } for 0 i k to MAC MAC generation: Random u G / {1} Compute u = uHsk(m) where Hsk(m) = xo + mi xi Output tag = (u, u )

Given (u, u) is that a valid MAC for m = { mi } ? Need to use sk = {xo, x1, , xk} Verification algorithm: Check u = uHsk(m) where Hsk(m) = xo + mi xi Note: Both MAC generation & verification require sk Verification reveals u, u , mi, not private!

What is to be done: Embed attributes as MAC messages mi Define a way to prove knowledge of a valid MAC in ZK Algorithms / Protocols: Setup defines all system parameters. CredKeygen generates issue keys, public keys. Credential Issuance protocol (proof + verification) Credential Showing protocol (proof + verification)

Setup Algorithm Output (G, p, g, h) as for the aMAC CredKeygen algorithm: Run MAC key gen. and get: sk = {x0, , xk}, iparam = {X1, , Xk} Random oxo in Zp Compute commitment Cxo = gxohoxo Output public (iparam, Cxo) & private (sk, oxo)

Insight: encode attributes as messages mi Issuer computes: Tag (u, u ) = MAC(sk, { mi }) Proof 0 = NIZK{ (sk = { xi }, oxo): u = uxo (umi)xi Cxo = gxohoxo Xi = hxi for 0 < i < k+1 } Output (u, u ), 0 Remember: these stay secret and and Note: proofs of knowledge of DL representations and equality! Prover Peggy get (u,u ), verify 0

See Appendix E of: Chase, M., S. Meiklejohn, and G. M. Zaverucha. "Algebraic MACs and Keyed-Verification Anonymous Credentials . eprint, 2013/516, 2013. The aMAC and credential scheme used is the one referred to a MACGGM.

Now the Prover (Peggy) tries to convince Victor / Issuer she holds a credential Prover computes: Random a in Zp and ua ,ua = (ua, u a) Random zi in Zp and Cmi=umihzi Random r in Zp and Cu = ua gr Prove: 1 = NIZK{(zi, r, mi): Cmi=umihzi V = g-r Xizi+ } Output (ua , Cmi , Cu ), 1 Blinding all linkable elements with random ones. Note: proofs of knowledge of DL representations and equality! Prove here any other statement about the attributes.

Victor (Verifier / Issuer): Compute V = uax0 Cmixi / Cu Verify 1 using V Reconstruct V does that work? Result: All revealed values are randomized. ZK proof does not leak anything identifying Unlinkability between Issuing & Showing Availability of commitments Cmi to prove statements on the attributes. Done.

Attributes (mi) may be kept secret when issuing. Include a secret to restrict use. Include secrets from other credentials. (eg. consolidate attributes from 2 sources) Include secret sequence number. Combine credentials with encryptions. Allows for revocation of anonymity. (Cipher text of name) Note: Benaloh Variant is re-randomizable.

Attribute based access control Service encodes capabilities of a user as attributes. When it comes to access control decision, the user proves that they possess a capability without revealing who they are. Example: I have the right to post in the group UCL InfoSec without telling the service who exactly I am.

Federated identity management A service may provide you with an identity, that you can show to other services to login. Example: Implement equivalent of Facebook Connect or Google login , by encoding your service attributes to a credential, and using this to prove your service identity to third parties. Multi-show perfect; single-show require multiple issuing; aMAC require on-line checks.

Privacy friendly e-identity Government issues you with Id-cards & e-passports with usual attributes (Name, age, gender, address, driving licence, profession, ) You may use the credentials to access restricted services or rebates. Example: can only buy a drink if you are over 18; can get a cheaper rate at the swimming pool if you are a local resident; can access the library if you are a UCL student. Without revealing anything more.

Electronic cash Issuer gets from you 1 and provides you a credential for spending 1. You spend the coin by showing the credential. Example: You charge your laundry cash card with 10 pounds; you may then insert it into the washing machines and run the showing protocol to get a wash. No one knows how often or where you do your washing. Key: need to implement double spending prevention!

Rate limiting and abuse control You get a ticket that entitles you to a certain number of entries to a place, or a service. You should not be able to use it more! Key: rate limiting! Example: You want to implement an anonymous video- on-demand service, but wish to limit the number of movies per day one may download. You issue credentials, and require people to show them for every download. Example: You want to allow people to anonymously comment on a blog, but not to flood it. You give them a credential, but rate limit the number of comments / edits per day.

Derive from the attribute a fixed string. Check it for duplication. Eg. Credential (Name, secret, ). Define hday = H(day) Publish Tagday = hday1/(secret+n) And NIZK{(secret): Cred( , secret, ) and Tagday(secret+n) = hday} When checking proof: ensure Tagday has not been seen before and 0 <= n < N

Core: Claus P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4:161 174, 1991. Stefan Brands. Rethinking public key infrastructures and digital certificates building in privacy. MIT Press. More: Jan Camenisch and Markus Stadler. Proof systems for general statements about discrete logarithms. Technical report TR 260, Institute for Theoretical Computer Science, ETH, Zurich, March 1997. Jan Camenisch and Anna Lysianskaya. A signature scheme with efficient proofs. (CL signatures)