3
$\begingroup$

I think this should be a simple question and I might be missing something fairly fundamental, but I haven't been able to find the answer.

Basically, suppose there are parties $A$ and $B$. Party $A$ gets a secret input $s$. Party $B$ has no input. They wish to securely compute the function $f(s) = (\bot, \bot)$ so nobody learns any information.

Suppose the protocol they use goes as follows: $A$ sends $s$ to $B$ in the clear. Clearly, this 'should not' be considered secure, as $B$ wasn't supposed to learn anything but she learned $s$. However, by the simulator-based definition of security, I don't understand why we can't efficiently simulate $B$'s view.

I.e. if we generate a simulated transcript just by picking a random $s$ and sending it to $B$, how can he distinguish between that and a real transcript?

Improve this question
$\endgroup$
4
  • $\begingroup$ Semi-honest or malicious model? $\endgroup$
    – fkraiem
    Dec 9, 2019 at 14:59
  • $\begingroup$ I'm on mobile right now and don't want to type a lot now. In short: Multiple executions would be distinguishable from a simulator choosing s uniform if the secret s is not chosen uniform by party A (e.g. consider A inputting s twice multiple times in every execution of the protocol) $\endgroup$
    – Martin Kromm
    Dec 9, 2019 at 15:12
  • 1
    $\begingroup$ Probably essentially a duplicate of crypto.stackexchange.com/questions/68908/… $\endgroup$
    – fkraiem
    Dec 9, 2019 at 15:20
  • $\begingroup$ @fkraiem semi-honest (a.k.a. honest-but-curious) $\endgroup$
    – Andy Dienes
    Dec 9, 2019 at 15:57

2 Answers 2

Reset to default
5
$\begingroup$

As in the linked question, what you are missing is that the simulated view for a given input pair must be indistinguishable from the simulated view for the same input pair.

So if $A$'s input $s$ is $0$, then the real view of $B$ will be $0$ with probability $1$. On the other hand, if your simulator just chooses a uniform bit, the simulated view of $B$ will be $0$ with probability $1/2$. That's distinguishable, so your simulator doesn't work. (Same if $s=1$ of course.)

A slightly more involved argument shows that any simulator will have the same issue, so there is no suitable simulator, and the protocol is not secure.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the answer. Intuitively, this makes sense. However, it's not clear to me why we should make any assumptions about $s$ (what if it is randomly generated?). I.e. what if we know $s$ arises from some $\mathsf{KeyGen}$ algorithm. Can't we simulate that? $\endgroup$
    – Andy Dienes
    Dec 9, 2019 at 16:19
  • 2
    $\begingroup$ The definition of security says we must consider separately every possible input, no matter how it was generated, and the simulator must work correctly on every one. $\endgroup$
    – fkraiem
    Dec 9, 2019 at 16:29
  • $\begingroup$ oh! I think the clause in the definition "for all inputs" had just not been clicking. It now makes sense to me why no simulator can always work. I.e. suppose $s \sim \{0,1\}$. Any simulator must pick either 0 or 1 with non-negligible frequency. Then it cannot securely simulate the view on the input of the 'other' bit. $\endgroup$
    – Andy Dienes
    Dec 9, 2019 at 16:33
3
$\begingroup$

The short answer is: the algorithm that is trying to distinguish real from ideal interaction already knows the "correct" inputs. So it can easily distinguish in this case.

More precisely, let's take the security definition from Hazay-Lindell (p21):

$$ \{ S_2(1^n, y, f(x,y) \}_{x,y,n} \overset{c}\equiv \{ \textsf{view}_2^\pi(x,y,n) \}_{x,y,n} $$

The subscripts denote an ensemble of distributions. For each value of $x,y,n$, the two corresponding distributions must be indistinguishable. This implies that the distinguisher is allowed to depend on $x,y,n$.

In this example, $x=s$ and $y=\bot$ and $f(x,y)=\bot$. So $S_2$, who gets literally no information about $s$, must generate a view that is indistinguishable from the real view. If the real view contains the "correct" $s$ (which you can think of as being hard-coded into the distinguisher too) then the distributions are trivially distinguishable.

Improve this answer
$\endgroup$
5
  • $\begingroup$ If you allow the distinguisher to depend on $x,y,n$ then it makes more sense to me how this scheme is insecure. Although, this seems to slightly fly in the face of intuition: the distinguisher is no longer 'one of the curious parties trying to tell a simulated view from a real view' (because the curious party cannot depend on $x$), rather the distinguisher is some external algorithm depending on all the inputs trying to tell the simulated view of the curious party from her real view. $\endgroup$
    – Andy Dienes
    Dec 9, 2019 at 16:17
  • $\begingroup$ The distinguisher does not depend on $x,y,n$ I believe. (See the definition of computational indistinguishability on p. 19.) $\endgroup$
    – fkraiem
    Dec 9, 2019 at 16:23
  • $\begingroup$ In that case, I disagree with the definition of Hazay-Lindell ;) But setting aside that definition: in the UC definition it is the environment which both chooses the inputs of the honest parties, and also tries to distinguish real from ideal. I remain adament that a coherent security definition must allow the distinguisher to know the inputs of honest parties. I can see why it might initially fly in the face of your intuition, but it is quite analogous to security of encryption: In CPA security, the attacker already knows (chooses) plaintexts and still can't distinguish ciphertexts. $\endgroup$
    – Mikero
    Dec 9, 2019 at 16:57
  • $\begingroup$ In any case, this doesn't change the answer to this question; if a distinguisher can distinguish real vs. simulated views even when not given the parties' inputs, certainly it can do so with them as well. $\endgroup$
    – fkraiem
    Dec 9, 2019 at 18:48
  • 1
    $\begingroup$ In fact it seems that if you take the definition from H-L and modify it so that the distinguisher is allowed to depend on the parties' inputs, the resulting definition is equivalent to the original one, due to the non-uniformity of the distinguisher. Namely, if a protocol is not secure in the new definition, there is an input pair on which the simulator fails (i.e., the distinguisher succeeds), and that input pair can be given as advice to the distinguisher in the original definition. $\endgroup$
    – fkraiem
    Dec 9, 2019 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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