Anonymous Credentials

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