Home

slides

1. skx warr_ x pk Del wary sky warn y M PSig Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 9 26 Algorithms of Anonymous Proxy Signature Scheme Issuer ik Reg User pk pk sk 1 gt Setup sk warr_ x pk gt Del sky war y M PSig pk M o gt PVer be 0 1 Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 9 26 Issuer ik 1 skx warr_ x pk sky WwWarfx y M pk M o ok Georg Fuchsbauer ENS Reg gt User pk sk Setup gt Del gt gt PSg o gt PVer be 0 1 Open a list of users or L failure Automorphic Signatures Algorithms of Anonymous Proxy Signature Scheme UCL 23 03 2010 9 26 Security for Anonymous Proxy Signatures Anonymity intermediate delegators and proxy signer remain anonymous Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 Security for Anonymous Proxy Signatures Anonymity intermediate delegators and proxy signer remain anonymous Traceability every valid signature can be traced to its intermediate delegators and proxy signer Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 10 26 Security for Anonymous Proxy Signatures Anonymity intermediate delegators and proxy sig
2. Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 8 26 Proxy Signatures Consecutive Delegations Delegator pkp Delegator 2 Delegator 3 ANONYMOUS NC Proxy Signer Opener ok DERI 2 Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 8 26 Algorithms of Anonymous Proxy Signature Scheme 1 gt Setup pp ik ok Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 9 26 Algorithms of Anonymous Proxy Signature Scheme Issuer ik 1 pk sk Setup User Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 9 26 Algorithms of Anonymous Proxy Signature Scheme Issuer ik Reg User pk pk sk 1 gt Setup pp ik ok sk pk Del gt Wally y Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 9 26 Algorithms of Anonymous Proxy Signature Scheme Issuer ik Reg User pk pk sk 1 gt Setup sk warr_ x pk Del gt Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 9 26 Algorithms of Anonymous Proxy Signature Scheme Issuer ik Reg User pk pk sk 1 gt Setup
3. Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 20 26 Variants of Boneh Boyen Boneh Boyen Weak Signatures Given G X xG E G and q 1 distinct id G cj G x Zp output a new pair 1 6 Gx Zp x c Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 Variants of Boneh Boyen The Hidden SDH BW07 Given G H X xG Gand q 1 distinct mecs E G qe ciH output new triple G cG cH x c Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 21 26 The Hidden SDH BW07 Variants of Boneh Boyen Given G H X xG G and q 1 distinct triples E ciH output a new triple 4G cG cH G e All components are group elements e Validity of a triple A C D is verifiable by PPEs e A X C e G e C H e G D Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 21 26 Assumptions 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 el Ch vi E G x le output a new triple K vG v G x es Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 22 26 Assumptions F Pointcheval Vergnaud Transferable Constant Size Fair E Cash CANS 09 SDH implies hardness of the following Given G K X
4. encrypt group elements and to e prove that they satisfy PPEs 5 public and decryption key ck ek ExtSetup Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 19 26 Groth Sahai proofs allow us to e commit to encrypt group elements and to e prove that they satisfy PPEs 5 public and decryption key ck ek ExtSetup To instantiate generic construction we need signature scheme s t Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 19 26 Groth Sahai proofs allow us to e commit to encrypt group elements and to e prove that they satisfy PPEs 5 public and decryption key ck ek ExtSetup To instantiate generic construction we need signature scheme s t e signatures are group elements Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 19 26 Groth Sahai proofs allow us to e commit to encrypt group elements and to e prove that they satisfy PPEs 5 public and decryption key ck ek ExtSetup To instantiate generic construction we need signature scheme s t signatures are group elements e verification by PPE Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 19 26 Groth Sahai proofs allow us to e commit to encrypt group elements and to e prove that they satisfy PPEs 5 public and decryption key ck ek ExtSetup To
5. instantiate generic construction we need signature scheme s t signatures are group elements e verification by PPE e able to sign public keys Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 19 26 Groth Sahai proofs allow us to e commit to encrypt group elements and to e prove that they satisfy PPEs 5 public and decryption key ck ek ExtSetup To instantiate generic construction we need signature scheme s t signatures are group elements e verification by PPE e able to sign public keys EUF CMA Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 19 26 Groth Sahai proofs allow us to e commit to encrypt group elements and to e prove that they satisfy PPEs 5 public and decryption key ck ek ExtSetup To instantiate generic construction we need signature scheme s t signatures are group elements e verification by PPE e able to sign public keys EUF CMA Automorphic Signatures Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 19 26 Boneh Boyen Signatures The q Strong Diffie Hellman Problem SDH BB04 Given G xG x2G x1G GIF for x 25 output G c G x Zp 1 Gare Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 20 26 Boneh Boyen Signatures The q Strong Diffie Hellman Problem SDH BB04 Given G xG x2G x1G GU f
6. notions Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 5 26 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 e 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 MOS Reg Graup members ski sign msg Verification Verify pk msg 1 Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 6 26 Proxy Signatures Delegator pkp M Delegatee Signer sign 58 Verify pkp msg Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 26 Proxy Signatures Consec Delegator pkp Delegator 2 re Delegator 3 Proxy Signer Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 8 26 Proxy Signatures Consecutive Delegations Delegator pkp E Delegator 2 Tr Delegator 3 E ANONYMOUS u Proxy Signer
7. Automorphic Signatures in Bilinear Groups Georg Fuchsbauer ENS Georg Fuchsbauer Ecole normale sup rieure UCL 23 03 2010 Automorphic Signatures UCL 23 03 2010 1 26 Motivation Anonymous Proxy Signatures Groth Sahai Witness Indistinguishable Proofs Automorphic Signatures Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 2 26 Motivation Anonymous Proxy 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 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 gt intermediate delegators 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 delega
8. CL 23 03 2010 16 26 Groth Sahai pairing product equation is an equation over variables Xn G of the form ITIT x9 E EE determined y Zp and tr Gr for 1 i j lt n Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 16 26 Groth Sahai pairing product equation is an equation over variables Xn G of the form Tex TII ee xy E EE determined by yj Zp and tr for 1 i j lt n Groth Sahai NIWI proof of satisfiability of PPE Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 16 26 Groth Sahai 11 Setup on input the bilinear group output a commitment key ck Com on input ck X G randomness p output commitment cx to X Prove on input ck Xj pi 7_ equation E output a proof Verify on input ck C E output 0 or 1 Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 17 26 Groth Sahai Il Setup on input the bilinear group output a commitment key ck Com on input ck X G randomness p output commitment cx to X Prove on input ck Xj 1 equation E output a proof Verify on input ck C E output 0 or 1 Correctness Honestly generated proofs are accepted by Verify Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 17 26 Groth Sahai 11 Setup on input the bilinear group output a commitm
9. F D an Ses Georg Fuchsbauer ENS Automorphic Signatures 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 which define the message space as DH mG mH m Zp KeyGen secret key x Zp public key X xG Y yH e Sign M DH choose c r Zp set C cF D cH 1G 5 rH A signature on a message M N DH is valid iff e C H e F D e A Y D e K M H e T S IRA AGs The above scheme is EUF CMA under ADHSDH and WFCDH Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 24 26 e Messages and public keys G signatures in Verification 7 pairing evaluations Also instantiable in asymmetric bilinear groups In combination with Groth Sahai proofs automorphic signatures enable efficient instantiations of generic concepts UCL 23 03 2010 25 26 Automorphic Signatures Georg Fuchsbauer ENS Applications In combination with Groth Sahai proofs automorphic signatures enable efficient instantiations of generic concepts e Round Optimal Blind Signatures Group Signatures e Anonymous Proxy Signatures with new features e Delegator anonymity by randomizing Groth Sahai proofs Blind delegation using blind signatures Georg Fuchsbauer ENS Automorphic Si
10. K proof 12 26 Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 Generic Construction Overview Setup Register Delegate Proxy Sign Verify Open Generates decryption key for opening authority signing key for issuer Parameters resp public keys crs for NIZK Issuer signs user s public key gt certificate Sign delegatee s public key warrant Re delegate additionally forward received warrants Sign message encrypt e interm delegators verification keys and certificates e warrants signature on message Output e ciphertext e NIZK proof that plaintext contains valid signatures Verify NIZK proof Decrypt ciphertext 12 26 Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 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 e Signature scheme inefficient due to bit by bit techniques Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 13 26 Groth Sahai Witness Indistinguishable Proofs Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 NIWI Non Interactive Witness Indistinguishable Proofs An NP language L is defined by relation R as L x dw x w R A NIWI for L consists of Setup Pro
11. ent key ck Com on input ck X G randomness p output commitment cx to X Prove on input ck Xj 1 equation E output a proof Verify on input ck E output 0 or 1 Correctness Honestly generated proofs are accepted by Verify Soundness ExtSetup outputs ck ek s t given and s t Verify ck 1 then Extract ek returns X that satisfies E Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 17 26 Groth Sahai Il Setup on input the bilinear group output a commitment key ck Com on input ck X G randomness p output commitment cx to X Prove on input ck 1 7 1 equation E output a proof Verify on input ck E output 0 or 1 Correctness Honestly generated proofs are accepted by Verify Soundness ExtSetup outputs ck ek s t given and s t Verify ck c E 1 then Extract ek returns X that satisfies E Witness Indistinguishability WISetup outputs ck indist from ck s t Com ck produces statistically hiding commitments i e Ve Com ck X p c e Given pi i Xj s t Com ck Xi pi Com ck and X and X satisfy E then Prove ck Xi pi i E Prove ck X7 p E Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 17 26 Automorphic Signatures Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 18 26 Groth Sahai proofs allow us to e commit to
12. gnatures UCL 23 03 2010 25 26 Thank you Fuchsbauer ENS Automorphic Signatures
13. ner 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 e Public key encryption IND CPA e Non interactive zero knowledge proofs Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 11 26 ction Ingredients Generic Construction using e Digital signatures EUF CMA e Public key encryption IND CPA e 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 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 certificate Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 12 26 Generic Construction Overview Setup Generates decryption key for opening a
14. or x 25 output G er Boneh Boyen Weak Signatures Given G xG G and 4 1 distinct pairs G c E G x Zp xig amp ci G x Zp output a new pair Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 20 26 Boneh Boyen Signatures The q Strong Diffie Hellman Problem SDH BB04 Given G xG x2G x1G GU for x 25 output 6 EC 2 Boneh Boyen Weak Signatures Given G xG G and 4 1 distinct pairs L G c E G x Zp xig amp ci G x Zp output a new pair Boneh Boyen Short Signatures Secret key 22 public key X xG Y e Sign m Zp choose r Zp signature A e Verify on m under X Y by checking e A X mG rY e 6 G Gir x E ry Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 20 26 Boneh Boyen Signatures The q Strong Diffie Hellman Problem SDH BB04 Given G xG x G x G GIH for x Z5 output G Boneh Boyen Weak Signatures Given G xG G and 4 1 distinct pairs new pair 6 c Gx Zp X G G ci E G x 2 output Boneh Boyen Short Signatures Secret key x y An public key X xG Y e Sign m Zp choose r Zp signature A e Verify A r on m under X Y by checking e A X mG t e 6 x m e G gt G 1 x m ry
15. tor s behalf Consecutiveness A delegatee may re delegate the received signing rights gt 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 gt 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 Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 5 26 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
16. uthority signing key for issuer Parameters resp public keys crs for NIZK Register Issuer signs user s public key certificate Delegate Sign delegatee s public key warrant Re delegate additionally forward received warrants 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 certificate Delegate Sign delegatee s public key warrant Re delegate additionally forward received warrants Proxy Sign Sign message encrypt e interm delegators verification keys and certificates e warrants signature on message Output e ciphertext e NIZK proof that plaintext contains valid signatures Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 12 26 Generic Construction Overview Setup Register Delegate Proxy Sign Verify Generates decryption key for opening authority signing key for issuer Parameters resp public keys crs for NIZK Issuer signs user s public key gt certificate Sign delegatee s public key warrant Re delegate additionally forward received warrants Sign message encrypt e interm delegators verification keys and certificates e warrants signature on message Output e ciphertext e NIZK proof that plaintext contains valid signatures Verify NIZ
17. ve and Verify e Setup outputs a common reference string crs e Prove crs x w outputs a proof 7 e Verify crs 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 is defined by relation R as L x dw x w R A NIWI for consists of Setup Prove and Verify e Setup outputs a common reference string crs e Prove crs x w outputs a proof 7 e Verify crs and outputs 1 or 0 It satisfies e completeness soundness witness indistinguishability Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 15 26 Groth Sahai Bilinear Groups and the Decision Linear Assumption BBS04 e Bilinear group p Gr e e G and Gr cyclic groups of prime order p e G x G gt Gr bilinear i e VX Y G Va b Z BY e X Y o G G Gr e G G Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 16 26 Groth Sahai Bilinear Groups and the Decision Linear Assumption BBS04 e Bilinear group p e e G and Gr cyclic groups of prime order p e G x G gt Gr bilinear i e VX Y Va b Z G Gr e G G Given U V aU it is hard to decide whether a f Georg Fuchsbauer ENS Automorphic Signatures U
18. xG G and q 1 triples 1 K v G vi G x zs output a new triple XTC K vG c v eGx ms X rc Asymm Double Hidden SDH ADHSDH Given G K F X xG Y xH 4 tuples Ze K viG GH viH output a new tuple XTC 1 K vG cF cH vG vH X rc Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 22 26 Assumptions 11 Verification C D V W satisfies e e A Y D e K vG xH cH e K e e C H e cF H e F D e e V H e vG H e G W Georg Fuchsbauer ENS Automorphic Signatures UCL 23 03 2010 Assumptions 11 Verification C D V W satisfies e e A Y D e K vG xH cH e K e e C H e cF H e F D e e V H e vG H e G W Weak Flexible CDH WFCDH Given G aG bG output aR bR abR G with R 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 which define the message space as DH mG mH m Zp KeyGen secret key x Zp public key X xG Y yH e Sign M DH choose c r Zp set C cF D cH 1G 5 rH A signature on a message DH is valid iff e C H e

slides

Contents

Download Pdf Manuals

Related Search

Related Contents