In this paper on pg. 1236, under the section "Security Against Continual Leakage", the authors say:

"We further remark that the weaker security notion previously achieved cannot be extended meaningfully to continual leakage in the MPC setting. That is, it cannot address the setting where the $n$ users do not just perform a one-shot MPC protocol, but rather engage in an unbounded number of MPC protocols for many functions, and during each MPC invocation the adversary leaks $\ell$ bits from each of the honest party’s internal state."

I'm confused about the difference between a "one-shot" MPC protocol vs. "unbounded number" of MPC protocols.

I am envisioning something like:

  • MPC protocol 1: leaks $\ell$ bits from each honest party's internal state
  • MPC protocol 2: leaks $\ell$ new bits from each honest party's internal state
  • MPC protocol 3: leaks $\ell$ new bits from each honest party's internal state
  • MPC protocol $k$: leaks $\ell$ new bits from each honest party's internal state

If there are a total of $n$ honest parties, then you have a total leakage of $n \times \ell \times k$ bits.

But if you consider the "one-shot" MPC protocol, you get just $n \times \ell$ bits leaked.

They give an example of threshold cryptography and say that, when you have a bunch of parties that compute a decryption function jointly, you may end up with the entire decryption key leaked, because every time $\ell$ bits are leaked, you can think of it as if $\ell$ bits of the decryption key were leaked.

Why are the authors even considering this "unbounded number" of MPC protocols ?

  • $\begingroup$ I don't understand the question. "Why are the authors even considering this 'unbounded number' of MPC protocols?" What? The threshold cryptography example or the idea of unbounded number of MPC protocol executions in general? $\endgroup$
    – mikeazo
    Commented Dec 16, 2013 at 17:38

1 Answer 1


Basically, there a many real-world problems where one might want to compute something on sensitive data several times. Indeed, later in the paper you cite, the authors give several example, e.g.:

"Medical Data: One may envision a huge database which contains the medical data of every patient in the US. To compute any global statistic on this data, one would not want to put complete trust in any single database. Instead, it is distributed to $n$ different databases. Each time they need to compute statistics on this data, they engage in an MPC protocol. As in the voting example, since these databases contain very sensitive information, an adversary may try to obtain this information via a leakage attack. Thus, to ensure security, the databases must run an MPC protocol that is secure against continual leakage."

The important words above are "each time". It would not do much good to have a distributed database that was secure only the first time it was queried.


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.