Socialist Millionaires variant, where only one party learns $x=y$?

Question

In the Socialist Millionaires protocol, Alice selcts some $x$ and Bob selects some $y$, and both parties learn whether or not $x=y$ without learning the other party's selected value. However, on a successful match, both parties do learn the other person's value -- it's the same as their own value. Does there exist a variant protocol (or way of cheating the existing protocol) wherein only one party learns $x=y$ and the other party learns nothing?

My particular case goes something like this:

• Bob has a small list of people he has invited to his birthday party.
• Bob is happy to let people query his entire list, item by item, via a Socialist Millionaires exchange to see if a particular person is included in the list. However, he does not want to give out the entire list wholesale.
• Alice has a secret crush on Charlie and wants to learn if Charlie is invited to the party. She could learn the answer by engaging Bob in a Socialist Millionaires exchange for every item in Bob's list.
• However, she does not want Bob to learn that she is interested in Charlie's invitation. If Charlie is on Bob's list, Bob will see that he and Alice participated in a matching exchange for his entry for Charlie.

Can Alice learn the equality of "Charlie" against every item on Bob's list, without Bob learning whether any particular item on the list was a match?

---

To put it another way, I think that this could be done with fully-homomorphic encryption, e.g.:

• Bob encrypts each item in his list with Alice's public key
• Alice sends her request for "Charlie" also encrypted with her public key
• Bob performs a homomorphic equality comparison of each encrypted list item against Alice's encrypted query (that is, Bob performs a $map$ of the encrypted list into a list of encrypted booleans, based on the homomorphic equality comparison of each item)
• Bob sends back a list of homomorphically encrypted booleans describing the matching-state of each comparison
• Alice decrypts Bob's reply with her private key

This case satisfies my requirement (I think?) that Bob learns nothing, because he can decrpyt neither Alice's query nor the results of his own homomorphic equality comparisons.

Is there a way to get a similar guarantee using a zero-knowledge proof exchange?

Answer 1

A protocol consists of parties taking turns sending messages. Therefore one party will naturally learn the output before the other (only very few exceptions exist to this rule). This means that in almost every protocol you find (especially in the semi-honest setting) you will see that either (1) the last protocol message literally is nothing more than the party-who-learned-output revealing the output to its counterpart (so you can exclude this message) or (2) the protocol is already described so that only one party gets output. In things like Wikipedia articles, it is often just simpler to describe MPC protocols as "both parties get the output", but under the hood there is generally one-sided output.

(In the Wikipedia article you reference, the protocol is written in a way that obscures the interaction pattern. The last communication between parties is in step 7 "$\langle Q_a Q_b^{-1} | \alpha,\beta\rangle$". But this step is an abstraction of Diffie-Hellman which consists of a message from each party. Just have one party omit this message and he/she will be the only one capable of learning the output.)

Protocols for private set intersection (PSI -- the generalization of socialist millionaires) are no exception. In our paper:

Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu: Efficient Batched Oblivious PRF with Applications to Private Set Intersection. CCS 2016.

(and every other PSI paper I know of) we describe the protocol so that only one party gets output.

The building block of this protocol is something called a "private membership test" where a sender has a set $S$ of items, a receiver has an item $v$, and only the receiver learns whether $v \in S$. This sounds like exactly what you're looking for.

This private membership test building block goes back to this work (and perhaps earlier):

Benny Pinkas, Thomas Schneider, Michael Zohner: Faster Private Set Intersection based on OT Extension. Usenix 2014.

Both of these papers are optimized to provide many instances of the private membership test building block primitive, since that is what is required for PSI. If you truly want just a single instance of private membership test, then there is probably nothing simpler than the classic Diffie-Hellman based PSI (homomorphic encryption is overkill if you just need semi-honest security). I describe it below, specialized to the case where Alice has just one item.

1. Alice (who has a single item $v$) picks random exponent $\alpha$ and sends $H(v)^\alpha$. Here $H$ is a random oracle.

2. Bob (who has a set of items $S$) picks random exponent $\beta$ and sends $(H(v)^\alpha)^\beta$ as well as $H(s)^\beta$ for every $s \in S$.

3. Alice can compute $(H(s)^\beta)^\alpha$ and check whether any of these values are equal to $(H(v)^\alpha)^\beta$. This will happen if and only if $v \in S$ (barring a negligibly unlikely collision in $H$).

Answer 2

The problem seems to be of private information retrieval in which one party holds a private database. Another party, who wants to learn a specific table entry or index value, performs a PIR protocol and learns that specific value without learning other content. At the same time, database owner doesn't knows the specific query index.

Have a lookon standard definition here: https://en.m.wikipedia.org/wiki/Private_information_retrieval