Return to Answer

Commonmark migration

Source Link

edited Jun 17, 2020 at 8:17

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:

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.
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$.

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

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:

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.
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$.

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

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:

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.
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$.

Source Link

created Jul 19, 2018 at 2:33

Mikero

14.5k
2
35
56

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

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:

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.
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$.