Relaxing Semi-Honest Security in Multiparty Computation

Question

I am currently reading Lindell's tutorial on simulation-based proofs and I am trying to understand the reasoning why the security notions are they way the are.

In simple words, in the case of semi-honest adversaries, we require that there exists one simulator for each party that can simulate the party's view based on its input and output. This simulator should produce a indistinguishable view no matter what the actual inputs (also of the other parties) to the protocol are. If we have constructed some protocol, we prove its security in the presence of semi-honest adversaries, by following, roughly, two steps.

1. Define an explicit simulator for each party that outputs, based on the party's input and output, a view that is indistinguishable from a view of that party from a real protocol run.

2. Assume towards contradiction that the real and simulated views are not indistinguishable and construct an adversary that breaks some underlying building block, e.g. an encryption scheme, commitments, or another protocol.

Hence, as far as I understand, this indistinguishability means that no (non-uniform) distinguisher, even knowing all inputs of all parties, given a real or a simulated view for one party, can tell whether the view was simulated or not.

Assuming my understanding of this is correct, my question is, whether a weaker version of this notion would also make sense, whether it already exists, or whether it would just be equivalent to the existing notion in some way.

Imagine some, very abstract, protocol between $P_1$ and $P_2$, where each of them has its own secret key and they use semi-honest 2PC to compute some shared key based on their own keys. Assume I have a protocol for this functionality and simulators for both parties that work for all inputs, apart from a negligible fraction of "bad" input keys. Intuitively, such a protocol should be a secure protocol in the presence of semi-honest adversaries (I think), but according to my understanding of the definition this would actually not be the case, since there does exist a distinguisher for some negligible fraction of inputs. Here, it seems that requirement for not having a distinguisher for all inputs is too strong.

Does my intuition make sense or is it flawed? Is there such a relaxed notion?

Answer 1

I'm not sure that the issue here is uniform versus non-uniform, but I'll address this first. It is possible to provide a uniform definition. In order to see what it would look like, I recommend reading Oded Goldreich's uniform treatment of zero knowledge http://www.wisdom.weizmann.ac.il/~oded/PS/uniform.ps.

In any case, your question is more about quantifying over all possible inputs, versus over a specific distribution. (Note that in Oded's uniform treatment, the quantification is over all poly-time samplable distributions. Here, you wish to guarantee security for a specific distribution only.) It is possible to define such a notion and it does make sense. The only question is if it buys you something. I have used such a notion once, in order to construct a secure password authentication protocol; see the definition in http://u.cs.biu.ac.il/~lindell/PAPERS/session-key.ps (Section 2.3.2). In this definition, the password is chosen randomly from a dictionary as part of the ideal and real models. You could do the same thing and choose a random key.