1
$\begingroup$

Adaptive adversaries are a class of adversaries who can decide to corrupt parties in the protocol execution process. However, I want more information about this model and the proof skills. There are some questions: (1) Where can I find the corresponding security definition? When was it first proposed and by whom? (2) Are there any papers adopting such a security model? (3) How can I prove that a protocol is secure in the presence of adaptively semi-honest/malicious adversaries?

$\endgroup$
1
  • $\begingroup$ You can refer to this paper. $\endgroup$
    – X.H. Yue
    Commented Mar 12 at 4:11

1 Answer 1

1
$\begingroup$

What do you mean about "proof skills"?

Anyway, the adaptive security model is well motivated: it gives the adversary additional power that is very natural in practice. Furthermore, there are a few approaches to MPC that entirely break in the presence of an adversary that can corrupt parties at any point of the protocol. A prominent example of this are protocols that rely on sampling committees at random, with the hope that the resulting set has a small number of corruptions. This is true if the adversary sets the corrupted parties at the beginning, but it breaks if the adversary can choose the corrupted parties after the committee has been selected.

Another example where adaptive security is hard to achieve is when encrypted messages are transmitted. For example, say a party receives an encryption $c$ of a given secret $m$, and later on this receiving party becomes corrupted. Part of the simulation paradigm relies on being able to count on some degrees of freedom on the messages corrupted parties receive, in particular, the ability to set these messages at will so that they look consistent with the protocol (i.e. the "real world"). The message $m$ was computed when the receiving party was honest, but now this party has been found to be corrupt. In these contexts many protocols exploit the fact that the adversary does not know $m$ (as it was encrypted), and hence any other $m$ we set may suffice. However, the adversary does have some information about $m$: the ciphertext $c$. If you want to change $m$ to a different message, you need to make sure you do it in such a way that the new message remains consistent with the ciphertext $c$. This is not a standard property of any CPA-secure encryption scheme! The right term is non-committing encryption, you can duckduckgo-it yourself. The point here is that there are subtleties involved when attempting to prove adaptive security, especially when using certain techniques such as committee selection or encryption that are known to have subtle issues when dealing with adaptive security.

Now, to address your questions concretely:

(1) A good resource is the book "Cramer, Ronald, and Ivan Bjerre Damgård. Secure multiparty computation. Cambridge University Press, 2015." Look in particular at Section 4.5 in this online draft. There is also the wonderful "Pragmatic MPC" book, which has a short discussion on it.

(2) The adaptive security model is quite common in the literature. MPC protocols tend to be adaptively secure "out of the box", without implying lots of changes in their security proof. This is particularly true for information-theoretic protocols that do not rely on the "committee" approach from above. See for instance "Efficient Multiparty Computations Secure Against an Adaptive Adversary" (also cited above in a comment). Now, for computationally secure protocols the approach tends to be more subtle, due to anomalies such as the encryption example from above. For instance, the protocol "SPDZ" is not adaptively secure, presumably because of the use of somewhat homomorphic encryption in the preprocessing phase.

(3) As mentioned, most of the time proofs go through in the adaptive model unless you're using a few techniques that are known to "cause trouble" in adaptive settings, such as committees or committing encryption, among others. Proofs are typically similar, with the extra overhead that you must account for the event in which an honest party becomes corrupted, and you have to be able to "explain" the messages this party has received thus far during the simulation. Some examples of when this becomes challenging are, for instance, "Adaptively Secure MPC with Sublinear Communication Complexity" or "Two-Round Adaptively Secure MPC from Isogenies, LPN, or CDH"

$\endgroup$
1
  • $\begingroup$ Thanks for your answer. Just like the security definition in the presence of static semi-honest adversaries, i.e., Given only the input and output of the corrupted party, a simulator in the ideal world can generate a view that is indistinguishable from the view of the adversary in the real world. Such a view includes the input, randomness, and the received messages of the corrupted party. The "proof skills" means a similar secure definition in the presence of adaptive semi-honest adversaries, and, what does the view include in the adaptive case? $\endgroup$
    – Jeffrey
    Commented Mar 12 at 23:55

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.