How to ask for an Identity confirmation without revealing

Question

Let us say Alice has a list of public keys of her contacts. Bob wants to contact Ted and Bob has public key of Ted.

Now, Is it possible to confirm that Alice has the same public key, without revealing that Bob wants to contact Ted? If we ask directly Alice, there will loss in privacy for both the users. Is there any relevant concept in Cryptography that can help me here ?

Answer 1

There are two ways that I see.

First, Oblivious Transfer allows a requester to retrieve relevant information (and only relevant information) from the sender without the requester revealing which piece of information they're after. This would allow the Bob to obtain the key that Alice has for Ted, without Alice knowing that Bob is interested in Ted's key. Depending on the scenario, this could be a vulnerability in the case that Bob has the wrong key -- this protocol would allow him to obtain the correct one from Alice.

Second, Secure Computation allows Bob to obtain the value of $f(x,y)$ where $x$ is only known to Bob and $y$ only known to Alice (and $f$ is mutually known). Let's say that Bob knows that Ted's key is stored at position $i$ of Alice's contact list. Then we could have $y=$Alice's contacts, $x=(i,t)$ where $t$ is they key Bob has for Ted. Then $f(x,y)=[[y[i] == t]]$.

Answer 2

Sounds like you want either private set matching, or private information retrieval (to retrieve the key). Try looking those up.

Answer 3

It’s fairly easy, you just need to do a private set membership query on Alice’s contacts.

Private set membership can be implemented in multiple ways. One I had found to be fairly simple and straightforward was once cited by @Mikero as answer to one of my questions on this SE.

It makes use of an Oblivious PRF by means of an Oblivious Transfer.

Here’s the presentation on the paper, and you can also find the paper via this link: https://youtu.be/i0kGwz_52Wg