Ensuring Secrets on Public Blockchains: Security and Efficiency Goals

https://eprint.iacr.org/2020/464 CAN A PUBLIC BLOCKCHAIN KEEP A SECRET? Fabrice Benhamouda1, Craig Gentry1, Sergey Gorbunov2, Shai Halevi1, Hugo Krawczyk1, Chengyu Lin3, Tal Rabin1, Leonid Reyzin2 1 3 2 TCC, November 16, 2020

What is a Blockchain? Depending on which part you are dealing with Computing platform Buzzword This Photo by Unknown Author is licensed under CC BY-NC Back-end of a payment system Consensus protocol Data structure

A Public Blockchain A distributed network of potentially many nodes Hundreds? Thousands? Millions? Continuously deciding on things These things are called transactions Decisions are made by consensus Published in blocks, visible to all In this talk: Blockchain A large distributed system with (only) broadcast channel

Blockchains as Computing Platforms Computing platform for us is a trusted party This Photo by Unknown Author is licensed under CC BY-NC-ND ?1 ?(?1,?2,?3) ?2 ?3 Can today s public blockchains be trusted parties? Meh Great for integrity/agreement/immutability Secrecy is harder, this is the focus of our work

This Work: Basic Secrecy Setting A client deposits a secret at the blockchain To be revealed only when the time is right More generally, used only in the prescribed manner Example: publish a puzzle, deposit a solution Blockchain reveals the solution if not found by next week Can form the basis for many applications

Security and Efficiency Goals The secret must remain a secret Unknown to the adversary, but still recoverable As long as we have large honest majority among the nodes Even when the adversary is mobile Efficiency: want a scalable solution Total-communication/per-party-work do not increase as time go by, or as more nodes join the network Plausible practicality: can hope to use it in practice No super-heavy tools (such as obfuscation/witness-encryption) We seek solutions based on dynamic proactive secret-sharing

Dynamic Proactive Secret Sharing (DPSS) Secret is shared among dynamically-changing committees Time broken into epochs , committee changes every epoch Minute/hour/day/week, Via a share-refresh protocol reshare reshare reshare reshare ?1 ?2 ?3 ?4 The secret remains a secret as long as honest majority in all these committees Even if different parties are compromised in different epochs A lot of prior work [OY91,CH93,HJKY95,DJ97,SLL10, DGGK10, BDLO15, , MZW+19,GKM+20]

New in This Work DPSS treats committee-selection as out-of-scope Honest-majority-in-each-epoch is a promise Evolving-Committee Proactive Secret Sharing (ECPSS) DPSS + committee-selection protocol We enforce enforce honest majority in committees, as long as we have a sufficiently large global honest majority

The Main Technical Challenge The adversary is mobile with corruption budget of some ?-fraction of the nodes (e.g., ? = 25%) For scalability, a small committee of share holders Much smaller than an ?-fraction of the nodes Adversary has enough budget to corrupt them all If it knows who they are How can the committee do its job, without the adversary learning who they are?

Useful Tool: Self-Selecting Committees A node self-selects to the committee, then prove to everyone that it deserves to be there Proof of work : Moderately hard puzzles are announced, a node is chosen to the committee if it has a solution Cryptographic sortition : Nodes have VRF key-pairs A public input ? is announced Node ? computes ? = ??????? 0,1 Is on the committee if ? < ? If we have ? nodes, we expect ?? committee members

Self-Selection Doesnt Work For Us Previous committee doesn t know who to pass the secret to Next committee cannot tell them that they were chosen Lest the adversary hears about it Another solution that doesn t work: each committee member selects its successor Corrupted members will always corrupt their successors Honest members will choose a corrupted successor w/ prob. ? Committee will eventually have a dishonest majority reshare? reshare reshare reshare reshare ?3 ?4 ?1 ?2

What We Want: Target-Anonymous Channels Would ve been great to have the following channels: ?visible input ports, ? hidden output ports Random assignment of the output ports to an ?-subset of the ? nodes Anyone can send on the ? th input port, not knowing who will receive the message The receivers will be the share holders ?1 ?2 ?1 ?3 ?2 ?4 ?3 ?5 ?6 ?? ??

