Revisiting Adaptively Secure Broadcast Protocols

Adaptively Secure Broadcast, Revisited Juan A. Garay (AT&T), Jonathan Katz (UMD), Ranjit Kumaresan (UMD), Hong-Sheng Zhou (UMD)

Talk Outline Preliminaries Broadcast Simulation-based security The Hirt-Zikas result [HZ10] Adaptive attacks on broadcast protocols Impossibility of adaptively secure broadcast! Here: (Re)examining their communication model Is adaptively secure broadcast possible?

Broadcast [PSL80,LSP82] Message m m1 m4 m1 m4 m2 m3 m2 m3 If the sender is honest, then all parties output the sender s message All honest parties always output the same message

Modeling the Problem Communication model Adversary model Point-to-point, secure and authenticated channels Centralized byzantine adversary Corrupts at most t out of n parties Static or adaptive adversary Static: parties corrupted before execution begins Adaptive: parties corrupted during protocol execution Synchronous network

Prior Work Unconditional security iff t < n/3[PSL80, LSP82, ] Computational security for t < n[PSL80, DS83, ] Assuming a public-key infrastructure (PKI) and digital signatures Most prior work focus on property-based notions of security

Simulation-Based Security Awkward or difficult to define adaptive security using property- based definitions If the sender is honest, then but what if the sender starts honest and is later corrupted? Cleaner definitions using the simulation paradigm (Side benefits: secure composition; security under concurrent executions)

The Simulation Paradigm [GMW87] Ideal-world with a trusted third party carrying out task Real-world cryptographic protocol

The Simulation Paradigm (contd) REAL IDEAL

Universally Composable Security [Can01] Environment Concurrent Composition REAL IDEAL

The Broadcast Functionality Functionality FBC : 1.FBC receives m from the sender; 2. D FBC sends m to all recipients.

Adaptively Secure Broadcast? Hirt-Zikas 10: Adaptive attacks on all existing broadcast protocols All existing broadcast protocols are not adaptively secure

An Adaptive Attack Message v Message v v v v' v Later 1st round

Adaptively Secure Broadcast? Hirt-Zikas 10: Adaptive attacks on all existing broadcast protocols Adaptively secure broadcast is impossible for t > n/2

Communication Model: A Closer Look [HZ10] model Atomic delivery model Adversary can corrupt sender & change its messages in the same round. Crucial for their impossibility result Sender s messages cannot be changed once sent [Can00,LLR02, ] No corruption in the middle of a round

Is Adaptive Security Possible? Is adaptively secure broadcast possible for t > n/2 if we assume atomic message delivery? Note: [HZ10] attacks work on known protocols even in this model Yes! Adaptively secure broadcast is possible for t < n

Relaxed Broadcast Functionality FRBC [HZ10] 1.FRBC receives m from the sender; 2. D FRBC sends m to the adversary 3. DThe adversary decides whether to corrupt the sender; if it does, the adversary may change m to any desired value 4.DFRBC sends m to all recipients Existing protocols (e.g., [DS83]) give adaptively secure relaxed broadcast for t < n

Commitments Alice (message m) Bob m m Hiding: m hidden from Bob Binding: Alice can open commitment only to m

Our Broadcast Protocol 1. Sender sends commitment to m using FRBC m 2. Sender sends the decommitment to each receiver via point-to-point channels 3. Each receiver broadcasts the decommitment they received using FRBC 4. All players agree on the first valid decommitment, and output the corresponding message

Avoiding Adaptive Attacks 1. Sender sends commitment to m using FRBC Adversary learns nothing about m m 2. Sender sends the decommitment to each receiver via point-to-point channels All honest parties receive the decommitment 3. Each receiver broadcasts the decommitment they received using FRBC Even if the sender is corrupted, the committed value cannot be changed 4. All players agree on the first valid decommitment, and output the corresponding message

Simulation 1. Sender sends commitment to m using FRBC Simulator sends dummy commitments m 2. Simulator gets m from FBC and generates a decommitment to m; it then sends this to all parties via point-to-point channels UC commitments allow simulator to open com to any m 3. Each receiver broadcasts decommitment viaFRBC 4. All players agree on a valid decommitment, and output the corresponding message

Setup Assumptions? As written, we use UC commitments UC commitment require additional setup assumptions + stronger cryptographic assumptions that we would like to avoid! In fact, honest-binding commitments suffice Binding once the sender acts honestly during the commit phase Can be realized with no additional setup, based on OWF Example based on Pedersen s commitment: Honest sender Input m Choose h,x com = (h, gmhx) Simulator (No input) Choose r,y com = (gr, gy) Equivocation On input m Set x = (y-m)/r Output (gr,x)

Our Result (Summarized) Assuming a PKI and digital signatures, there exists a (universally composable) broadcast protocol secure against adaptive corruption of any t < n parties

Applications to Secure Computation Protocols for secure computation typically designed/analyzed assuming a broadcast channel Plug in a protocol that realizes FBC security when run over a point-to- point network Can we use a protocol realizing FRBC instead? Better efficiency ? Secure computation in [HZ10] network model? We observe that FRBC suffices for most specific constructions Messages broadcast are always commitments to some value

Summary Adaptively secure broadcast for t < n Assuming the standard synchronous communication model Our result: Matches the threshold for statically secure broadcast Requires no additional setup or assumptions Can be safely used within arbitrary other protocols

Thank You