In the paper “Multiparty Computation Secure Against Continual Memory Leakage” on pg. 1237, the footnote #1 discuss why it is not possible to construct a leakage resilient two-party protocol. But I'm confused about the 2nd half.

Assume the adversary controls party $P_1$. In this case, he knows the entire secret state $s_1$ of $P_1$, and can choose his leakage function L to depend on $s_1$: i.e., L=$L_{s_1}$ .

This makes sense to me. If the adversary controls $P_1$ obviously he knows secret state $s_1$ and can use $s_1$ to his advantage to construct a leakage function $L_{s_1}$. The only thing left to do is to leak on the other unknown secret states (like $s_2$). So he creates a leakage function that takes as input $s_2$ --> L=$L_{s_1}(s_2)$. But the next part talks about a shrinking function $g$ which doesn't make sense to me.

Note that L takes as input the secret state $s_2$ of $P_2$, and thus the adversary can leak any (shrinking) function $g(s_1, s_2)$ by setting $L_{s1}(s_2)$ = $g(s_1, s_2)$

What is the point of setting L = g ? Couldn't they just do L = $L(s_1,s_2)$? Why introduce another function?

The next part really confuses me…

But, recall that from the secret states ($s_1 , s_2$ ) the parties can compute any function of the original inputs ($x_1 , x_2$ ).

Two questions regarding the specific quote above:

  1. What does this mean exactly?
  2. Where are they telling me to recall this information from? I don't see any references.
  • $\begingroup$ As for setting $L = g$, this is just a bit awkward notation. The reason is that $L$ was not actually defined up to this point. (It was "defined" to depend on $s_1$ and $s_2$ but this does not tell you anything.) $\endgroup$ Commented Nov 30, 2013 at 22:03
  • $\begingroup$ As for your two questions, the premise of multiparty computation is that given the internal state of all actors (including their secrets $s_i$) you could just as well simulate the computation yourself without involving multiple parties. I guess if this scheme is supposed to work for arbitrary computations, this is the same as saying that you can compute any function of $(x_1,x_2)$ given $(s_1,s_2)$. $\endgroup$ Commented Nov 30, 2013 at 22:08
  • $\begingroup$ @AndrewPoelstra - If you know the internal state of all parties including secrets $s_i$ then you could simulate the computation. But in this particular proof the adversary doesn't fully know $s_2$ of $P_2$. There is only leakage on $s_2$. Is that why they conclude by saying "Clearly such leakage cannot be simulated in the ideal world" ? I feel like you have answered my other questions, so if you post an answer I'll go ahead and mark it correct. Thanks. $\endgroup$ Commented Nov 30, 2013 at 22:17


Your Answer

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