# US 8,572,405 B2 · Collusion-resistant outsourcing of private set intersection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,572,405 B2
- Document ID: US8572405B2
- Status: Granted
- Kind: B2
- Application number: 13/421,103
- Filed: 2012-03-15
- Published: 2013-09-19
- Granted: 2013-10-29
- Earliest claimed: 2012-03-15
- Assignees: Sap SE
- Applicants: Florian Kerschbaum
- Inventors: Florian Kerschbaum
- Web page: https://patentgrep.com/patent/US8572405B2

## CPC

- H04L 9/00: {Cryptographic mechanisms or cryptographic} arrangements for secret or secure communications; Network security protocols
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Implementations of the present disclosure include methods, systems, and computer-readable storage mediums for receiving an encrypted first data set from a first entity, storing the encrypted first data set in computer-readable memory, receiving an encrypted second data set from a second entity, storing the encrypted second data set in computer-readable memory, receiving public encryption information associated with the encrypted first data set and the encrypted second data set, storing the public encryption information in computer-readable memory, and processing, using the one or more processors, the encrypted first data set and the encrypted second data set to provide the set intersection, wherein an advantage of a first adversary in guessing data elements of the encrypted first data set is negligible in a security parameter.

## Claims

### Claim 1

A computer-implemented method for determining a set intersection using a third party, the method being executed using one or more processors and comprising:
receiving an encrypted first data set from a first entity;
storing the encrypted first data set in computer-readable memory;
receiving an encrypted second data set from a second entity;
storing the encrypted second data set in computer-readable memory;
receiving public encryption information associated with the encrypted first data set and the encrypted second data set;
storing the public encryption information in computer-readable memory; and
processing, using the one or more processors, the encrypted first data set and the encrypted second data set to provide the set intersection, wherein:
Adv
A
<
1
poly
⁡
(
λ
)
where:
γ is a security parameter;
poly( )refers to any positive polynomial; and
AdvA is provided as an advantage of a first adversary in guessing data elements of the encrypted first data set and is determined based on a probability of the first adversary guessing the data elements and a second adversary guessing the data elements, the first adversary comprising the third party and the second entity, and the second adversary having access to the encrypted first data set and the public encryption information.

### Claim 2 (depends on 1)

The method of claim 1, wherein AdvA is calculated as:
AdvA=Pr[A(S)=x−A′(pk, c)=x]
where:
A is the first adversary;
S represents messages of the first entity received by the third part;
A′is the second adversary;
pk is the public encryption information;
c is an encrypted data element included in the encrypted first data set;
x is a correct guess of a value of an unencrypted data element associated with the encrypted data element; and
Pr [ ] is a mathematical notation indicating a probability calculation.

### Claim 3 (depends on 1)

The method of claim 1, wherein a first data set is encrypted using a key to provide the encrypted first data set and a second data set is encrypted using the key to provide the encrypted second data set.

### Claim 4 (depends on 3)

The method of claim 3, wherein the first data set and the second data set are each encrypted based on a keyed hash function using the key.

### Claim 5 (depends on 3)

The method of claim 3, wherein the processing, using the one or more processors, the encrypted first data set and the encrypted second data set to provide the set intersection comprises:
calculating a cross-product of the encrypted first data set and the encrypted second data set to provide a plurality of bit strings, each bit string associated with an encrypted data element pair comprising an encrypted data element of the encrypted first data set and an encrypted data element of the encrypted second data set; and
for one or more encrypted data element pairs:
determining that first l bits of an associated bit string are each equal to a first value and, in response, adding next m bits of the associated bit string as a data element of the set intersection.

### Claim 6 (depends on 5)

The method of claim 5, wherein the first value is zero.

### Claim 7 (depends on 5)

The method of claim 5, wherein the m bits of the associated bit string defines an unencrypted data element that is included in each of the first data set and the second data set.

### Claim 8 (depends on 1)

The method of claim 1, wherein the encrypted first data set is encrypted based on a first exponent (d1) and the encrypted second data set is encrypted based on a second exponent (d2), the first entity receiving the first exponent (d1) and a third exponent (f) from a trusted source, the second entity receiving the second exponent (d2) and the third exponent (f) from the trusted source, and the third party receiving a fourth exponent (e) from the trusted source.

