5
$\begingroup$

Imagine the following setting: a party considers a secret sharing or multiparty protocol that is secure against semi-honest adversaries. The adversary selectively chooses the inputs such that it could learn the inputs of its counterparts from what is derived from the output.

A simple example could be taken from any Linear Secret Sharing Scheme Alice secret shares $x$ and Bob $y$ and want to compute $x+y$. Under this scenario, Alice could choose $x=0$, so that she learns Bob's input.

A more complex scenario is what sometimes is described as the full universe attack on Private Set Intersection (the problem of 2 parties computing the intersection of their sets). The attack in this case is as follows: Alice holds a vector $X$ and Bob a vector $Y$, and want to compute the intersection $X ∩ Y$. In this case the attack consists on Alice replacing its set $X$ by a set $X'$ containing all possible inputs on the universe.

From my understanding of what the security definition of MPC is (and the use of an ideal functionality) this attack would be possible under a semi-honest model. My question is the following: Is such attack possible when a malicious adversary is considered? And more importantly, can I consider such adversarial behavior as malicious, or is it indifferent from the MPC security model?

From my understanding of the implications of a malicious adversary and the capabilities of protocols that are secure against malicious adversaries, such as BGW, SPDZ or MASCOT, such an attack would still be possible. However I have recently come across this work on PSI https://eprint.iacr.org/2013/515.pdf, where they classify such attack as a malicious attack, given that the adversary is manipulating its input to learn other parties inputs.

$\endgroup$
  • $\begingroup$ Just so you know, the malicious PSI protocol in eprint/2013/515 is buggy. See eprint.iacr.org/2016/665 and also my paper eprint.iacr.org/2016/746 which contains a fix. $\endgroup$ – Mikero Jan 21 '17 at 3:26
  • $\begingroup$ @Mikero thanks for that! I will give them a look! Do you also consider the full universe attack as described in that paper? (as an active attack) btw is there were the bug is? $\endgroup$ – DaWNFoRCe Jan 22 '17 at 11:04
  • $\begingroup$ Our security proof indirectly implies that an adversarial receiver cannot set all bloom filter bits to 1 for a full universe attack. The bug in DCW is that nothing forces the sender to use correct secret shares. $\endgroup$ – Mikero Jan 22 '17 at 17:13
5
$\begingroup$

In general, such attacks are "allowed" in the malicious model. This is due to the fact that secure computation guarantees that the process of computation reveals nothing. A secure protocol should behave like an ideal model where a trusted party computes the result. Now, in some cases, this is a problem. However, in practice, in many cases it is OK.

Consider the case of PSI: in practice, the length of the inputs is known to both parties. Thus, it may not be possible for one party to input the entire universe (which may also be huge). Having said this, this is possible if a protocol is used that depends on the entire universe (e.g., PSI by running secure computation via a circuit that computes over vectors of bits, so that the $i$th bit of a party's vector equals 1 if and only if it has the $i$th element of the universe in its input). Formally, the definition of the functionality should express the size of the input and therefore make this clear. However, in reality, this detail is often overlooked in papers.

In short, this is a real issue and if you want to use MPC you need to understand the ramification of "maliciously chosen inputs".

$\endgroup$
  • $\begingroup$ Thanks as always for your help, and for saving the day (once again). This is now clear to me for the MPC case. I have, however, a counter question with respect of the PSI part of your answer. In the case the adversary is not limited in the number of queries he is able to do, the size of the query might not be a problem right? Furthermore, on eprint.iacr.org/2013/515.pdf, they describe this behavior as "malicious" (this is the source of my confusion). In short, should the parties providing valid inputs, be assumed on a semi-honest setting and the opposite malicious? $\endgroup$ – DaWNFoRCe Jan 16 '17 at 22:39
  • $\begingroup$ I don't know about that paper. However, in the semi-honest model, the party is not allowed to change their prescribed input. So, changing inputs, adding input values and so on is considered malicious behavior. $\endgroup$ – Yehuda Lindell Jan 16 '17 at 22:41
  • $\begingroup$ Last question, in this case, should I interpret the full universe attack as a such ? That is, to input the full universe on my query is a manipulation of the prescribed input and hence malicious behavior? $\endgroup$ – DaWNFoRCe Jan 16 '17 at 22:55
  • $\begingroup$ Yes. (Of course, having said that, one should not that it's an easy malicious attack to carry out. So, in practice, you should assess what your real threat model is. Theoretically speaking, however, it is a malicious attack.) $\endgroup$ – Yehuda Lindell Jan 16 '17 at 23:03

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.