Constructing Target-Anonymous Channels We assume PKI: every node has a known public key Using anonymous public-key encryption Given ???,???,??, , hard to tell under which ??? it was encrypted To establish a channel to node ??: Choose ephemeral key pair ?? ,?? ?????? $ Encrypt ?? under the public key of ?? to get ?? ???????? Using anonymous PKE, ?? does not betray ?? Broadcast the pair (?? ,??) Anyone can encrypt/broadcast messages under ?? Only ?? can recover ?? and then decrypt Who is going to do choose ?? and do all of this? Choices must be hidden from then adversary

The Overall Solution ?1 ?2 ?3 ?4 Nominating committees reshare reshare reshare reshare Secret-sharing committees ?1 ?2 ?3 ?4 The protocol consists of two parts 1. Nominating committee self-selects Each nominator ?jchooses a random nominee ?? from the ? parties, establishes a target-anonymous channel to it 2. The old sharing-committee passes the secret to the new one over these target-anonymous channels

Resilience of This Solution If adversary controls ?-fraction of the nodes Then it controls ?-fraction of the nominators Adversarial nominators choose adversarial nominees Honest nominators choose adversarial nominees w.p. ? Chosen committee will have 2?-fraction dishonest nodes Note: cannot use proof of proper nomination Even if forced to select honestly, an adversarial nominator could always turn around and corrupt its nominee To get honest majority we need to assume ? < ?.??

Passing the Secret Between Committees reshare See the paper for our new share-refresh protocol Each old-committee-member re-shares its share New-committee-members can combine these shares-of-shares Each member of old committee broadcasts one message With secrets encrypted under keys of target-anonymous channels Including public NIZK proofs that re-sharing was done correctly The ciphertexts that I broadcast in this epoch are consistent with the ones that were broadcast to me in the previous epoch Statement, witness are short , of size linear in the committee-size

The End Result A scalable evolving-committee PSS protocol Assuming that the adversary controls < 0.29 of the nodes Room for improvement here Can be implemented under DDH, DCR, LWE, Requires anonymous encryption under selective opening attacks Can conceivably be made practical Architecture, techniques are broadly applicable Can be used to do secure-MPC on public blockchains The blockchain can sign, decrypt, compute, even obfuscate ?1 ?(?1,?2,?3) ?2 ?3 Public blockchain as a trusted-party

Anonymous PKE Under Selective Opening We broadcast ctxts under anonymous PKE Adversary sees pks, ctxts, then decides who to corrupt Can an adversary that only corrupts ?-fraction of keys, nonetheless manages to read ? fraction of the ctxts? ? ciphertexts ? public keys

Anonymous PKE Under Selective Opening We broadcast ctxts under anonymous PKE Adversary sees pks, ctxts, then decides who to corrupt Can an adversary that only corrupts ?-fraction of keys, nonetheless manages to read ? fraction of the ctxts? ? ciphertexts Can an adversary that corrupts ?? keys, hit ? ? blue keys? Even though they are hidden ? ? public keys

Selective Opening Attacks An adaptive adversary sees keys and ciphertexts, then opens keys one at a time Semi adaptive decides on the set of keys to open at once (rather than one at a time) In the context of secrecy secrecy, it is known that semantic security does not imply secrecy under selective opening Even for semi-adaptive adversaries We ask the same question about anonymity

Selective Opening Attacks An adaptive adversary sees keys and ciphertexts, then opens keys one at a time Semi adaptive decides on the set of keys to open at once (rather than one at a time) Lemma: anonymous PKE anonymous PKE opening opening ?? keys, cannot open much more than keys, cannot open much more than ? + ? ? ciphertext ciphertext- -encrypting keys encrypting keys except with negligible probability Conjectures: the same holds for fully adaptive semi semi- -adaptive adversary adaptive adversary

Some Open Problems/Future Work Prove the conjecture about anonymous-PKE and selective-opening Improve this solution (in the pipeline) Improve resilience of target-anonymous channels From ? < 0.29 to any While keeping it scalable Don t just keep the secret, compute on it Implement this solution ? < 1 2