Download slides

Automorphic Signatures in Bilinear Groups
Georg Fuchsbauer
École normale supérieure
UCL, 23.03.2010
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
1 / 26
1
Motivation: Anonymous Proxy Signatures
2
Groth-Sahai Witness-Indistinguishable Proofs
3
Automorphic Signatures
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
2 / 26
1
Motivation: Anonymous Proxy Signatures
2
Groth-Sahai Witness-Indistinguishable Proofs
3
Automorphic Signatures
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
3 / 26
Anonymous Consecutive Delegation of Signing Rights
F, Pointcheval: Anonymous Proxy Signatures [SCN'08]
Delegation A delegator delegates his signing rights to a proxy signer
(or delegatee) who can then sign on the delegator's
behalf
Consecutiveness A delegatee may re-delegate the received signing rights
⇒ intermediate delegators
Anonymity All intermediate delegators and the proxy signer
remain anonymous
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
4 / 26
Anonymous Consecutive Delegation of Signing Rights
F, Pointcheval: Anonymous Proxy Signatures [SCN'08]
Delegation A delegator delegates his signing rights to a proxy signer
(or delegatee) who can then sign on the delegator's
behalf
Consecutiveness A delegatee may re-delegate the received signing rights
⇒ intermediate delegators
Anonymity All intermediate delegators and the proxy signer
remain anonymous
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
4 / 26
Anonymous Consecutive Delegation of Signing Rights
F, Pointcheval: Anonymous Proxy Signatures [SCN'08]
Delegation A delegator delegates his signing rights to a proxy signer
(or delegatee) who can then sign on the delegator's
behalf
Consecutiveness A delegatee may re-delegate the received signing rights
⇒ intermediate delegators
Anonymity All intermediate delegators and the proxy signer
remain anonymous
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
4 / 26
Anonymous Consecutive Delegation of Signing Rights
F, Pointcheval: Anonymous Proxy Signatures [SCN'08]
Delegation A delegator delegates his signing rights to a proxy signer
(or delegatee) who can then sign on the delegator's
behalf
Consecutiveness A delegatee may re-delegate the received signing rights
⇒ intermediate delegators
Anonymity All intermediate delegators and the proxy signer
remain anonymous
After verifying a proxy signature one knows that someone entitled signed
but nothing more.
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
4 / 26
Application: GRID computing
User authenticates herself and starts process which needs to authenticate
to resources / start subprocesses
⇒ Delegation and re-delegation of signing rights
No need to know that it was not the user herself to be authenticated
Relation to Other Primitives
Anonymous proxy signatures are a generalization of
Proxy signatures (consecutive delegation)
formalized by [BPW03]
(Dynamic) group signatures (anonymity)
formalized by [BSZ05]
and satisfy the respective security notions.
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
5 / 26
Application: GRID computing
User authenticates herself and starts process which needs to authenticate
to resources / start subprocesses
⇒ Delegation and re-delegation of signing rights
No need to know that it was not the user herself to be authenticated
Relation to Other Primitives
Anonymous proxy signatures are a generalization of
Proxy signatures (consecutive delegation)
formalized by [BPW03]
(Dynamic) group signatures (anonymity)
formalized by [BSZ05]
and satisfy the respective security notions.
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
5 / 26
Application: GRID computing
User authenticates herself and starts process which needs to authenticate
to resources / start subprocesses
⇒ Delegation and re-delegation of signing rights
No need to know that it was not the user herself to be authenticated
Relation to Other Primitives
Anonymous proxy signatures are a generalization of
Proxy signatures (consecutive delegation)
formalized by [BPW03]
(Dynamic) group signatures (anonymity)
formalized by [BSZ05]
and satisfy the respective security notions.
more recently: Delegatable Anonymous Credentials [BCCKLS09]
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
5 / 26
(Dynamic) Group Signatures
Group public key: pk
Issuer (ik )
Opener (ok )
$
HH
kY
@Q
BM I
Q H
B
@
QQHH
@
Q HH
Reg HH
Q
@
Q
HH
@
Q
B
Hj
Q
@
R
s
Q
H
?
BN
6
open
Group members (ski )
sign msg
?
σ
%
Verication: Verify(pk, msg, σ) = 1
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
6 / 26
Proxy Signatures
Delegator (pkD )
PP
PP
P
delegate
PP
q
P
Delegatee/Signer
PP
PP
sign
Verify(pkD , msg, σ)
Georg Fuchsbauer (ENS)
Pmsg
PP
q
σ
Automorphic Signatures
UCL, 23.03.2010
7 / 26
Proxy Signatures, Consecutive Delegations
Delegator (pkD )
XXX
XX
z
Delegator 2
XX
XXX
z
Delegator 3
XX
XXX
z
Proxy Signer
PP
P
Georg Fuchsbauer (ENS)
Automorphic Signatures
PP
PP
q
σ
UCL, 23.03.2010
8 / 26
Proxy Signatures, Consecutive Delegations
Delegator (pkD )
XXX
'
XX
z
$
Delegator 2
XX
XXX
z
Delegator 3
ANONYMOUS
XX
XXX
z
&
Georg Fuchsbauer (ENS)
Proxy Signer
PP
P
Automorphic Signatures
PP
PP
q
%
σ
UCL, 23.03.2010
8 / 26
Proxy Signatures, Consecutive Delegations
Delegator (pkD )
XXX
'
XX
z
$
Delegator 2
XX
XXX
z
Delegator 3
XX
XXX
z
ANONYMOUS
Proxy Signer
&
Opener (ok)
Georg Fuchsbauer (ENS)
PP
P
open
Automorphic Signatures
%
PP
PP
q
σ
6
UCL, 23.03.2010
8 / 26
Algorithms of Anonymous Proxy Signature Scheme
1λ →
Georg Fuchsbauer (ENS)
Setup
→
Automorphic Signatures
pp, ik, ok
UCL, 23.03.2010
9 / 26
Algorithms of Anonymous Proxy Signature Scheme
ik
Issuer ( )
...
Reg
-
pk
1λ →
Georg Fuchsbauer (ENS)
Setup
...
pk, sk
→
Automorphic Signatures
-
User
pp, ik, ok
UCL, 23.03.2010
9 / 26
Algorithms of Anonymous Proxy Signature Scheme
ik
Issuer ( )
...
Reg
-
pk
1λ →
skx , pky
Georg Fuchsbauer (ENS)
→
...
pk, sk
Setup
→
Del
→
Automorphic Signatures
-
User
pp, ik, ok
warrx →y
UCL, 23.03.2010
9 / 26
Algorithms of Anonymous Proxy Signature Scheme
ik
Issuer ( )
...
Reg
-
pk
1λ →
skx , [warr→x , ] pky
Georg Fuchsbauer (ENS)
→
...
pk, sk
Setup
→
Del
→
Automorphic Signatures
-
User
pp, ik, ok
warr[→]x →y
UCL, 23.03.2010
9 / 26
Algorithms of Anonymous Proxy Signature Scheme
ik
Issuer ( )
...
Reg
-
pk
1λ →
skx , [warr→x , ] pky
sky , warrx →...→y , M
Georg Fuchsbauer (ENS)
...
pk, sk
User
pp, ik, ok
warr[→]x →y
Setup
→
→
Del
→
→
PSig
→ σ
Automorphic Signatures
-
UCL, 23.03.2010
9 / 26
Algorithms of Anonymous Proxy Signature Scheme
ik
Issuer ( )
...
Reg
-
pk
1λ →
skx , [warr→x , ] pky
sky , warrx →...→y , M
pkx , M , σ
Georg Fuchsbauer (ENS)
...
pk, sk
User
pp, ik, ok
warr[→]x →y
Setup
→
→
Del
→
→
PSig
→ σ
→
PVer
→
Automorphic Signatures
-
b ∈ {0, 1}
UCL, 23.03.2010
9 / 26
Algorithms of Anonymous Proxy Signature Scheme
ik
Issuer ( )
...
Reg
-
pk
1λ →
skx , [warr→x , ] pky
sky , warrx →...→y , M
pkx , M , σ
ok, M , σ
Georg Fuchsbauer (ENS)
...
pk, sk
-
User
pp, ik, ok
warr[→]x →y
Setup
→
→
Del
→
→
PSig
→ σ
→
PVer
→
→
Open
→ a list of users or ⊥ (failure)
Automorphic Signatures
b ∈ {0, 1}
UCL, 23.03.2010
9 / 26
Security for Anonymous Proxy Signatures
Security
Anonymity intermediate delegators and proxy signer remain
anonymous
Traceability every valid signature can be traced to its intermediate
delegators and proxy signer
Non-Frameability no one can produce a signature that, when opened,
wrongfully reveals a delegator or signer
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
10 / 26
Security for Anonymous Proxy Signatures
Security
Anonymity intermediate delegators and proxy signer remain
anonymous
Traceability every valid signature can be traced to its intermediate
delegators and proxy signer
Non-Frameability no one can produce a signature that, when opened,
wrongfully reveals a delegator or signer
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
10 / 26
Security for Anonymous Proxy Signatures
Security
Anonymity intermediate delegators and proxy signer remain
anonymous
Traceability every valid signature can be traced to its intermediate
delegators and proxy signer
Non-Frameability no one can produce a signature that, when opened,
wrongfully reveals a delegator or signer
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
10 / 26
Generic Construction: Ingredients
Generic Construction
using
Digital signatures (EUF-CMA)
Public-key encryption (IND-CPA)
Non-interactive zero-knowledge proofs
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
11 / 26
Generic Construction: Ingredients
Generic Construction
using
Digital signatures (EUF-CMA)
Public-key encryption (IND-CPA)
Non-interactive zero-knowledge proofs
(Existence follows from trapdoor permutations)
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
11 / 26
Generic Construction: Overview
Setup Generates decryption key for opening authority;
signing key for issuer
Parameters: resp. public keys, crs for NIZK
Register Issuer signs user's public key → certicate
Delegate Sign delegatee's public key → warrant
Re-delegate: additionally forward received warrants
Proxy-Sign Sign message, encrypt
• interm. delegators' verication keys and certicates
• warrants • signature on message
Output
• ciphertext
• NIZK proof that plaintext contains valid signatures
Verify Verify NIZK proof
Open Decrypt ciphertext
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
12 / 26
Generic Construction: Overview
Setup Generates decryption key for opening authority;
signing key for issuer
Parameters: resp. public keys, crs for NIZK
Register Issuer signs user's public key → certicate
Delegate Sign delegatee's public key → warrant
Re-delegate: additionally forward received warrants
Proxy-Sign Sign message, encrypt
• interm. delegators' verication keys and certicates
• warrants • signature on message
Output
• ciphertext
• NIZK proof that plaintext contains valid signatures
Verify Verify NIZK proof
Open Decrypt ciphertext
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
12 / 26
Generic Construction: Overview
Setup Generates decryption key for opening authority;
signing key for issuer
Parameters: resp. public keys, crs for NIZK
Register Issuer signs user's public key → certicate
Delegate Sign delegatee's public key → warrant
Re-delegate: additionally forward received warrants
Proxy-Sign Sign message, encrypt
• interm. delegators' verication keys and certicates
• warrants • signature on message
Output
• ciphertext
• NIZK proof that plaintext contains valid signatures
Verify Verify NIZK proof
Open Decrypt ciphertext
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
12 / 26
Generic Construction: Overview
Setup Generates decryption key for opening authority;
signing key for issuer
Parameters: resp. public keys, crs for NIZK
Register Issuer signs user's public key → certicate
Delegate Sign delegatee's public key → warrant
Re-delegate: additionally forward received warrants
Proxy-Sign Sign message, encrypt
• interm. delegators' verication keys and certicates
• warrants • signature on message
Output
• ciphertext
• NIZK proof that plaintext contains valid signatures
Verify Verify NIZK proof
Open Decrypt ciphertext
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
12 / 26
Generic Construction: Overview
Setup Generates decryption key for opening authority;
signing key for issuer
Parameters: resp. public keys, crs for NIZK
Register Issuer signs user's public key → certicate
Delegate Sign delegatee's public key → warrant
Re-delegate: additionally forward received warrants
Proxy-Sign Sign message, encrypt
• interm. delegators' verication keys and certicates
• warrants • signature on message
Output
• ciphertext
• NIZK proof that plaintext contains valid signatures
Verify Verify NIZK proof
Open Decrypt ciphertext
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
12 / 26
Generic Construction: Overview
Setup Generates decryption key for opening authority;
signing key for issuer
Parameters: resp. public keys, crs for NIZK
Register Issuer signs user's public key → certicate
Delegate Sign delegatee's public key → warrant
Re-delegate: additionally forward received warrants
Proxy-Sign Sign message, encrypt
• interm. delegators' verication keys and certicates
• warrants • signature on message
Output
• ciphertext
• NIZK proof that plaintext contains valid signatures
Verify Verify NIZK proof
Open Decrypt ciphertext
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
12 / 26
Instantiation
F, Pointcheval: Proofs on Encrypted Values in Bilinear Groups and an
Application to Anonymity of Signatures. [PAIRING '09]
Encryption and proofs based on a generalization of techniques of
Boyen-Waters Group Signatures [PKC'07]
based on Subgroup Decision Assumption
Signature scheme inecient due to bit-by-bit techniques
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
13 / 26
1
Motivation: Anonymous Proxy Signatures
2
Groth-Sahai Witness-Indistinguishable Proofs
3
Automorphic Signatures
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
14 / 26
NIWI
Non-Interactive Witness-Indistinguishable Proofs
An NP language L is dened by relation R as L := {x | ∃w : (x , w ) ∈ R }.
A NIWI for L consists of Setup, Prove and Verify.
Setup outputs a common reference string crs
Prove(crs, x , w ) outputs a proof π
Verify(crs, x , π) and outputs 1 or 0
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
15 / 26
NIWI
Non-Interactive Witness-Indistinguishable Proofs
An NP language L is dened by relation R as L := {x | ∃w : (x , w ) ∈ R }.
A NIWI for L consists of Setup, Prove and Verify.
Setup outputs a common reference string crs
Prove(crs, x , w ) outputs a proof π
Verify(crs, x , π) and outputs 1 or 0
It satises
completeness
soundness
witness indistinguishability
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
15 / 26
Groth-Sahai I
Bilinear Groups and the Decision Linear Assumption [BBS04]
Bilinear group (p , G, GT , e , G )
(G, +) and (GT , ·) cyclic groups of prime order p
e : G × G → GT bilinear, i.e. ∀X , Y ∈ G, ∀a, b ∈ Z:
e (aX , bY ) = e (X , Y )ab
G = hG i, GT = he (G , G )i
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
16 / 26
Groth-Sahai I
Bilinear Groups and the Decision Linear Assumption [BBS04]
Bilinear group (p , G, GT , e , G )
(G, +) and (GT , ·) cyclic groups of prime order p
e : G × G → GT bilinear, i.e. ∀X , Y ∈ G, ∀a, b ∈ Z:
e (aX , bY ) = e (X , Y )ab
G = hG i, GT = he (G , G )i
Given (U , V , G , αU , β V , γ G ) it is hard to decide whether γ = α + β .
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
16 / 26
Groth-Sahai I
Bilinear Groups and the Decision Linear Assumption [BBS04]
Bilinear group (p , G, GT , e , G )
(G, +) and (GT , ·) cyclic groups of prime order p
e : G × G → GT bilinear, i.e. ∀X , Y ∈ G, ∀a, b ∈ Z:
e (aX , bY ) = e (X , Y )ab
G = hG i, GT = he (G , G )i
Given (U , V , G , αU , β V , γ G ) it is hard to decide whether γ = α + β .
PPE
A pairing-product equation is an equation over variables X1 , . . . , Xn ∈ G of
the form
n
n Y
n
Y
Y
e (Ai , Xi )
e (Xi , Xj )γ , = tT ,
(E)
i =1
i =1 j =1
determined by Ai ∈ G, γi ,j ∈ Zp and tT ∈ GT , for 1 ≤ i , j ≤ n.
i j
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
16 / 26
Groth-Sahai I
Bilinear Groups and the Decision Linear Assumption [BBS04]
Bilinear group (p , G, GT , e , G )
(G, +) and (GT , ·) cyclic groups of prime order p
e : G × G → GT bilinear, i.e. ∀X , Y ∈ G, ∀a, b ∈ Z:
e (aX , bY ) = e (X , Y )ab
G = hG i, GT = he (G , G )i
Given (U , V , G , αU , β V , γ G ) it is hard to decide whether γ = α + β .
PPE
A pairing-product equation is an equation over variables X1 , . . . , Xn ∈ G of
the form
n
n Y
n
Y
Y
e (Ai , Xi )
e (Xi , Xj )γ , = tT ,
(E)
i =1
i =1 j =1
determined by Ai ∈ G, γi ,j ∈ Zp and tT ∈ GT , for 1 ≤ i , j ≤ n.
i j
Groth, Sahai: NIWI proof of satisability of PPE
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
16 / 26
Groth-Sahai II
Setup
Com
Prove
Verify
on input the bilinear group output a commitment key ck
on input ck , X ∈ G, randomness ρ output commitment cX to X
on input ck , (Xi , ρi )ni=1 , equation E output a proof φ
on input ck , ~c, E , φ, output 0 or 1
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
17 / 26
Groth-Sahai II
Setup
Com
Prove
Verify
on input the bilinear group output a commitment key ck
on input ck , X ∈ G, randomness ρ output commitment cX to X
on input ck , (Xi , ρi )ni=1 , equation E output a proof φ
on input ck , ~c, E , φ, output 0 or 1
Correctness Honestly generated proofs are accepted by Verify
Soundness ExtSetup outputs (ck , ek ) s.t.
given ~c and φ s.t. Verify(ck ,~c, E , φ) = 1 then Extract(ek ,~c)
~ that satises E
returns X
Witness-Indistinguishability WISetup outputs ck ∗ indist. from ck s.t.
Com(ck ∗ , ·, ·) produces statistically hiding commitments i.e.
∀c ∀X ∃ρ : Com(ck ∗ , X , ρ) = c
Given (Xi , ρi )i , (Xi0 , ρ0i )i s.t. ci = Com(ck ∗ , Xi , ρi ) = Com(ck ∗ , Xi0 , ρ0i )
and (Xi )i and (Xi0 )i satisfy E then
Prove(ck ∗ , (Xi , ρi )i , E ) ∼ Prove(ck ∗ , (Xi0 , ρ0i )i , E )
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
17 / 26
Groth-Sahai II
Setup
Com
Prove
Verify
on input the bilinear group output a commitment key ck
on input ck , X ∈ G, randomness ρ output commitment cX to X
on input ck , (Xi , ρi )ni=1 , equation E output a proof φ
on input ck , ~c, E , φ, output 0 or 1
Correctness Honestly generated proofs are accepted by Verify
Soundness ExtSetup outputs (ck , ek ) s.t.
given ~c and φ s.t. Verify(ck ,~c, E , φ) = 1 then Extract(ek ,~c)
~ that satises E
returns X
Witness-Indistinguishability WISetup outputs ck ∗ indist. from ck s.t.
Com(ck ∗ , ·, ·) produces statistically hiding commitments i.e.
∀c ∀X ∃ρ : Com(ck ∗ , X , ρ) = c
Given (Xi , ρi )i , (Xi0 , ρ0i )i s.t. ci = Com(ck ∗ , Xi , ρi ) = Com(ck ∗ , Xi0 , ρ0i )
and (Xi )i and (Xi0 )i satisfy E then
Prove(ck ∗ , (Xi , ρi )i , E ) ∼ Prove(ck ∗ , (Xi0 , ρ0i )i , E )
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
17 / 26
Groth-Sahai II
Setup
Com
Prove
Verify
on input the bilinear group output a commitment key ck
on input ck , X ∈ G, randomness ρ output commitment cX to X
on input ck , (Xi , ρi )ni=1 , equation E output a proof φ
on input ck , ~c, E , φ, output 0 or 1
Correctness Honestly generated proofs are accepted by Verify
Soundness ExtSetup outputs (ck , ek ) s.t.
given ~c and φ s.t. Verify(ck ,~c, E , φ) = 1 then Extract(ek ,~c)
~ that satises E
returns X
Witness-Indistinguishability WISetup outputs ck ∗ indist. from ck s.t.
Com(ck ∗ , ·, ·) produces statistically hiding commitments i.e.
∀c ∀X ∃ρ : Com(ck ∗ , X , ρ) = c
Given (Xi , ρi )i , (Xi0 , ρ0i )i s.t. ci = Com(ck ∗ , Xi , ρi ) = Com(ck ∗ , Xi0 , ρ0i )
and (Xi )i and (Xi0 )i satisfy E then
Prove(ck ∗ , (Xi , ρi )i , E ) ∼ Prove(ck ∗ , (Xi0 , ρ0i )i , E )
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
17 / 26
1
Motivation: Anonymous Proxy Signatures
2
Groth-Sahai Witness-Indistinguishable Proofs
3
Automorphic Signatures
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
18 / 26
Motivation
Groth-Sahai proofs allow us to
commit to (encrypt) group elements and to
prove that they satisfy PPEs
Opener's public and decryption key: (ck , ek ) ← ExtSetup
To instantiate generic construction, we need signature scheme s.t.
signatures are group elements
verication by PPE
able to sign public keys
EUF-CMA
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
19 / 26
Motivation
Groth-Sahai proofs allow us to
commit to (encrypt) group elements and to
prove that they satisfy PPEs
Opener's public and decryption key: (ck , ek ) ← ExtSetup
To instantiate generic construction, we need signature scheme s.t.
signatures are group elements
verication by PPE
able to sign public keys
EUF-CMA
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
19 / 26
Motivation
Groth-Sahai proofs allow us to
commit to (encrypt) group elements and to
prove that they satisfy PPEs
Opener's public and decryption key: (ck , ek ) ← ExtSetup
To instantiate generic construction, we need signature scheme s.t.
signatures are group elements
verication by PPE
able to sign public keys
EUF-CMA
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
19 / 26
Motivation
Groth-Sahai proofs allow us to
commit to (encrypt) group elements and to
prove that they satisfy PPEs
Opener's public and decryption key: (ck , ek ) ← ExtSetup
To instantiate generic construction, we need signature scheme s.t.
signatures are group elements
verication by PPE
able to sign public keys
EUF-CMA
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
19 / 26
Motivation
Groth-Sahai proofs allow us to
commit to (encrypt) group elements and to
prove that they satisfy PPEs
Opener's public and decryption key: (ck , ek ) ← ExtSetup
To instantiate generic construction, we need signature scheme s.t.
signatures are group elements
verication by PPE
able to sign public keys
EUF-CMA
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
19 / 26
Motivation
Groth-Sahai proofs allow us to
commit to (encrypt) group elements and to
prove that they satisfy PPEs
Opener's public and decryption key: (ck , ek ) ← ExtSetup
To instantiate generic construction, we need signature scheme s.t.
signatures are group elements
verication by PPE
able to sign public keys
EUF-CMA
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
19 / 26
Motivation
Groth-Sahai proofs allow us to
commit to (encrypt) group elements and to
prove that they satisfy PPEs
Opener's public and decryption key: (ck , ek ) ← ExtSetup
To instantiate generic construction, we need signature scheme s.t.
signatures are group elements
verication by PPE
able to sign public keys
EUF-CMA
Automorphic Signatures
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
19 / 26
Boneh-Boyen Signatures
q
The -Strong Die-Hellman Problem (SDH) [BB04]
Given (G , xG , x 2 G , . . . , x q G ) ∈ Gq+1 for x ← Z∗p , output
1
( x+
c G , c ) ∈ G × Zp .
Weak
Boneh-Boyen
Signatures
Given G , xG ∈ G and q − 1 distinct pairs ( x +1c G , ci ) ∈ G × Zp , output a
new pair ( x +1 c G , c ) ∈ G × Zp .
i
Boneh-Boyen Short Signatures
Secret key (x , y ) ∈ Z2p , public key X = xG , Y = yG
Sign m ∈ Zp : choose r ← Zp ; signature: (A = x +m1+ry G , r )
Verify (A, r ) on m under (X , Y ) by checking
e (A, X + mG + rY ) = e (G , G )
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
20 / 26
Boneh-Boyen Signatures
q
The -Strong Die-Hellman Problem (SDH) [BB04]
Given (G , xG , x 2 G , . . . , x q G ) ∈ Gq+1 for x ← Z∗p , output
1
( x+
c G , c ) ∈ G × Zp .
Weak
Boneh-Boyen
Signatures
Given G , xG ∈ G and q − 1 distinct pairs ( x +1c G , ci ) ∈ G × Zp , output a
new pair ( x +1 c G , c ) ∈ G × Zp .
i
Boneh-Boyen Short Signatures
Secret key (x , y ) ∈ Z2p , public key X = xG , Y = yG
Sign m ∈ Zp : choose r ← Zp ; signature: (A = x +m1+ry G , r )
Verify (A, r ) on m under (X , Y ) by checking
e (A, X + mG + rY ) = e (G , G )
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
20 / 26
Boneh-Boyen Signatures
q
The -Strong Die-Hellman Problem (SDH) [BB04]
Given (G , xG , x 2 G , . . . , x q G ) ∈ Gq+1 for x ← Z∗p , output
1
( x+
c G , c ) ∈ G × Zp .
Weak
Boneh-Boyen
Signatures
Given G , xG ∈ G and q − 1 distinct pairs ( x +1c G , ci ) ∈ G × Zp , output a
new pair ( x +1 c G , c ) ∈ G × Zp .
i
Boneh-Boyen Short Signatures
Secret key (x , y ) ∈ Z2p , public key X = xG , Y = yG
Sign m ∈ Zp : choose r ← Zp ; signature: (A = x +m1+ry G , r )
Verify (A, r ) on m under (X , Y ) by checking
e (A, X + mG + rY ) = e (G , G )
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
20 / 26
Boneh-Boyen Signatures
q
The -Strong Die-Hellman Problem (SDH) [BB04]
Given (G , xG , x 2 G , . . . , x q G ) ∈ Gq+1 for x ← Z∗p , output
1
( x+
c G , c ) ∈ G × Zp .
Weak
Boneh-Boyen
Signatures
Given G , xG ∈ G and q − 1 distinct pairs ( x +1c G , ci ) ∈ G × Zp , output a
new pair ( x +1 c G , c ) ∈ G × Zp .
i
Boneh-Boyen Short Signatures
Secret key (x , y ) ∈ Z2p , public key X = xG , Y = yG
Sign m ∈ Zp : choose r ← Zp ; signature: (A = x +m1+ry G , r )
Verify (A, r ) on m under (X , Y ) by checking
e (A, X + mG + rY ) = e ( x +m1+ry G , (x + m + ry )G ) = e (G , G )
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
20 / 26
Variants of Boneh-Boyen
Weak
Boneh-Boyen
Signatures
Given G , X := xG ∈ G and q − 1 distinct pairs
1
( x +1c G , ci ) ∈ G × Zp , output a new pair ( x +
c G , c ) ∈ G × Zp .
i
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
21 / 26
Variants of Boneh-Boyen
The Hidden SDH [BW07]
Given G , H , X := xG ∈ G and q − 1 distinct triples
1
3
( x +1c G , ci G , ci H ) ∈ G3 , output a new triple ( x +
c G , cG , cH ) ∈ G .
i
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
21 / 26
Variants of Boneh-Boyen
The Hidden SDH [BW07]
Given G , H , X := xG ∈ G and q − 1 distinct triples
1
3
( x +1c G , ci G , ci H ) ∈ G3 , output a new triple ( x +
c G , cG , cH ) ∈ G .
i
All components are group elements
Validity of a triple (A, C , D ) is veriable by PPEs:
e (A, X + C ) = e (G , G )
e (C , H ) = e (G , D )
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
21 / 26
Assumptions I
F, Pointcheval, Vergnaud: Transferable Constant-Size Fair E-Cash
[CANS'09]
SDH implies hardness of the following:
Given G , K , X := xG∈ G and q − 1 triples
2
1
x +c (K +vi G ), ci ,vi ∈ G × Zp , output a new triple
2
1
x +c (K +vG ), c , v ∈ G × Zp .
i
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
22 / 26
Assumptions I
F, Pointcheval, Vergnaud: Transferable Constant-Size Fair E-Cash
[CANS'09]
SDH implies hardness of the following:
Given G , K , X := xG∈ G and q − 1 triples
2
1
x +c (K +vi G ), ci ,vi ∈ G × Zp , output a new triple
2
1
x +c (K +vG ), c , v ∈ G × Zp .
i
Asymm. Double Hidden SDH (ADHSDH)
Given G , K , F , H , X := xG , Y := xH
∈ G and q − 1 tuples
1
(
K
+
v
G
),
c
F
,
c
H
,
v
G
,
v
H
i
i
i
i i , output a new tuple
x +c
1
x +c (K + vG ), cF , cH , vG , vH .
i
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
22 / 26
Assumptions II
Verication
(A, C , D , V , W ) satises
e (A, Y + D )= e ( x +1 c (K + vG ), xH + cH ) = e (K + V , H ),
e (C , H )= e (cF , H ) = e (F , D )
e (V , H )= e (vG , H ) = e (G , W )
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
23 / 26
Assumptions II
Verication
(A, C , D , V , W ) satises
e (A, Y + D )= e ( x +1 c (K + vG ), xH + cH ) = e (K + V , H ),
e (C , H )= e (cF , H ) = e (F , D )
e (V , H )= e (vG , H ) = e (G , W )
(Weak) Flexible CDH (WFCDH)
Given (G , aG , bG ) ∈ G3 , output (R , aR , bR , abR ) ∈ G4 with R 6= 0.
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
23 / 26
F: Automorphic Signatures in Bilinear Groups
http://eprint.iacr.org/2009/320
Automorphic Signature
Parameters: (G , K , F , H , T ) ← G5 , which dene the message space
as DH := {(mG , mH ) | m ∈ Zp },
KeyGen: secret key x ← Zp , public key (X := xG , Y := yH )
Sign (M , N ) ∈ DH: choose c , r ← Zp , set
A := x +1 c (K +rT + M ), C := cF , D := cH , R := rG , S := rH
A signature on a message (M , N ) ∈ DH is valid i
e (A, Y + D ) = e (K + M , H ) e (T , S )
Georg Fuchsbauer (ENS)
Automorphic Signatures
e (C , H ) = e (F , D )
e (R , H ) = e (G , S )
UCL, 23.03.2010
24 / 26
F: Automorphic Signatures in Bilinear Groups
http://eprint.iacr.org/2009/320
Automorphic Signature
Parameters: (G , K , F , H , T ) ← G5 , which dene the message space
as DH := {(mG , mH ) | m ∈ Zp },
KeyGen: secret key x ← Zp , public key (X := xG , Y := yH )
Sign (M , N ) ∈ DH: choose c , r ← Zp , set
A := x +1 c (K +rT + M ), C := cF , D := cH , R := rG , S := rH
A signature on a message (M , N ) ∈ DH is valid i
e (A, Y + D ) = e (K + M , H ) e (T , S )
e (C , H ) = e (F , D )
e (R , H ) = e (G , S )
The above scheme is EUF-CMA under ADHSDH and WFCDH.
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
24 / 26
Applications
Eciency
Messages and public keys in G2 , signatures in G5
Verication: 7 pairing evaluations
Also instantiable in asymmetric bilinear groups
In combination with Groth-Sahai proofs, automorphic signatures enable
ecient instantiations of generic concepts.
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
25 / 26
Applications
Eciency
Messages and public keys in G2 , signatures in G5
Verication: 7 pairing evaluations
Also instantiable in asymmetric bilinear groups
In combination with Groth-Sahai proofs, automorphic signatures enable
ecient instantiations of generic concepts.
Round-Optimal Blind Signatures
Group Signatures
Anonymous Proxy Signatures with new features:
Delegator anonymity (by randomizing Groth-Sahai proofs)
Blind delegation (using blind signatures)
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
25 / 26
Thank you! ^
¨
Georg Fuchsbauer (ENS)
Automorphic Signatures
UCL, 23.03.2010
26 / 26