1
$\begingroup$

In the ideal world, $A$ sends several inputs $x_1,...,x_\lambda$ to the functionality and $B$ sends input $y$. Functionality sends $f(x_1,y),...,f(x_\lambda,y)$ to $A$ and nothing to $B$.

Suppose that we have a protocol which is secure against semi-honest adversaries to realize this functionality.

In this protocol, $A$ sends encrypted values of $x_i$s to $B$. $B$ computes the encrypted result of each $f(x_i,y)$ and sends them back to $A$. $A$ decrypts these values to know each $f(x_i,y)$.

  1. Is it possible for $A$ to choose $x_i$s in a way that this protocol is also secure against malicious $B$? For example, $A$ can choose some $x_i$s equal or with some specific relation in such a way that any deviation from the protocol is detected?

What I am intended to say is something like cut-and-choose but for outputs instead of inputs.

  1. More generally, is it necessary to force the malicious party to act honestly at each intermediate step or it is sufficient to force him to output correctly?
Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Detection of malicious behavior can happen anywhere. However, it is not true that you can run semi-honest protocols and then check later. This is because such protocols can reveal the honest party's input when interacting with a malicious adversary. In such as case, even if you detect the cheating, security is not achieved. Thus, you need to make sure that no cheating happens that can break privacy; for correctness, it suffices to detect at the end. (There is a model called covert for which privacy can be breached as long as detection happens with good probability.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ In the case of one-sided simulation, for the party that outputs nothing we can guarantee that he cannot learns anything from the other parties input via indistinguishability of inputs. In this case, however, we cannot be sure about correctness. Is it worse to add something like in the question (several inputs to get several output, or something similar) to the proof in order to guarantee the correctness property? $\endgroup$
    – MH Samadani
    Commented Nov 15, 2015 at 7:11
  • 1
    $\begingroup$ This is an interesting idea. You want to extend the one-sided simulation definition so that when the party not getting output is corrupted, there is still correctness, and you want to do this by allowing a funny type of simulation with many inputs. It's hard for me to judge how good this is, because it depends on the exact definition. But, it is an interesting idea. $\endgroup$
    – Yehuda Lindell
    Commented Nov 25, 2015 at 5:38
2
$\begingroup$

More generally, is it necessary to force the malicious party to act honestly is each intermediate step or it is sufficient to force him to output correctly?

Detection of malicious behavior can occur at the end. It does not have to happen at each intermediate step.

Is it possible for A to choose $x_i$s in a way that this protocol is also secure against malicious B? For example, A can choose some $x_i$s equal or with some specific relation in such a way that any deviation from the protocol is detected?

What if the adversary always cheats in the same way? It may be possible to do what you are saying. I'm not aware of any published results like this example, however. But I also doubt there is a proof saying that this general idea is impossible. Thus, to really answer, we'd need a more concrete proposal and have to either prove security or give a counter example.

Improve this answer
$\endgroup$
2
  • $\begingroup$ But actually in practice we use ZK proofs for every action of adversarial party. $\endgroup$
    – MH Samadani
    Commented Nov 9, 2015 at 14:10
  • 2
    $\begingroup$ @MHSamadani It isn't true that we use ZK proofs for every action at all. More efficient protocols involve a series of checks that are based on different techniques, and overall prevent cheating. Using ZK proofs for every action - even if they are efficient ZK proofs - is typically not practical. $\endgroup$
    – Yehuda Lindell
    Commented Nov 9, 2015 at 14:14

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.