### Claim 9 (depends on 8)

The method of claim 8, wherein:
(d1+d2)e=f (mod φ(n))
where:
φ( )denotes a totient function; and
n is a modulus that is selected by the first entity and the second entity, a factorization of n being unknown to either the first entity and the second entity.

### Claim 10 (depends on 9)

The method of claim 9, wherein the modulus is a RSA encryption modulus.

### Claim 11 (depends on 8)

The method of claim 8, wherein the encrypted first data set is encrypted based on applying the first exponent to each data element of a first data set.

### Claim 12 (depends on 8)

The method of claim 8, further comprising:
defining a set of encrypted data elements, wherein each encrypted data element in the set of encrypted data elements is defined based on a product of an encrypted data element of the encrypted first data set and an encrypted data element of the encrypted second data set, the product being raised to the fourth exponent; and
storing the set of encrypted data elements in computer-readable memory.

### Claim 13 (depends on 12)

The method of claim 12, further comprising:
receiving, from the first entity, a set intersection request; and
in response to receiving the set intersection request, transmitting the set of encrypted data elements to the first entity.

### Claim 14

A non-transitory computer-readable storage medium coupled to one or more processors and having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations for determining a set intersection using a third party, the operations comprising:
receiving an encrypted first data set from a first entity;
storing the encrypted first data set;
receiving an encrypted second data set from a second entity;
storing the encrypted second data set;
receiving public encryption information associated with the encrypted first data set and the encrypted second data set;
storing the public encryption information; and
processing, using the one or more processors, the encrypted first data set and the encrypted second data set to provide the set intersection, wherein:
Adv
A
<
1
poly
⁡
(
λ
)
where:
γ is a security parameter;
poly( )refers to any positive polynomial; and
AdvA is provided as an advantage of a first adversary in guessing data elements of the encrypted first data set and is determined based on a probability of the first adversary guessing the data elements and a second adversary guessing the data elements, the first adversary comprising the third party and the second entity, and the second adversary having access to the encrypted first data set and the public encryption information.

### Claim 15

A system, comprising:
a computing device; and
a computer-readable storage device coupled to the computing device and having instructions stored thereon which, when executed by the computing device, cause the computing device to perform operations for determining a set intersection using a third party, the operations comprising:
storing the encrypted first data set;
receiving an encrypted second data set from a second entity;
storing the encrypted second data set;
receiving public encryption information associated with the encrypted first data set and the encrypted second data set;
storing the public encryption information; and
processing, using the one or more processors, the encrypted first data set and the encrypted second data set to provide the set intersection, wherein:
Adv
A
<
1
poly
⁡
(
λ
)
where:
γ is a security parameter;
poly( )refers to any positive polynomial; and
AdvA is provided as an advantage of a first adversary in guessing data elements of the encrypted first data set and is determined based on a probability of the first adversary guessing the data elements and a second adversary guessing the data elements, the first adversary comprising the third party and the second entity, and the second adversary having access to the encrypted first data set and the public encryption information.

### Claim 16 (depends on 14)

The computer-readable storage medium of claim 14, wherein a first data set is encrypted using a key to provide the encrypted first data set and a second data set is encrypted using the key to provide the encrypted second data set.

### Claim 17 (depends on 16)

The computer-readable storage medium of claim 16, wherein the first data set and the second data set are each encrypted based on a keyed hash function using the key.

### Claim 18 (depends on 14)

The computer-readable storage medium of claim 14, wherein the encrypted first data set is encrypted based on a first exponent (d1) and the encrypted second data set is encrypted based on a second exponent (d2), the first entity receiving the first exponent (d1) and a third exponent (f) from a trusted source, the second entity receiving the second exponent (d2) and the third exponent (f) from the trusted source, and the third party receiving a fourth exponent (e) from the trusted source.

### Claim 19 (depends on 15)

The system of claim 15, wherein a first data set is encrypted using a key to provide the encrypted first data set and a second data set is encrypted using the key to provide the encrypted second data set.

### Claim 20 (depends on 19)

The system of claim 19, wherein the first data set and the second data set are each encrypted based on a keyed hash function using the key.