Secure Computation: Reactive Functionalities in the Hybrid Model for Standalone Security

Question

A common approach to make (secure computation) protocol descriptions and proofs simpler is to describe them in a hybrid model, where the protocol in the real world has access to some auxiliary ideal functionality F (e.g. an ideal OT functionality). Lets say I only care about standalone security (vs. UC). Assuming all calls to F are sequential (i.e. not interleaved or in parallel) and the parties do not communicate with each other in between starting a call and finishing it, then (as far as I understand) I can use regular sequential composition of standalone secure protocols to instantiate the hybrids with standalone secure protocols to obtain an overall standalone secure protocol.

My problem is with reactive functionalities, i.e. functionalities that keep a state and, for the sake of concreteness, with commitments. Say, for example, I want to prove Blum's coin tossing protocol secure in a commitment hybrid model (see here for the protocol and a proof, which is not in the hybrid model).

Protocol recap: Alice and Bob want to toss a fair coin:

1. Alice commits to a random bit $r_a$.
2. Bob publishes a random bit $r_b$.
3. Alice opens commitment and the output of the protocol is defined as $r_a \oplus r_b$

It seems I run into a problem, because I cannot instantiate my hybrid with a standalone secure commitment scheme, because in between Alice doing the commitment and Alice opening it, the parties communicate.

What is the most common way of circumventing the issue? The only thing I could find right now was in Complexity of Multi-Party Computation Functionalities, where the authors state (in Footnote 8 on page 6):

A reactive functionality can be reduced to a non-reactive functionality by secret-sharing the internal state of the functionality among all n parties

I don't understand what this means. What does it mean (concretely for the example of coin tossing) and is this the most common approach of handling my described issue in the coin tossing example?

Answer 1

First, your question about that footnote. I guess I can expand on it since I'm probably the one who wrote the footnote.

You can model a reactive functionality as follows:

1. Fix an initial value for the (private, internal) state $s$
2. Repeat forever:
   • Receive input $x$ from Alice and $y$ from Bob
   • Compute $(s', a, b) \gets f(s, x,y)$
   • Give output $a$ to Alice and $b$ to Bob, and set $s := s'$

Here $f$ is a deterministic function that characterizes this functionality. The initial value of $s$ is public information. What is being proposed in that footnote is the following protocol for the reactive functionality:

1. Alice & Bob fix secret shares $s_A, s_B$ for the initial value of $s$

2. Repeat forever:

   • Perform a secure computation of the non-reactive functionality:

     $g\Big( (s_A, x), (s_B,y) \Big) = \Big( (a,s'_A), (b, s'_B) \Big)$, where $(s',a,b) \gets f\big(\textsf{Reconstruct}(s_A,s_B), x,y\big)$ and $(s'_A, s'_B) \gets \textsf{Share}(s')$

     in other words, Alice gives input $(s_A,x)$ and Bob gives input $(s_B,y)$ to this computation. Alice receives output $(a, s'_A)$ and Bob receives $(b,s'_B)$.

   • Alice updates her share $s_A := s'_A$ and Bob does too: $s_B := s'_B$

This protocol's invariant is that at every step the parties hold secret shares of the reactive functionality's internal state. At each step they perform a non-reactive computation that reconstructs the internal state and performs one step of the reactive functionality.

For semi-honest security any standard secret-sharing scheme is fine to use here. For malicious security, you need to be able to detect tampering of shares (since nothing prevents Alice from receiving $s'_A$ as output in one round and giving something other than $s'_A$ as input to the next round).

---

Now for your specific concern about commitment. You are right that there is communication between the parties during the lifetime of the commitment functionality. And if you think of the entire lifetime of the commitment functionality as one unit, this is problematic for rewinding/simulation in the standalone setting.

But the commitment functionality has two phases: commit phase & reveal phase. The way around the issue is to require simulators that are local to each of these phases. That is, when you are simulating the reveal phase, you can't rewind to before the reveal phase (although you may have done some rewinding in the commit phase, you are now stuck with that history after you declare the commit phase to be done).

If you look at the typical security definitions for commitment, that is exactly what they say.

• In a simulation-based definition for commitment, we define binding by means of an extraction game. A corrupt committer can't distinguish between committing to an honest receiver vs committing to a rewinding simulator which extracts the committed value. This is really just a statement about the commit phase only (well, mostly).

• We define hiding by means of an equivocation game. A corrupt receiver can't distinguish between talking to an honest committer vs talking to a locally-rewinding simulator which doesn't get the value until the reveal phase starts. Again, this simulator is allowed to rewind in the commit phase, and in the reveal phase, but it is not allowed to rewind the reveal phase all the way back in time to the commit phase.

If you are wondering whether this means that we're already requiring stronger UC security rather than standalone, it's helpful to think of a commitment protocol that has a 10-round commit phase and 10-round reveal phase. If this protocol was UC-secure, you could use it in a larger protocol, and ask the parties to send additional messages in round 7 of the commit phase. But it's no good for the standalone definition I gave, since there may be rewinding taking us back and forth across round 7 many times. So this standalone definition says: each individual phase of the reactive functionality should be "atomic". That is indeed what happens in the description of your coin-tossing protocol: do the commit phase, wait for it to be done, only then send your random bit. So that is why your coin-tossing protocol is standalone-secure when instantiated with standalone-secure commitment.

In summary, communication between parties is kosher during the lifetime of the reactive functionality, but only as long as it is in between the distinct "phases" of the reactive functionality.