3
$\begingroup$

On page 29 of Book Efficient Secure Two-Party Protocols by Y. Lindell and C. Hazay, there's this proposition:

Let π be a protocol that securely computes a functionality f in the presence of malicious adversaries. Then π securely computes f in the presence of augmented semi-honest adversaries.

There's a proof following this proposition. In the proof, they say that the distribution over messages will be identical since the real adversary will follow the protocol exactly. But since an augmented semi honest adversary might change the input, won't the distribution over messages change as well? Also, why can't a similar proof be drawn for security in case of semi-honest adversaries?

Moreover, is the definition of security in case of augmented semi-honest adversaries analogous to that in case of malicious adversaries? In the book, I was unable to find a formal definition of security for augmented semi honest adversaries.

P.S: This is the proof:

Let π be a protocol that securely computes f in the presence of malicious adversaries. Let A be an augmented semi-honest real adversary and let S be the simulator for A that is guaranteed to exist by the security of π (for every malicious A there exists such an S, and in particular for an augmented semi-honest A). We construct a simulator S′ for the augmented semi-honest setting, by simply having S′ run S. However, in order for this to work, we have to show that S′ can do everything that S can do. In the ma- licious ideal model, S can choose whatever input it wishes for the corrupted party; since S′ is augmented semi-honest, it too can modify the input. In addition, S can cause the honest party to output abort. However, S′ cannot do this. Nevertheless, this is not a problem because when S is the simulator for an augmented semi-honest A it can cause the honest party to output abort with at most negligible probability. In order to see this, note that when two honest parties run the protocol, neither outputs abort with non-negligible probability. Thus, when an honest party runs together with an augmented semi-honest adversary, it too outputs abort with at most negligible probabil- ity. This is due to the fact that the distribution over the messages it receives in both cases is identical (because a semi-honest real adversary follows the protocol instructions just like an honest party). This implies that the simu- lator for the malicious case, when applied to an augmented semi-honest real adversary, causes an abort with at most negligible probability. Thus, the aug- mented semi-honest simulator can run the simulator for the malicious case, as required.

$\endgroup$
  • $\begingroup$ Since not everyone has the book, it would be helpful if you described what an augmented semi-honest adversary is. $\endgroup$ – mikeazo Sep 1 '17 at 12:47
  • $\begingroup$ An augmented semi-honest adversary is one which can change its input before the protocol execution. Once the protocol starts, it follows the protocol exactly, but tries to gain useful insight from the messages it receives. $\endgroup$ – Deevashwer Sep 1 '17 at 12:51
3
$\begingroup$

As pointed out in the comments, an augmented semi-honest adversary is one who can change its input before the protocol execution begins, but from then on the adversary runs the protocol specification exactly.

Note that if a protocol is secure for malicious adversaries, then the simulator must be able to work also for an adversary who changes its input and then behaves honestly. Thus, the protocol is secure also for augmented semi-honest adversaries.

The reason that this does not work for semi-honest adversaries is because the ideal-world simulator for a semi-honest adversary cannot change the input. That is, in the case of malicious adversaries, both the real adversary and the ideal simulator are stronger than for semi-honest adversaries. This fact means that security for malicious adversaries does not necessarily imply security for semi-honest adversaries (because the ideal simulator cannot run in the semi-honest case if it needs to change the input of the corrupted party). In the book, we give an explicit counter-example of a protocol that is secure for malicious adversaries but not for semi-honest. I know that this is extremely counter-intuitive, but that's the reality.

$\endgroup$
  • $\begingroup$ I get exactly why security in malicious case doesn't imply security in semi honest case. The problem I had before was that why doesn't this proof work for semi honest case. We argued that the simulator can abort a protocol with negligible probability. Why can't we say that a semi-honest simulator S' can change the input as well as abort a protocol with negligible probability? I get it now, though. Thank You very much for your response. $\endgroup$ – Deevashwer Sep 2 '17 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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