3
$\begingroup$

I've been looking for real-world protocols for private function evaluation in the case of a reactive functionality. Please refer to section 2.5.3 of the book Efficient Secure Two-Party Protocols by Hazay and Lindell for a full definition. In a P.F.E. setting, one party, namely $A$, holds a string $x$, and the other party, namely $B$, holds a circuit $C$, such that $C$ takes $x$ as well as $s_t$ as input and outputs $(y, s_{t+1})$.

In the ideal world and when both parties are honest, the trusted third party sends random shares of $s_{t+1}$ to the parties, and reconstructs $s_{t+1}$ for the next round. To make a real-world protocol, $A$ can choose her random share $r_{t+1}$ for the next round, and $B$ obtains $s_{t+1} \oplus r_{t+1}$ from the PFE. Note that $B$ should now send $\widetilde{C}$ (instead of $C$) such that $$ \widetilde{C}(x, r_t, s_t \oplus r_t, r_{t+1}) = (y, s_{t+1} \oplus r_{t+1})$$ For malicious adversaries, the ideal-world solution in the book requires the trusted third party to compute message authentication tags as well and send them to the parties in a zig-zag manner. When I tried to make a real-world version of it, I noticed that I should also include the Boolean circuit of a message authentication scheme in $\widetilde{C}$. From what I've realised so far, MAC circuits are not small, and the circuits in my use-case (i.e., $C$) would need far fewer gates than that of a single MAC instance.

So, there are two questions:

  1. Is there a MAC scheme with a small circuit?
  2. If there isn't any known MAC with a small circuit, can I circumvent encoding (multiple instances of) a MAC in $\widetilde{C}$?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

For this application you can use a one-time MAC since the functionality can MAC each party's share under a different key, and use fresh keys for every round. The simplest one-time MACs are information-theoretic, for example:

$$ \textsf{MAC}\bigl( (a,b), m \bigr) = am+b, $$

where each variable is an element of a finite field. This is a well-known one-time MAC, whose verification circuit is just a few arithmetic operations.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Asking for clarification: if $B$ picks $a_t$ and $b_t$ (u.a.r.) and $\widetilde{C}$ outputs $\widetilde{r_t} = \textsf{MAC}((a_t,b_t), r_t)$ for $A$, then $A$ is unconditionally bound to its choice of $r_t$? This, of course, requires that $A$ picks an O.T.P. just to keep $\widetilde{r_t}$ hidden from $B$. $\endgroup$
    – Mahyar
    Commented Sep 21 at 4:38
  • 1
    $\begingroup$ Given one value-MAC pair under this key, it is not possible to guess a different value-MAC pair under the same key, with probability better than $1/|\mathbb{F}|$. So yes, Alice is bound to her share of the reactive functionality's internal state. But in this particular application you have to be careful about whether Bob is bound to his MAC key (which he must provide in the next round). $\endgroup$
    – Mikero
    Commented Sep 21 at 6:23
  • $\begingroup$ Thanks! Yes, I'm (rather opaquely) assuming that Bob is playing honestly. $\endgroup$
    – Mahyar
    Commented Sep 21 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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