�ݺ�ߣ

IBM Research, Zurich

Efficient Attributes for
Anonymous Credentials

Jan Camenisch and
Thomas Gross

10/29/2008 | ACM CCS 2008 © 2008 IBM Corporation


Overview

 Introduction: Access with electronic identity cards

 Basis: Camenisch-Lysyanskaya signatures

 Problem Statement: Efficient finite set attributes

 Key Ideas: Prime number encoding and divisibility

 Efficiency

2 Efficient Attributes for Anonymous Credentials | 10/29/2008 | ACM CCS 2008 © 2008 IBM Corporation


Getting Access to a Vernissage
Authorities
Identity Mixer
Credential

Citizen
Policy:
“free entry: must be
retired OR
entitled to social benefit OR
a teacher OR
a poor grad student…
… on hunt for free food”
Museum

Proof of Knowledge
“Piled Higher and Deeper”
“My EID proves: by Jorge Cham
www.phdcomics.com
I fulfill the policy.”


EID Card
Limitations

 Limited access to
crypto-coprocessor

 Limited RAM

 Only pure modular
exponentiation
 very expensive



EID Card
Attributes

 Identification number

Free-form
 Name, first name

 Date of birth

Binary & Finite Set
 Nationality
 Place of birth
 Profession
 Social benefit status
 Eye and hair color
 Sex…



Basis: Camenisch-Lysyanskaya Signatures
[Camenisch & Lysyanskaya ‟01]

Public key of signer: RSA modulus n and ai, b, d Є QRn,

Secret key: factors of n

ℓ
Signature of L attributes m1, ..., mL Є {0,1} : (c,e,s)
For random prime e > 2ℓ and integer s ≈ n, compute c such that

d = a m1·...· a mL
bs ce mod n
1 L

Theorem: Signature scheme is secure against adaptively chosen
message attacks under SRSA assumption.

[SRSA: Barić & Pfitzmann '97 and Fujisaki & Okamoto '97]
Efficient Attributes for Anonymous Credentials | 10/29/2008 | ACM CCS 2008 © 2008 IBM Corporation


Basis: Camenisch-Lysyanskaya Signatures
[Camenisch & Lysyanskaya ‟01]

ℓ
For random prime e > 2ℓ and integer s ≈ n, compute c such that

m1 mL s e
d = a ·...· a b c mod n
1 L

L attribute bases blinding
SRSA problem
one base per attribute mi instance

Proofs of possession: constant constant
O(L) mod-exp complexity
 Invites for a nap
“Piled Higher and Deeper”
by Jorge Cham www.phdcomics.com



Problem Statement
Enable Camenisch-Lysyanskaya signatures to compress all
binary and finite set attributes in one dedicated attribute base.

Efficiency:
 Proofs of possession linear in the free-form attributes: O(l),
binary and finite set attributes only as small constant overhead.

 Proofs of relationships with efficient toolbox for AND, NOT, OR.

Security:
 Signature scheme is secure against adaptively chosen message
attacks under SRSA assumption.

 Attribute encoding is integer under SRSA assumption.



Key Ideas: Prime Encoding… [Compare to
Camenisch & Lysyanskaya „02]

Idea: Encode attribute values as prime numbers.

 SETUP: Certify a small public prime number ei for each value realization
of a binary or finite-set attribute.
 ISSUE: Product of prime numbers E=(ei) in a single dedicated base.

 Compression of k binary and finite-set attributes in one base

Realization:
ℓ
With k binary or finite set attributes and l string attributes

m1
d = a ei
·a · ...· a ml bs ce mod n
0 1 l



Key Ideas: … and Divisibility

Idea: Use coprime/divisibility to prove attribute
presence and absence.

PROOF: Selectively disclose attribute primes (ej) and prove knowledge of
remaining factorization E’ = ij(ei) of the compound attribute (ei).

 Efficient proof methods for AND, NOT, OR statements.

Realization:
Proof of Knowledge of AND with prime attributes:
● PK{(e, E’, m1, ..., ml, s) :

e E’ s
d := c' · (a (ej)) · a m1 · ...· a ml b mod n … }
0 1 l



Efficiency: Asymptotic Modular Exponentiations

Base Bit Vector Prime
Encoding Encoding encoding
Bases &
O(L) O(l) O(l)*
Possession
AND
O(L) O(L+i) O(l)*
(i attributes)

NOT O(L) O(L) O(l)*

OR
O(L+i) O(L+i) O(l)**
(i attributes)

*) Small constant overhead to proof of possession (1-2 mod-exp).
**) Constant overhead of 18 mod-exp. over proof of possession.
Break even points, e.g. k=5 binary attributes, i=2 shown.


Summary
Advantages Limitations
 Constant mod-exps for  Free-form attributes
binary flags & finite sets  A priori vocabulary

 Efficient proofs for
AND, NOT, OR

 Compact credentials:  Public key overhead:
Save k-1 attribute bases k * |mi| * |ei|

Conclusion: 80/20 solution where finite sets matter



BACKUP



Recall: The Strong RSA Assumption

Flexible RSA Problem: Given RSA modulus n and z Є QRn find
integers e and u such that

ue = z mod n

(Recall: QRn = {x : exist y s.t. y2 = x mod n } )

● Introduced by Barić & Pfitzmann '97 and Fujisaki & Okamoto '97

● Hard in generic algorithm model [Damgård & Koprowski '01]



Signature Scheme based on the SRSA I
[Camenisch & Lysyanskaya „02]

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 e > 2 and integer s ≈ n

● compute c such that
m1 mk
d= a ·...· a bs ce mod n
1 k

● signature is (c,e,s)



Signature Scheme based on the SRSA II

A signature (c,e,s) on messages m1, ..., mk is valid iff:
ℓ
● m1, ..., mk Є {0,1} :
ℓ
● e>2
m1 mk s e
● d= a ·...· a b c mod n
1 k

Theorem: Signature scheme is secure against
adaptively
chosen message attacks under SRSA assumption.



Proof of Knowledge of a Signature
Observe:

s'
Let c' = c b mod n with random s'
e m1 mk
then d = c‘ a · ... · a bs* (mod n), with s* = s-es’
1 k
i.e., (c',e, s*) is a also a valid signature!

Therefore, to prove knowledge of signature on some m
● provide c'
e m1 mk s
● PK{(e, m1, ..., mk, s) : d := c' a · ... · a b
1 k
ℓ ℓ+1 ℓ
 mi Є {0,1}  eЄ2 ± {0,1} }



Proof of Knowledge of a Signature
Using second Commitment

assume second group n, ai, b, n
2nd commitment C = a1sk b s*

To prove knowledge of signature on some m
provide c'

PK{(e, m1, ..., mk, s,s* ) :

C = a1m1b s*  d := c‘ e
a m1
1
· ... · a mk
k
bs }


�ݺ�ߣ

CCS\'08: Efficient Attributes For Anonymous Credentials - Thomas Gross

Recommended

More Related Content

Featured (20)

CCS\'08: Efficient Attributes For Anonymous Credentials - Thomas Gross