SESSION ID: CRYP-F03 Universally Composable Accumulators Foteini Baldimtsi, Ran Canetti, Sophia Yakoubov Sophia Yakoubov Postdoc Aarhus University @sophiay135 #RSAC #RSAC Our Contributions Accumulators are used in… – (Anonymous) Credentials – Cryptocurrencies – Group and Ring Signatures Definition styles: Statement Proof of secure use in system Game-Based Definitions Simple Hard 2 UC Definitions Complex Easy #RSAC Our Contributions First UC definition for accumulators Proof of equivalence of game-based and UC definitions Statement Proof of secure use in system Game-Based Definitions Simple Hard 3 = UC Definitions Complex Easy #RSAC Our Contributions First UC definition for accumulators Proof of equivalence of game-based and UC definitions – Best of both worlds! – All existing constructions are automatically UC-secure Statement Proof of secure use in system Game-Based Definitions Simple Hard 4 = UC Definitions Complex Easy #RSAC Our Contributions First UC definition for accumulators Proof of equivalence of game-based and UC definitions Demonstration of Composition – Modular accumulators – Anonymous credentials Statement Proof of secure use in system Game-Based Definitions Simple Hard 5 = UC Definitions Complex Easy OUTLINE #RSAC What is an accumulator? First UC definition for accumulators Proof of equivalence of game-based and UC definitions Demonstration of Composition 6 OUTLINE #RSAC What is an accumulator? First UC definition for accumulators Proof of equivalence of game-based and UC definitions Demonstration of Composition 7 OUTLINE #RSAC What is an accumulator? First UC definition for accumulators Proof of equivalence of game-based and UC definitions Demonstration of Composition 8 #RSAC Application: Credentials Alice Bob 9 #RSAC Application: Credentials I’m Alice, a member of the gym! Yep, you’re on Merlin’s list. Go ahead. Alice Bob 10 #RSAC Application: Credentials !!! Alice Bob 11 Accumulators: a digest of set S S = {Alice, Bob, …} Witness wA Can I have the membership witness for “Alice”? S 12 #RSAC wA #RSAC Application: Credentials wA I’m Alice, a member of the gym! wA So you are. Go ahead. S 13 Everything is an Accumulator! #RSAC Merkle Trees S h1 pk Alice A Go ahead. S 14 Everything is an Accumulator! #RSAC Merkle Trees Digital Signatures Merlin’s signature σ on “Alice” Go ahead. S 15 = PKM Everything is an Accumulator! Merkle Trees Digital Signatures Strong Add ✓ ✗ ✗ #RSAC ✓ 16 Everything is an Accumulator! Merkle Trees Digital Signatures Strong Add ✓ ✗ ✗ #RSAC ✓ RSA Accumulator – p1, p2 secret primes – n = p1p2 – S = v (mod n) ^“Alice” wA ^“Bob” ← “Charlie” wB 17 Everything is an Accumulator! Merkle Trees Digital Signatures RSA Accumulator Strong Add ✓ ✗ ✗ ✗ #RSAC ✓ – p1, p2 secret primes – n = p1p2 – S = v (mod n) ^“Alice” wA ^“Bob” ← “Charlie” wB 18 Everything is an Accumulator! Merkle Trees Digital Signatures RSA Accumulator Strong Add Del ✓ ✗ ✗ Hiding Update Message - ✗ ✓ ✓ ✗ ✗ ✓ ✗ – p1, p2 secret primes – n = p1p2 – S = v (mod n) ^“Alice” wA ✓ Can I join? wC ← v v ← v“Charlie” mod n ← “Charlie” ^“Bob” wB 19 #RSAC Everything is an Accumulator! Merkle Trees Digital Signatures RSA Accumulator Strong Add Del ✓ ✗ ✗ ✓ ✗ ✓ ✗ Hiding Update Message - Proofs of NonMembership ✓ ✓ ✗ ✗ ✗ ✗ ✓ There are many other interesting accumulator properties! 20 #RSAC