2
$\begingroup$

I think this problem is similar to private set intersection, yet distinct in a way where:

Alice has an extensive Mapping of say id to name

id1 -> John Doe

id2 -> Jane Doe

id3 -> Edgar Poe

Bob has a short-list of id's say

id1 (Alice knows the name of this person)

id3 (Alice knows the name of this person)

id4 (Alice doesn't know the name of this person)

Neither Bob, nor Alice wants to share all their data assets with each other. However Alice has agreed to share the names of the people for whom Bob has knows the id. Bob on the other hand, doesn't want Alice to know which id's he has.

Are there any known, secure protocols which only involve two parties? (no-trusted 3rd parties etc)

$\endgroup$

1 Answer 1

3
$\begingroup$

Many (most?) leading PSI protocols can be easily adapted to provide this functionality. It is sometimes called "PSI with associated data" or "PSI with data transfer". For example, you can see this variant of PSI described explicitly in:

Emiliano De Cristofaro and Gene Tsudik. Practical private set intersection protocols with linear complexity. Financial Cryptography 2010.

Even many protocols which don't mention "associated data" explicitly can be easily modified to provide it. I know for sure that the following papers (which are the fastest 2-party semi-honest PSI) will support it:

Benny Pinkas, Thomas Schneider, Gil Segev, Michael Zohner: Phasing: Private Set Intersection using Permutation-based Hashing. Usenix 2015.

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

These protocols use an "oblivious PRF" paradigm for PSI, which works roughly like this:

  1. Parties perform an Oblivious PRF where Alice learns (description of) a random function $F$ and Bob learns $F(y)$ for every $y$ in his set.

  2. Alice can compute and send $F(x)$ for every $x$ in his set. Now Bob can compare against his set of $F$-values and identify the intersection. For values $x$ that Alice has but Bob doesn't have, the corresponding $F(x)$ value looks random to Bob, so leaks no information about that $x$.

There is a fair amount of other algorithmic/combinatorial stuff in these protocols, but eventually at some level the protocol is doing what I described above.

To add associated data to this protocol outline, you can just use the $F(x)$ values as keys to encrypt the associated data. Something like this:

  • For every $y$, Bob has $F(y)$ and (if it's not long enough) expands it with a PRG to get two values $tag_y$ and $k_y$.

  • For every $x$, Alice similarly expands $F(x)$ into $tag_x$ and $k_x$. She sends $(tag_x, \mathsf{Enc}(k_x, data[x]))$, where $data[x]$ is the record/data associated with key $x$.

  • Bob can look for tuples of the form $(\tau, c)$ where $\tau$ is a tag that he recognizes as $tag_y$. He can then decrypt $c$ with the corresponding key $k_y$ to obtain the data associated with $y$.

$\endgroup$
1
  • $\begingroup$ I've been researching possible implementations of OPRF and I've found a rather straight forward implementation of EC-OPRF in JavaScript: github.com/multiparty/oprf I'm totally oblivious to the idea, from what I understood it has essentially 2 functions ran by Bob. masking and unmasking. Alice salts the masked input (with a key). However Alice can also do the calculation directly as well. Do you think I can directly implement this protocol and use as is? $\endgroup$
    – zetaprime
    Commented Jul 22, 2018 at 2:30

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.