Anonymous Credentials Jan Camenisch IBM Research – Zurich @jancamenisch www.camenisch.org/eprivacy August 11, 2015 © 2014 IBM Corporation Houston, we have a problem! ﾩ 2 © 2014 IBM Corporation Houston, we have a problem! ﾩ “Buzz Aldrin's footprints are still up there” (Robin Wilton) 3 © 2014 IBM Corporation Computers don't forget ! Data storage ever cheaper → “store by default” – also collateral collection, surveillance cameras, Google Street View with wireless traffic, Apple location history,... ! Data mining ever better – self-training algorithms cleverer than their designers – not just trend detection, even prediction, e.g., flu pandemics, ad clicks, purchases,… – what about health insurance, criminal behavior? ! The world as we know it – Humans forget most things too quickly – Paper collects dust in drawers We build apps with the paper-based world in mind :-( – if it works it works – security too often still an afterthought – implementors too often have no crypto education 4 © 2014 IBM Corporation Where's all my data? The ways of data are hard to understand ! Devices, operating systems, & apps are getting more complex and intertwined – Mashups, Ad networks – Not visible to users, and experts – Data processing changes constantly ! And the cloud makes it worse... – Processing machines can be moved around w/out borders Far too easy to lose (control over) data and to collect data! 5 © 2014 IBM Corporation You have no privacy, get over it .....?!? … “The NSA has all our data anyway” … “I have nothing to hide!” ! Huge security problem! – Millions of hacked passwords (100'000 followers $115 - 2013) – Stolen identities ($150 - 2005, $15 - 2009, $5 – 2013) ! Difficult to put figures down – Credit card fraud – Spam & marketing – Manipulating stock ratings, etc.. – (Industrial) espionage ! We know secret services can do it easily, but they are not the only ones – but this is not about homeland security – and there are limits to the degree of protection that one can achieve ! last but not least: data are the new money, so they need to be protected! 6 © 2014 IBM Corporation Privacy – a lost case? No, but we need paradigm shift & build stuff for the moon rather than the sandy beach! 7 © 2014 IBM Corporation Need to protect our data! ! devices, sensors, etc cannot all be physically protected – – authentication of all devices authentication of all data ...makes it even worse :-( ! data cannot be controlled – – – 8 minimize information encrypt information attach usage policies to each bit © 2014 IBM Corporation So what can we do ! Legal approach – Regulate what information can be collected – How to collect it – How to use and protect it – Issue fines for misbehavior – Very different for different countries and cultures ! Technological approach – Protect data by encryption – Govern data by policies – Minimize data that needs to be used August 11, 2015 © 2014 IBM Corporation of course there are limits... ! tracing is so easy – each piece of hardware is quite unique – log files everywhere ! …. but that's not the point! – it's not about NSA et al. – active vs. passive “adversaries” ..... still, privacy August 11, 2015 by design! © 2014 IBM Corporation Our Vision In the Information Society, users can act and interact in a safe and secure way while retaining control of their private spheres. © 2014 IBM Corporation PETs Can Help! Privacy, Identity, and Trust Mgmt Built-In Everywhere! ! Network Layer Anonymity – ... in mobile phone networks – ... in the Future Internet as currently discussed – ... access points for ID cards ! Identification Layer – Access control & authorization ! Application Layer – “Standard” e-Commerce – Specific Apps, e.g., eVoting, OT, PIR, ..... – Web 2.0, e.g., Facebook, Twitter, Wikis, .... 12 © 2014 IBM Corporation Privacy at the Authentication Layer Authentication without identification 13 August 11, 2015 © 2014 IBM Corporation What is an identity & identity management? language skills work marital status phone number salary credit card number shopping hobbies public authority name address birth date insurance nick name leisure blood group health status health care ! ID: set of attributes shared w/ someone – attributes are not static: user & party can add ! ID Management: two things to make ID useful – authentication means – means to transport attributes between parties 14 August 11, 2015 © 2014 IBM Corporation Let's see a scenario 15 August 11, 2015 © 2014 IBM Corporation Alice wants to watch a movie at Mplex I wish to see Alice in Wonderland Alice Movie Streaming Service © 2014 IBM Corporation Alice wants to watch a movie at Mplex You need: - subscription - be older than 12 Alice Movie Streaming Service © 2014 IBM Corporation Watching the movie with the traditional solution ok, here's - my eID - my subscription Alice Movie Streaming Service © 2014 IBM Corporation Watching the movie with the traditional solution Aha, you are - Alice Doe - born on Dec 12, 1975 - 7 Waterdrive - CH 8003 Zurich - Married - Expires Aug 4, 2018 Mplex Customer - #1029347 - Premium Subscription - Expires Jan 13, 2016 Alice Movie Streaming Service © 2014 IBM Corporation Watching the movie with the traditional solution This is a privacy and security problem! • - identity theft • - profiling • - discrimination Aha, you are - Alice Doe - born on Dec 12, 1975 - 7 Waterdrive - CH 8003 Zurich - Married - Expires Aug 4, 2018 Mplex Customer - #1029347 - Premium Subscription - Expires Jan 13, 2016 Alice Movie Streaming Service © 2014 IBM Corporation Watching the movie with the traditional solution With OpenID and similar solution, e.g., log-in with Facebook Alice Movie Streaming Service 21 August 11, 2015 © 2014 IBM Corporation Watching the movie with the traditional solution With OpenID and similar solution, e.g., log-in with Facebook Aha, Alice is watching a 12+ movie Alice Movie Streaming Service 22 August 11, 2015 © 2014 IBM Corporation Watching the movie with the traditional solution With OpenID and similar solution, e.g., log-in with Facebook Aha, Alice is watching a 12+ movie Aha, you are - [email protected] - born on Dec 12, 1975 - Alice's friends are .... - Alice's public profile is ... Mplex Customer - #1029347 - Premium Subscription - Expires Jan 13, 2016 Alice Movie Streaming Service 23 August 11, 2015 © 2014 IBM Corporation Identity Mixer solves this. When Alice authenticates to the Movie Streaming Service with Identity Mixer, all the services learns is that Alice has a subscription is older than 12 and no more. © 2014 IBM Corporation Privacy-protecting authentication with IBM Identity Mixer Like PKI, but better: ! One secret Identity (secret key) ! Many Public Pseudonyms (public keys) August 11, 2015 © 2014 IBM Corporation Privacy-protecting authentication with IBM Identity Mixer Like PKI, but better: ! Issuing a credential Name = Alice Doe Birth date = April 3, 1997 August 11, 2015 © 2014 IBM Corporation Privacy-protecting authentication with Privacy ABCs Alice Movie Streaming Service 27 August 11, 2015 © 2014 IBM Corporation Privacy-protecting authentication with IBM Identity Mixer I wish to see Alice in Wonderland You need: - subscription - be older than 12 Alice Movie Streaming Service 28 © 2014 IBM Corporation Privacy-protecting authentication with IBM Identity Mixer Alice Movie Streaming Service 29 © 2014 IBM Corporation Privacy-protecting authentication with IBM Identity Mixer I wish to see Alice in Wonderland You need: - subscription - be older than 12 Alice Movie Streaming Service 30 © 2014 IBM Corporation Privacy-protecting authentication with IBM Identity Mixer Like PKI ! but does not send credential ! only minimal disclosure Alice - valid subscription - eID with age ≥ 12 Movie Streaming Service August 11, 2015 © 2014 IBM Corporation Privacy-protecting authentication with IBM Identity Mixer Like PKI ! but does not send credential ! only minimal disclosure (Public Verification Key of issuer) Aha, you are - older than 12 - have a subscription Alice Movie Streaming Service 32 August 11, 2015 © 2014 IBM Corporation Advantages of Identity Mixer ! For Users: privacy – minimizing disclosure of personal data – keeping their identities safe – pseudonymous/anonymous access ! For Service Providers: security, accountability, and compliance – avoiding the risk of loosing personal data if it gets stolen – compliance with legislation (access control rules, personal data protection) – strong authentication (cryptographic proofs replace usernames/passwords) – user identification if required (under certain circumstances) 33 © 2014 IBM Corporation Demo Try yourself at www.ibm.biz/identitymixer on Privacy Day (January 28) © 2014 IBM Corporation Further Concepts 35 August 11, 2015 © 2014 IBM Corporation Concept – Inspection TTP • If car is damaged: ID with insurance or gov't needs be retrieved • Similarly: verifiably encrypt any certified attribute (optional) • TTP is off-line & can be distributed to lessen trust 36 August 11, 2015 © 2014 IBM Corporation Concept – Revocation Revocation authority parameters (public key) Revocation info • If Alice was speeding, license needs to be revoked! • There are many different use cases and many solutions • Variants of CRL work (using crypto to maintain anonymity) • Accumulators • Signing entries & Proof, .... • Limited validity – certs need to be updated • ... For proving age, a revoked driver's license still works 37 August 11, 2015 © 2014 IBM Corporation Concept – Usage Limitation Degree of anonymity can be limited: ! If Alice and Eve are on-line at the same time, they are caught! ! Use Limitation – anonymous until: – If Alice used certs > 100 times total... – ... or > 10'000 times with Bob ! Alice's cert can be bound to hardware token (e.g., TPM) 38 August 11, 2015 © 2014 IBM Corporation A couple of use cases 39 August 11, 2015 © 2014 IBM Corporation Age verification Proving 12+, 18+, 21+ without disclosing the exact date of birth – privacy and compliance with age-related legislation ! Movie streaming services ! Gaming industry ! Online gambling platforms ! Dating websites ! Social benefits for young/old people 40 © 2014 IBM Corporation Healthcare Anonymous treatment of patients (while enabling access control and payments) ! Anonymous access to patients' records – accessing medical test results ! Anonymous consultations with specialists – online chat with a psychologist – online consultation with IBM Watson ! Eligibility for the premium health insurance – proving that the body mass index (BMI) is in the certain range without disclosing the exact weight, height, or BMI 41 © 2014 IBM Corporation Subscriptions, membership Who accesses which data at which time can reveal sensitive information about the users (their research strategy, location, habits, etc.) ! Patent databases ! DNA databases ! News/Journals/Magazines ! Transportation: tickets, toll roads ! Loyalty programs ??? 42 © 2014 IBM Corporation Polls, recommendation platforms Providing anonymous, but at the same time legitimate feedback ! Online polls – applying different restrictions on the poll participants: location, citizenship ! Rating and feedback platforms – anonymous feedback for a course only from the students who attended it – wikis – recommendation platforms 43 © 2014 IBM Corporation Towards Realizing Anonymous Creds 44 August 11, 2015 © 2014 IBM Corporation An Software Stack View on Identity Mixer application layer resource request presentation policy presentation token Wallet AC & app logic store policy layer crypto layer policy credential matcher evidence gen. orchestration store credential mgr Sig Enc ... Com ... ZKP policy token matcher store evidence verif. orchestration token mgr Sig Enc ... Com ... ZKP © 2014 IBM Corporation Privacy-protecting authentication with Privacy ABCs (Issuer parameter) Credential specification Pseudonym Credential 12 < age Presentation token Presentation policy (Verifier paramet 46 August 11, 2015 © 2014 IBM Corporation The Policy Layer – An Example: Presentation policy <abc:PresentationPolicy PolicyUID="https://movies...com/presentationpolicies/movie1"> <abc:Message> <abc:ApplicationData> Terms and Conditions </abc:ApplicationData> </abc:Message> <abc:Credential Alias="#voucher"> <abc:CredentialSpecAlternatives> <abc:CredentialSpecUID>https://movies.....com/specifications/voucher</abc:CredentialSpecUID> </abc:CredentialSpecAlternatives> <abc:IssuerAlternatives> <abc:IssuerParametersUID>https://movies....com/parameters/voucher</abc:IssuerParametersUID> </abc:IssuerAlternatives> </abc:Credential> <abc:AttributePredicate Function="urn:oasis:names:tc:xacml:1.0:function:dateTime-geq"> <abc:Attribute CredentialAlias="#voucher" AttributeType="Expires" /> <abc:ConstantValue>2014-06-17T14:06:00Z</abc:ConstantValue> </abc:AttributePredicate> presentation policy </abc:PresentationPolicy> presentation token User 47 August 11, 2015 Verifier © 2014 IBM Corporation So let's look at the cryptography 48 August 11, 2015 © 2014 IBM Corporation Required Technologies Signature Schemes Encryption Schemes Zero-Knowledge Proofs Commitment Schemes ..... challenge is to do all this efficiently! August 11, 2015 © 2014 IBM Corporation zero-knowledge proofs 50 August 11, 2015 © 2014 IBM Corporation Zero-Knowledge Proofs ! interactive proof between a prover and a verifier about the prover's knowledge Commitment Challenge Response ! properties: zero-knowledge verifier learns nothing about the prover's secret proof of knowledge (soundness) prover can convince verifier only if she knows the secret completeness if prover knows the secret she can always convince the verifier 51 August 11, 2015 © 2014 IBM Corporation Zero Knowledge Proofs of Knowledge of Discrete Logarithms Given group <g> and element y Є <g> . Prover wants to convince verifier that she knows x s.t. y = gx such that verifier only learns y and g. Prover: x random r t := gr t c s := r - cx y, g Verifier: s random c t = g s yc ? notation: PK{(α): y = gα } 52 August 11, 2015 © 2014 IBM Corporation Zero Knowledge Proofs Proof of knowledge: if a prover can successfully convince a verifier, then the secret need to be extractable. Prover might do protocol computation in any way it wants & we cannot analyse code. Thought experiment: ! Assume we have prover as a black box → we can reset and rerun prover ! Need to show how secret can be extracted via protocol interface x t t c c' x s t = gs yc = gs' yc' → yc'-c = gs-s' → y = g(s-s')/(c'-c) → August 11, 2015 s' x = (s-s')/(c'-c) mod q © 2014 IBM Corporation Zero Knowledge Proofs: Security Zero-knowledge property: If verifier does not learn anything (except the fact that Alice knows x = log g y ) Idea: One can simulate whatever Bob “sees”. Choose random c', s' compute t := g s' c' y if c = c' send s' = s , otherwise restart t c s Problem: if domain of c too large, success probability becomes too small August 11, 2015 © 2014 IBM Corporation Zero Knowledge Proofs of Knowledge of Discrete Logarithms One way to modify protocol to get large domain c: Prover: x random r t := gr h = H(c,v) ? s := r - cx y, g Verifier: h t random c,v h := H(c,v) c,v s t = g s yc ? notation: PK{(α): y = gα } 55 August 11, 2015 © 2014 IBM Corporation Zero Knowledge Proofs: Security One way to modify protocol to get large domain c: Choose random c', s' compute t' := gs' yc' after having received c “reboot” verifier Choose random s compute t := gs yc send s h t' c,v h t c,v s August 11, 2015 © 2014 IBM Corporation Zero Knowledge Proofs of Knowledge of Discrete Logarithms Given group <g> and element y Є <g> . Prover wants to convince verifier that she knows x s.t. y = gx such that verifier only learns y and g. Prover: x random r t := gr t c s := r - cx y, g Verifier: s random c t = g s yc ? notation: PK{(α): y = gα } 57 August 11, 2015 © 2014 IBM Corporation From Protocols To Signatures Signature SPK{(α): y = gα }(m): Signing a message m: - chose random r Є Zq and - compute c := H(gr||m) = H(t||m) s := r - cx mod (q) - output (c,s) Verifying a signature (c,s) on a message m: - check c = H(gs yc||m) ? 58 ↔ t = gs y c ? Security: - underlying protocol is zero-knowledge proof of knowledge - hash function H(.) behaves as a “random oracle.” August 11, 2015 © 2014 IBM Corporation Zero Knowledge Proofs of Knowledge of Discrete Logarithms Many Exponents: PK{(α,β,γ,δ): y = gα hβzγkδuβ } Logical combinations: PK{(α,β): y = gα ∧ z = gβ ∧ u = gβhα } PK{(α,β): y = gα ∨ z = gβ } Intervals and groups of different order (under SRSA): PK{(α): y = gα ∧ α Є [A,B] } PK{(α): y = gα ∧ z = gα ∧ α Є [0,min{ord(g),ord(g)}] } Non-interactive (Fiat-Shamir heuristic, Schnorr Signatures): SPK{(α): y = gα }(m) 59 August 11, 2015 © 2014 IBM Corporation Some Example Proofs and Their Analysis Let g, h, C1, C2, C3 be group elements. Now, what does PK{(α1,β1,α2,β2, α3, β3): C1= gα1hβ1 ∧ C2= gα2hβ2 ∧ C3 =gα3hβ3∧ C3 = gα1gα2hβ3 } mean? → Prover knows values α1, β1, α2, β2, β3 such that C1= gα1hβ1 , C2= gα2hβ2 and C3 = gα1gα2hβ3 = gα1 + α2 hβ3 = g α3 hβ3 → α3 = a1 + a2 (mod q) And what about: PK{(α1,...,β3): → C1= gα1hβ1 ∧ C2= gα2hβ2 ∧ C3 =gα3hβ3 ∧ C3 = gα1 (g5)α2hβ3 } C3 = gα1gα2hβ3 = gα1 + 5 α2 hβ3 → a3 = a1 + 5 a2 60 August 11, 2015 (mod q) © 2014 IBM Corporation Some Example Proofs and Their Analysis Let g, h, C1, C2, C3 be group elements. Now, what does C1= gα1hβ1 ∧ C2= gα2hβ2 ∧ C3 =gα3hβ3 ∧ C3 = C2α1hβ3 } mean? PK{(α1,..,β3): → Prover knows values α1, β1, α2, β2, β3 such that C1= gα1hβ1 , C2= gα2hβ2 and C3 = C2α1hβ3 = (gα2hβ2)α1hβ3 = gα2·α1hβ3+β2·α1 C3 = gα2·α1 hβ3+β2·α1 = gα3 hβ3' → a3 = a1 · a2 (mod q) And what about PK{(α1,β1 β2): C1= gα1hβ1 ∧ C2= gα2hβ2 ∧ C2 = C1α1hβ2 } → a2 = a12 (mod q) 61 August 11, 2015 © 2014 IBM Corporation Some Example Proofs and Their Analysis Let g, h, C1, C2, C3 be group elements. Now, what does PK{(α1,..,β2): C1= gα1hβ1 ∧ C2= gα2hβ2 ∧ g = (C2/C1)α1hβ2 } mean? → Prover knows values α, β1, β2 such that C1= gα1hβ1 g = (C2/C1)α1hβ2 = (C2 g-α1h-β1)α1 hβ2 → g1/α1 = C2 g-α1h-β1 hβ2/α1 C2 = gα1 hβ1 h-β2/α1 g1/α1 = gα1 + 1/α1 hβ1-β2/α1 C2 = gα2 hβ2 α2 = α1 + a1-1 (mod q) 62 August 11, 2015 © 2014 IBM Corporation Privacy-protecting authentication with Privacy ABCs commitment scheme signature scheme Alice zero-knowledge proofs 63 August 11, 2015 © 2014 IBM Corporation signature schemes 64 August 11, 2015 © 2014 IBM Corporation Signature Scheme: Functionality Key Generation August 11, 2015 © 2014 IBM Corporation Signature Scheme: Functionality Signing (m1,..., mk) σ = sig((m1,..., mk), ) August 11, 2015 © 2014 IBM Corporation Signature Scheme: Functionality Verification (m1,..., mk) σ σ = sig((m1,..., mk), ) ver(σ,(m1,..., mk), ) = true August 11, 2015 © 2014 IBM Corporation Signature Scheme: Security Unforgeability under Adaptive Chosen Message Attack m1 August 11, 2015 σ1 © 2014 IBM Corporation Signature Scheme: Security Unforgeability under Adaptive Chosen Message Attack m1 ml August 11, 2015 σ1 σl © 2014 IBM Corporation Signature Scheme: Security Unforgeability under Adaptive Chosen Message Attack m1 ml σ1 σl σ' and m'≠ mi s.t. ver(σ', m', August 11, 2015 ) = true © 2014 IBM Corporation Signature Scheme: Security Unforgeability under Adaptive Chosen Message Attack m1 ml σ1 σl σ' and m'≠ mi s.t. ver(σ', m', August 11, 2015 ) = true © 2014 IBM Corporation RSA Signature Scheme – for reference Rivest, Shamir, and Adlemann 1978 Secret Key: two random primes p and q Public Key: n := pq, prime e, and collision-free hash function H: {0,1}* -> {0,1}ℓ Computing signature on a message m Є {0,1}* d := 1/e mod (p-1)(q-1) s := H(m) d mod n Verification of signature s on a message m Є {0,1}* se = H(m) Correctness: se = (H(m)d)e = H(m)d·e = H(m) 72 August 11, 2015 (mod n) (mod n) © 2014 IBM Corporation RSA Signature Scheme – for reference Verification signature on a message m Є {0,1}* se := H(m) (mod n) Wanna do proof of knowledge of signature on a message, e.g., PK{ (m,s): se = H(m) (mod n) } But this is not a valid proof expression!!!! :-( 73 August 11, 2015 © 2014 IBM Corporation CL-Signature Scheme Public key of signer: RSA modulus n and ai, b, d Є QRn, Secret key: factors of n To sign k messages m1, ..., mk Є {0,1}ℓ : ● choose random prime 2ℓ+2 > e > 2ℓ+1 and integer s ≈ n ● compute c : c = (d / (a m1·...· a mk bs ))1/e mod n 1 ● 74 k signature is (c,e,s) August 11, 2015 © 2014 IBM Corporation CL-Signature Scheme To verify a signature (c,e,s) on messages m1, ..., mk: ● m1, ..., mk Є {0,1}ℓ: ● e > 2ℓ+1 ● d = ce a 1 m1 ·...· a k mk bs mod n Theorem: Signature scheme is secure against adaptively chosen message attacks under Strong RSA assumption. 75 August 11, 2015 © 2014 IBM Corporation Proving Knowledge of a CL-signature Recall: d = ce a1m1a2m2 bs mod n Observe: ! Let c' = c btmod n with randomly chosen t ! Then d = c'e a1m1a2m2 bs-et (mod n), i.e., (c',e, s* = s-et) is also signature on m1 and m2 To prove knowledge of signature (c',e, s*) on m2 and some m1 ! provide c' ! PK{(ε, µ1, σ) : d/a2m2 := c'ε a1µ1 b σ ∧ µ Є {0,1}ℓ ∧ ε > 2ℓ+1 } → proves d := c'ε a1µ1 a2m2b σ 76 August 11, 2015 © 2014 IBM Corporation Privacy-protecting authentication with Privacy ABCs commitment scheme signature scheme Alice zero-knowledge proofs 77 August 11, 2015 © 2014 IBM Corporation commitment scheme 78 August 11, 2015 © 2014 IBM Corporation Commitment Scheme: Functionality m m m, 2-36-17 August 11, 2015 ? mє m © 2014 IBM Corporation Commitment Scheme: Security Binding m, 2-36-17 m', 3-21-11 August 11, 2015 ? m є m ? m' є m © 2014 IBM Corporation Commitment Scheme: Security Binding m, 2-36-17 m', 3-21-11 August 11, 2015 ? m є m ? m' є m © 2014 IBM Corporation Commitment Scheme: Security Hiding: for all message m, m' m m' August 11, 2015 m m' © 2014 IBM Corporation Commitment Scheme: Security Hiding: for all message m, m' m m' August 11, 2015 m m' ? m m' m m' © 2014 IBM Corporation Commitment Schemes Group G = <g> = <h> of order q To commit to element x Є Zq: • Pedersen: perfectly hiding, computationally binding choose r Є Zq and compute c = gxhr • ElGamal: computationally hiding, perfectly binding: choose r Є Zq and compute c = (gxhr, gr) To open commitment: • reveal x and r to verifier • verifier checks if c = gxhr August 11, 2015 © 2014 IBM Corporation Pedersen's Commitment Scheme Pedersen's Scheme: Choose r Є Zq and compute c = gxhr Perfectly hiding: Let c be a commitment and u= logg h Thus c = gxhr = gx+ur = g(x+ur')+u(r-r') = gx+ur'hr-r' for any r'! I.e., given c and x' here exist r' such that c = gx'hr' Computationally binding: Let c, (x', r') and (x, r) s.t. c = gx'hr' = gxhr Then gx'-x = hr-r' and u = logg h = (x'-x)/(r-r') mod q August 11, 2015 © 2014 IBM Corporation Commitment Scheme: Extended Features Proof of Knowledge of Contents m Proof m true Proof of Relations among Contents m, m' Proof m = 2 •m' August 11, 2015 m m' true © 2014 IBM Corporation Commitment Scheme: Extended Features Let C1 = gmhr and C' = gm'hr then: m Proof m true PK{(α,β): C = gβhα } m, m' Proof m = 2 •m' PK{(α,β,γ): August 11, 2015 m m' true C' = gβhα ⋀ C = (g2)βhγ } © 2014 IBM Corporation putting things together 88 August 11, 2015 © 2014 IBM Corporation Realizing Pseudonyms and Key Binding ! Let G = <g> = <h> of order q ! User's secret key: random sk ∈ Zq ! To compute a pseudonym Nym – Choose random r ∈ Zq – Compute Nym = gskhr 89 August 11, 2015 © 2014 IBM Corporation Privacy-protecting authentication with Privacy ABCs Like PKI, but better: ! Issuing a credential Name = Alice Doe Birth date = April 3, 1997 Concept: credentials 90 August 11, 2015 © 2014 IBM Corporation Realizing Issuance of Credential Recall: a signature (c,e,s) on messages m1, ..., mk: – m1, ..., mk Є {0,1}ℓ: – e > 2ℓ+1 e –d = c a m1 ·...· a 1 mk k bs mod n Problem: Pseudonym not in message space! Solution: Sign secret key instead → d = ce a 1 sk ·a 2 m2 ·...· a mk k bs mod n New Problem: how can we sign a secret message? 91 August 11, 2015 © 2014 IBM Corporation Signature Scheme: Signing Hidden Messages ( m1 m ,... , m mj , mj+1,..., mk) σ ver(σ,(m1,..., mk), ) = true mj , mj+1,..., mk), ) m ,... , m σ = sig((( m1 Verification remains unchanged! Security requirements basically the same as for signatures, but • signer should not learn any information about m1, ..., mj • Forgery w.r.t. message clear parts and opening of commitments August 11, 2015 © 2014 IBM Corporation Realizing Issuance of Credential n, ai, b, d C=a 1 sk bs' August 11, 2015 © 2014 IBM Corporation Realizing Issuance of Credential σ' } {( K P C=a 1 sk σ , 1 µ ' ): C C n, ai, b, d µ1 b a = 1 e m a ,n bs' August 11, 2015 © 2014 IBM Corporation Realizing Issuance of Credential n, ai, b, d σ' } {( K P C=a 1 sk σ , 1 µ ' ): C C µ1 b a = 1 e m a ,n ”) s , e , c ( c = (d/C a name 2 bs”)1/e mod n bs' August 11, 2015 © 2014 IBM Corporation Realizing Issuance of Credential n, ai, b, d σ' } {( K P C=a 1 sk σ , 1 µ ' ): C C µ1 b a = 1 e m a ,n ”) s , e , c ( c = (d/C a name 2 bs”)1/e mod n bs' d = ce a August 11, 2015 sk 1 a 2 name bs” + s' (mod n) © 2014 IBM Corporation Realizing Issuance of Credential Want to sign w.r.t. Nym = gskhr August 11, 2015 n, ai, b, d © 2014 IBM Corporation Realizing Issuance of Credential Want to sign w.r.t. Nym = gskhr ρ ⋀ µ1 h =g {(µ K P 1 n, ai, b, d σ' } m m a y n N , : m ) y ,σ' N ρ , C, C ρ b 1 µ a2 a = 1 stores Nym, name e c = (d/C a name 3 bs”)1/e mod n sk r Nym = g h C=a 1 sk a r 2 August 11, 2015 bs' d = ce a sk 1 a ra 2 3 name bs” + s' (mod n) © 2014 IBM Corporation An Example Scenario 91 October 28, 2014 © 2013 IBM Corporation Polling: Scenario and Requirements Scenario: ! Pollster(s) and a number of users ! Only registered user (e.g., students who took a course) can voice opinion (e.g., course evaluation) ! User can voice opinion only once (subsequent attempts are dropped) ! Users want to be anonymous ! A user's opinion in different polls must not be linkable August 11, 2015 © 2014 IBM Corporation Polling – Solution: Registration (n,a1,a2,b,d) ! User generates pseudonym (ID for registration) ! User obtains credential on pseudonym stating that she is eligible for polls, i.e., (c,e,s) d = ce a sk 1 a 2 r a 3 attr bs (mod n) ! Credential can contain attributes (e.g., course ID) about her August 11, 2015 © 2014 IBM Corporation Polling – Solution: Submit Poll 1. User generates domain pseudonym, domain = pollID 2. User transforms credential 3. Transformed credential with a subset of the attributes – User is anonymous and unlinkable – Multiple opinions are detected because uniqueness of domain pseudonym August 11, 2015 © 2014 IBM Corporation Polling – Solution: Polling 1. Domain pseudonym: P = gdsk = H(pollID)sk P1 = H(pollID1)sk and P2 = H(pollID2)sk are unlinakble (under the Decisional Diffie-Hellman assumption) 2. User transforms credential: – c' = c bs'mod n with randomly chosen s' – SPK{(ε, µ1, µ2, µ3,σ) : P = gdµ1 ⋀ d := c'ε a1µ1 a2µ2a3µ3b σ (mod n) ⋀ µ1, µ2, µ3 Є {0,1}ℓ ⋀ ε > 2ℓ+1 }(opinion) August 11, 2015 © 2014 IBM Corporation Further Concepts 104 August 11, 2015 © 2014 IBM Corporation Concept – Inspection Inspector parameters TTP Inspection grounds • If car is damaged: ID with insurance or gov't needs be retrieved • Similarly: verifiably encrypt any certified attribute (optional) • TTP is off-line & can be distributed to lessen trust 105 August 11, 2015 © 2014 IBM Corporation Public Key Encryption Key Generation Encryption Decryption August 11, 2015 © 2014 IBM Corporation Security Like Envelopes !? No info about message August 11, 2015 © 2014 IBM Corporation Security Like Envelopes !? or ? This is called semantic security (secure if used once only or within careful construction.) August 11, 2015 © 2014 IBM Corporation Verifiable Encryption with Label Label is important to bind context to an encryption. E.g., defines decryption condition, binds user to car, etc. Security definition: change of label is new ciphertext August 11, 2015 © 2014 IBM Corporation Verifiable Encryption with Label August 11, 2015 © 2014 IBM Corporation Verifiable Encryption !Of attributes (discrete logarithm) –Camenisch-Shoup (SRSA) – based on Paillier Encryption !Of pseudonyms (group elements) –Cramer-Shoup (DL) or rarely ElGamal (DL) !Otherwise (any secret for which ZKPK exists) –Camenisch-Damgaard, works for any scheme, but much less efficient !....Open Problem to find new ones! August 11, 2015 © 2014 IBM Corporation ElGamal Encryption Scheme ! Group G = <g> of order q ! Secret Key Group x Є {1,...,q}; Public key y = gx ! To encrypt message m Є <g>: – choose random r Є {1,...,q}; – compute c = (yr m, gr) ! To decrypt ciphertext c = (c1,c2) – We know c = (yr m, gr) = (gxr m, gr) – Thus set m = c1 c2-x = yr m g-xr = yr-r m = m August 11, 2015 © 2014 IBM Corporation Realizing Inspection Nym Nym = gskhr y= gx d = ce a ska ra name bs” + s' (mod n) 1 2 3 ! Encrypt Nym : random u Є {1,...,q} and enc = (yu Nym, gu) = (e1,e2) ! Compute proof token (presentation token): – compute c' = c btmod n with randomly chosen t – compute proof PK{(ε, µ1, µ2, µ3, σ) : d := c'ε a1µ1a2µ2a3µ3b σ ∧ e1 = yρ gµ1hµ2 ∧ e2 = gρ ∧ » August 11, 2015 µ1, µ3, µ3 Є {0,1}ℓ ∧ ε > 2ℓ+1 } © 2014 IBM Corporation Revocation of credentials © 2014 IBM Corporation Anonymous Credential Revocation various reasons to revoke credential % user lost credential / secret key % misbehavior of user publishes revocation info looks up Alice should be able to convince verifier that her credential is among the good ones! 115 August 11, 2015 © 2014 IBM Corporation Anonymous Credential Revocation % Pseudonyms → standard revocation lists don't work ? 116 August 11, 2015 © 2014 IBM Corporation Revocable Credentials: First Solution ! Include into credential some credential ID ui as message, e.g., d = ce a 1 sk a 2 ui bs” + s' (mod n) ! Publish list of all valid (or invalid) ui's. (u1,..., uk) ! Alice proves that her ui is on the list. – Choose random g – Compute Uj = guj for uj in (u1,..., uk) –Prove PK{(ε, µ, ρ, σ) : ( d = c'ε a ρa µ b σ (n) ∧ U1 = gµ ) 1 2 ∨ && & ∨(d = c'ε a ρa µ b σ (mod n) ∧ Uk = gµ ) } 1 2 ! Not very efficient, i.e., linear in size k of list :-( August 11, 2015 © 2014 IBM Corporation Revocable Credentials: Second Solution ! Include into credential some credential ID ui as message, e.g., d = ce a ska ui bs” + s' (mod n) 1 2 ! Publish list of all invalid ui's. (u1,..., uk) ! Alice proves that her ui is not on the list. – Choose random h and compute U = hui – Prove PK{(ε, µ, ρ, σ) : d = c'ε a ρa µ b σ (mod n) 1 2 ∧ U = hµ } – Verifier checks whether U = huj for all uj on the list. ! Better, as only verifier needs to do linear work (and it can be improved using so-call batch-verification...) ! What happens if we make the list of all valid ui's public? ! If credential is revoked, all past transactions become linkable... August 11, 2015 © 2014 IBM Corporation Revocable Credentials: Second Solution Variation: verifier could choose h and keep it fixed for a while ! Can pre-compute list Ui = hui ! → single table lookup ! BUT: if user comes again, verifier can link!!! ! ALSO: verifier could not change h at all! or use the same as other verifiers! – one way out h = H(verifier, date), so user can check correctness. – date could be the time up to seconds and the verifier could just store all the lists, i.e., pre-compute it. August 11, 2015 © 2014 IBM Corporation Revocable Credentials: Second Solution … better implementation of proof : Issuer signs intervals between revoked # → revocation list: #1,#4,#5, Sig( 0 ,#1) Sig(#1,#4) Sig(#4,#5) Sig(#5, N ) #3 #3 #3 Verifier does not learn #, #i, #j ! #3 contains # where #i < # <#j and Sig(#i,#j) Sig(#i,#j) can be realised also with credential signature scheme, using different public key August 11, 2015 © 2014 IBM Corporation Revocable Credentials: Third Solution Using cryptographic accumulators: credentials contain random serial number # Issuer accumulates all "good" serial numbers #2 #3 #1 #2 #2 #6 #4 #5 #2 contains # that is included in Proof requires witness August 11, 2015 © 2014 IBM Corporation Revocable Credentials: Third Solution Using cryptographic accumulators: to revoke #2 issuer publishes new accumulator & new witnesses for unrevoked credentials #2 #3 #1 #2 #2 #6 #4 #5 #2 contains # that is included in Proof would require witness August 11, 2015 © 2014 IBM Corporation Revocable Credentials: Third Solution #2 Using so-called cryptographic accumulators: ! Key setup: RSA modulus n, seed v #3 #1 ! Accumulate: – values are primes ei #6 #4 #5 – accumulator value: z = v Π ei mod n – publish z and n – witness value x for ej : s.t. z = x ej mod n can be computed as x = v e1·...·ej-1 · ej+1·...·ek mod n ! Show that your value e is contained in accumulator: – provide x for e – verifier checks August 11, 2015 z = x e mod n © 2014 IBM Corporation Revocable Credentials: Third Solution Security of accumulator: show that e s.t. z = x e mod n for e that is not contained in accumulator: – For fixed e: Equivalent to RSA assumption – Any e: Equivalent to Strong RSA assumption #2 #3 #1 #6 #4 #5 Revocation: Each cert is associated with an e and each user gets witness x with certificate. But we still need: – Efficient protocol to prove that committed value is contained in accumulator. – Dynamic accumulator, i.e., ability to remove and add values to accumulator as certificates come and go. August 11, 2015 © 2014 IBM Corporation Revocable Credentials: Third Solution ! Prove that your key is in accumulator: – Commit to x: • choose random s and g and • compute U1 = x hs, U2 = gs and reveal U1 ,U2, g – Run proof-protocol with verifier PK{(ε, µ, ρ, σ, ξ, δ) : d = c'ε a ρa µ b σ (mod n) ∧ z = U1µ(1/h)ξ (mod n) 1 2 µ ξ δ ∧ 1 = U2 (1/g) (mod n) ∧ U2 = g (mod n)} August 11, 2015 © 2014 IBM Corporation Revocable Credentials: Third Solution ! Analysis – No information about x and e is revealed: • (U1, U2) is a secure commitment to x • proof-protocol is zero-knowledge – Proof is indeed proving that e contained in the certificate is also contained in the accumulator: a) 1 = U2µ(1/g)ξ = (gδ)µ (1/g)ξ (mod n) => ξ = δ µ b) z = U1µ(1/h)ξ =U1µ(1/h)δ µ =(U1/hδ )µ c) d = c'ε a ρa µ b σ (mod n) 1 August 11, 2015 (mod n) 2 © 2014 IBM Corporation Revocation: Third Solution Dynamic Accumulator ! When a new user gets a certificate containing enew –Recall: z = v Π ei mod n –Thus: z' = z enew mod n –But: then all witnesses are no longer valid, i.e., need to be updated x' = x enew mod n August 11, 2015 © 2014 IBM Corporation Revocation: Third Solution Dynamic Accumulator ! When a certificate containing erev revoked – Now z' = v Π ei = z 1/erev mod n – Witness: • Use Ext. Euclid to compute a and b s.t. a eown + b erev = 1 • Now x' = x b z' a mod n • Why: x'eown = ((x b z' a )eown) erev 1/erev mod n = ((x b z' a )eown erev ) 1/erevmod n = ((x eown) b erev (z' erev) a eown) 1/erev mod n = (z b erev z a eown ) 1/erev mod n = z 1/erev mod n = z' :-) August 11, 2015 © 2014 IBM Corporation Revocation: Third Solution (improved) Dynamic Accumulator: in case the issuer knows the factorization of n ! When a new user gets a certificate containing enew – Recall: z = v Π ei mod n – Actually v never occurs anywhere... so: v' = v 1/enew mod n and x = z 1/enew mod n – Thus z needs not to be changed in case new member joins! ! Witnesses need to be recomputed upon revocation only! August 11, 2015 © 2014 IBM Corporation Revocation: Zeroth Solution Update of Credentials: encode validity time as attribute if credential is valid → no need to check revocation updates from issuer no additional effort for verifier 130 August 11, 2015 © 2014 IBM Corporation Revocation: Zeroth Solution Re-issue certificates (off-line – interaction might be too expensive) U Recall issuing for identity mixer: U := a 1 m1 a m2 2 bs' Choose e,s” c = (d/(Ua (c,e,s”) August 11, 2015 3 m3 a 4 time bs” ))1/e mod n © 2014 IBM Corporation Revocation: Zeroth Solution Re-issue certificates (off-line – interaction might be too expensive) ! Idea: just repeat last step for each new time time': Choose ei,si” ci = (d/(Ua 3 m3' a 4 time' bsi” ))1/ei mod n (ci,ei,si”) ! Update information (ci,ei,si”) can be pushed to user by many different means August 11, 2015 © 2014 IBM Corporation Conclusions ! Roadmap – – – – – Explain possibilities to engineers, policy makers etc Usable prototypes Provide transparency Public infrastructure for privacy protection Laws with teeth (encourage investment in privacy) ! Challenges – Internet services get paid with personal data (inverse incentive) – End users are not able to handle their data (user interfaces..) – Security technology typically invisible and hard to sell ! Towards a secure information society – Society changes quickly and gets shaped by technology – Consequences are hard to grasp (time will show...) – We must inform and engage in a dialog 133 August 11, 2015 © 2014 IBM Corporation Thank you! ! eMail: [email protected] ! Links: – www.abc4trust.eu – www.futureID.eu – www.au2eu.eu – www.PrimeLife.eu – www.zurich.ibm.com/idemix – idemixdemo.zurich.ibm.com ! Code – github.com/p2abcengine & abc4trust.eu/idemix 134 August 11, 2015 © 2014 IBM Corporation References ! D. Chaum, J.-H. Evertse, and J. van de Graaf. An improved protocol for demonstrating possession of discrete logarithms and some generalizations. In EUROCRYPT ’87, vol. 304 of LNCS, pp. 127–141. Springer-Verlag, 1988. ! S. Brands. Rapid demonstration of linear relations connected by boolean operators.In EUROCRYPT ’97, vol. 1233 of LNCS, pp. 318–333. Springer Verlag, 1997. ! Mihir Bellare: Computational Number Theory http://www-cse.ucsd.edu/~mihir/cse207/w-cnt.pdf ! Camenisch, Lysanskaya: Dynamic Accumulators and Applications to Efficient Revocation of Anonymous Credentials. Crypto 2002, Lecture Notes in Computer Science, Springer Verlag. ! Ateniese, Song, Tsudik: Quasi-Efficient Revocation of Group Signatures. In Financial Cryptography 2002, Lecture Notes in Computer Science, Springer Verlag. ! Jan Camenisch, Natalie Casati, Thomas Gross, Victor Shoup: Credential Authenticated Identification and Key Exchange. CRYPTO 2010:255-276 ! Jan Camenisch, Maria Dubovitskaya, Gregory Neven: Oblivious transfer with access control. ACM Conference on Computer and Communications Security 2009: 131-140 ! Ateniese, Song, Tsudik: Quasi-Efficient Revocation of Group Signatures. In Financial Cryptography 2002, Lecture Notes in Computer Science, Springer Verlag. ! M. Bellare, C. Namprempre, D. Pointcheval, and M. Semanko: The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme. Journal of Cryptology, Volume 16, Number 3. Pages 185 -215, Springer-Verlag, 2003. ! E. Bangerter, J. Camenisch and A. Lyskanskaya: A Cryptographic Framework for the Controlled Release Of Certified Data. In Twelfth International Workshop on Security Protocols 2004. www.zurich.ibm.com/~jca/publications ! Stefan Brands: Untraceable Off-line Cash in Wallets With Observers: In Advances in Cryptology – CRYPTO '93. Springer Verlag, 1993. August 11, 2015 © 2014 IBM Corporation References ! J. Camenisch and A. Lyskanskaya: Efficient Non-transferable Anonymous Multi-show Credential System with Optional Anonymity Revocation. www.zurich.ibm.com/~jca/publications ! David Chaum: Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms. In Communications of the ACM, Vol. 24 No. 2, pp. 84—88, 1981. ! David Chaum: Blind Signatures for Untraceable Payments. In Advances in Cryptology – Proceedings of CRYPTO '82, 1983. ! David Chaum: Security Without Identification: Transaction Systems to Make Big Brother obsolete: in Communications of the ACM, Vol. 28 No. 10, 1985. ! Camenisch, Shoup: Practical Verifiable Encryption and Decryption of Discrete Logarithms. CRYPTO 2003: 126144 ! Victor Shoup: A computational introduction to Number Theory and Algebra. Available from: http://www.shoup.net/ntb/ ! D. Chaum: Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms. In Communications of the ACM. ! D. Chaum: The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability. Journal of Cryptology, 1988. ! J. Camenisch and V. Shoup: Practical Verifiable Encryption and Decryption of Discrete Logarithms. In Advances in Cryptology - CRYPTO 2003. ! T. ElGamal: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In Advances in Cryptology - CRYPTO '84. August 11, 2015 © 2014 IBM Corporation

- Similar pages