Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.
share|improve this question
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.) – Andrew Poelstra Nov 30 '13 at 22:03
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)$. – Andrew Poelstra Nov 30 '13 at 22:08
@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. – user1068636 Nov 30 '13 at 22:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.