4
$\begingroup$

I'm studying the UC framework by Canetti. While I understand the basic idea, there are still a lot of details that I need to work through.

One thing that's puzzling me is how to achieve concurrency under the UC execution mode. For example, in many distributed algorithms, a machine may broadcast a message and then every receiver may do some computation on the message. The result of the computation may be broadcasted again.

The paper says

In order to simplify the process of determining the next ITI to be activated, we allow an ITI to execute at most a single external-write instruction per activation.

In that case, how does one capture a broadcast functionality, both as an ideal functionality as well as a real protocol?

Improve this question
$\endgroup$
  • $\begingroup$ I'm haven't tried looking at the paper, but the ​ "single external read-write instruction" ​ might be a broadcast. ​ ​ ​ ​ $\endgroup$ – user991 May 25 '17 at 14:02
  • $\begingroup$ From my understanding, the ITM (interactive Turing machine) only has one outgoing message tape, thus only one external write can occur at a time. $\endgroup$ – lamba May 25 '17 at 14:12
  • $\begingroup$ The way I'm imagining it, that tape's contents might include recipients, and messages might be allowed to have more than one recipient. ​ ​ $\endgroup$ – user991 May 25 '17 at 14:23
  • $\begingroup$ I found a more relevant on page 9 "at any point in time throughout the computation only a single machine is active." $\endgroup$ – lamba May 25 '17 at 14:41
1
$\begingroup$

I think this would be the relevant paper to understand how to model synchronicity in the UC model:

Universally composable synchronous computation: Jonathan Katz and Ueli Maurer and Bjoern Tackmann and Vassilis Zikas (TCC 2013)

Basically, they define a "clock" functionality that performs a "tick" (increments a public counter) only after all honest parties indicate that they are done with the current round's activities.

To answer your question about "sending a message to all parties": In this paper, communication channels are modeled by having parties explicitly poll the channel to receive a message when they're ready. So to broadcast a message, send a command to the broadcast functionality. The functionality waits to be activated by honest parties who request to read from the broadcast channel.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks, I think this is what I'm looking for. I haven't read the paper yet, but I have a question regarding the polling mechanism. I can imagine ITI will poll the broadcast functionality every time they're activated. But what if the ITI are purely reactive, that is they only do work after some broadcasted message is received, how do they poll in that case? Does the environment instruct the ITI to poll? $\endgroup$ – lamba May 27 '17 at 8:52
  • 1
    $\begingroup$ Looks like the environment is involved. 'Consequently, the environment can continuously provide "run-time" to protocol machines to make them poll, e.g., at a bounded-delay or eventual-delivery channel.' at the bottom of page 4. $\endgroup$ – lamba May 28 '17 at 9:29
2
$\begingroup$

UC broadcast can be defined by a functionality $\mathcal{F}_{\textrm{BC}}$, which upon receiving a message $x$ from party $P_i$, sends $(x, P_i)$ to all parties and the adversary.

This is formally given in, e.g. Section 3.2 of a paper by Goldwasser and Lindell. However, many higher-level protocols use broadcast without explicitly specifying the functionality, because it is so straightforward.

That paper also contains the following, very simple echo-broadcast protocol for any $t < n$ corruptions:

  • $P_i$ sends $x$ to all other parties
  • Every other party re-sends $x$ to everybody else and checks that they received the same values.
  • If any value is inconsistent, abort. Otherwise, output $x$.

This is secure in a slightly weaker model, where a corrupt party may force some honest parties to abort; however, any honest party who does not abort will learn the correct output.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks! What I don't quite understand is the "send $x$ to other parties" part. I thought the execution model is that the ITM goes into the inactive state after doing a single external write. In that case how can it send a message to all other parties? $\endgroup$ – lamba May 25 '17 at 22:51
  • $\begingroup$ I'm not sure about the details of how this is defined in the model, but many standard UC functionalities send multiple messages on activation. Perhaps to do this more formally the functionality would have to first receive a message from each recipient, in turn. $\endgroup$ – pscholl May 26 '17 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.