# US 2023/0053566 A1 · Privacy-preserving computing with third-party service

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

- Number: US 2023/0053566 A1
- Document ID: US20230053566A1
- Status: Published application
- Kind: A1
- Application number: 17/396,124
- Filed: 2021-08-06
- Published: 2023-02-23
- Earliest claimed: 2021-08-06
- Assignees: Amazon Technologies, Inc.
- Applicants: Amazon Technologies, Inc.
- Inventors: William Horne; Eric Crockett
- Web page: https://patentgrep.com/patent/US20230053566A1

## CPC

- G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries}
- H04L 9/008: {involving homomorphic encryption}
- H04L 9/3242: {involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC}
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Systems, devices, and methods are provided for secure multiparty computation (MPC) protocols. A first computing entity may send a first cryptographically protected data set to a server and a second computing entity may send a second cryptographically protected data set to the server. The server may lack access to plaintext versions of the data sets. The server may compare cryptographically protected data elements from the first and second data sets as part of a secure MPC protocol to determine certain information regarding the data sets, such as determining which data elements are included in both sets, and perform homomorphic computations according to a homomorphic encryption scheme. The server is accordingly able to determine an encrypted result.

## Claims

### Claim 1

A system, comprising:
one or more processors; and
memory storing executable instructions that, as a result of execution by the one or more processors, cause the system to:
obtain, from a first computing entity, a first cryptographically protected data set comprising a first column of cryptographically protected data elements generated using a keyed one-way function and based on a first cryptographic secret, wherein the first cryptographic secret is shared between the first computing entity and a second computing entity;
obtain, from the second computing entity, a second cryptographically protected data set comprising:
a second column of cryptographically protected data elements generated using the keyed one-way function and based on the first cryptographic secret; and
a third column of cryptographically protected data elements encrypted according to a homomorphic encryption scheme, wherein plaintext of the third column is inaccessible to the system;
perform a privacy-preserving comparison of the first cryptographically protected data set and the second cryptographically protected data set to identify a joined cryptographically protected data set comprising a subset of the third column;
compute an encrypted result of the subset of the third column according to the homomorphic encryption scheme; and
provide the encrypted result to the second computing entity, wherein the second computing entity has access to a second cryptographic key usable to decrypt the encrypted result.

### Claim 2 (depends on 1)

The system of claim 1, wherein the homomorphic encryption scheme is implemented according to an ElGamal crypto system.

### Claim 3 (depends on 1)

The system of claim 1, wherein the instructions include further instructions that, as a result of execution by the one or more processors, cause the system to provide, to the first computing entity, cardinality of the subset.

### Claim 4 (depends on 1)

The system of claim 1, wherein the instructions to perform the privacy-preserving comparison of the first cryptographically protected data set and the second cryptographically protected data set to identify the subset of the third column include instructions that, as a result of execution by the one or more processors, cause the system to:
compare a first cryptographically protected data element located at a first row of the first column with a second cryptographically protected data element located at a second row of the second column; and
include the second row of the third column in the subset.

### Claim 5

A computer-implemented method, comprising:
at a third computing entity:
obtaining, from a first computing entity, a first cryptographically protected data set comprising a first set generated based on cryptographic material shared between the first computing entity and a second computing entity;
obtaining, from the second computing entity, a second cryptographically protected data set comprising:
a second set generated based on the cryptographic material; and
a plurality of encrypted data elements generated according to a homomorphic encryption scheme that correspond to the second set;
performing a join, based on the first cryptographically protected data set and the second cryptographically protected data set, to identify a collection of one or more encrypted data elements;
performing, according to the homomorphic encryption scheme, one or more privacy-preserving computations using the collection of one or more encrypted data elements; and
providing an encrypted result of the one or more computations to the second computing entity.

### Claim 6 (depends on 5)

The method of claim 5, wherein performing the join, based on the first cryptographically protected data set and the second cryptographically protected data set comprises:
identifying a first cryptographically protected data element located at a first row of the first set;
identifying a second cryptographically protected data element located at a second row of the second set;
determining the first cryptographically protected data element matches the second cryptographically protected data element; and
adding an encrypted data element located at the second row of the plurality of encrypted data elements to the collection.

### Claim 7 (depends on 5)

The method of claim 5, wherein the one or more privacy-preserving computations comprise a set of homomorphic computations agreed upon by the first computing entity and the second computing entity.

### Claim 8 (depends on 5)

The method of claim 5, wherein the first set is generated further based on a Hash-based Message Authentication Code (HMAC) algorithm.

### Claim 9 (depends on 5)

The method of claim 5, wherein the homomorphic encryption scheme comprises a partial homomorphic encryption scheme.

### Claim 10 (depends on 5)

The method of claim 5, wherein the join is an inner join of the first data set and the second data set based on an equivalence relationship between the first set and the second set.

### Claim 11 (depends on 5)

The method of claim 5, further comprising:
determining a second result based on the collection of one or more encrypted data elements; and
providing the second result to the first computing entity.

### Claim 12 (depends on 5)

The method of claim 5, further comprising:
obtaining, from a third computing entity, a third cryptographically protected data set comprising a fourth column generated based on the cryptographic material, wherein the cryptographic material is further shared with the third computing entity; and
performing the join further based on the third cryptographically protected data set.

### Claim 13

A non-transitory computer-readable storage medium storing executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:
establish a first cryptographic secret with a second computer system;
obtain a first data set comprising a plurality of rows of data elements;
determine a cryptographically protected first data set by at least:
cryptographically protecting a first portion of the first data set using the first cryptographic secret; and
homomorphically encrypting a second portion of the first data set using a second cryptographic secret and according to a homomorphic encryption scheme;
shuffling the plurality of rows;
provide, to a third computer system and according to a multiparty computation (MPC) protocol, the cryptographically protected first data set to cause the third computer system to perform one or more privacy-preserving computations based on the first cryptographically protected data set and a second cryptographically protected data set generated by the second computer system, wherein:
the second cryptographically protected data set is also generated based on the first cryptographic secret; and
the third computer system lacks access to the first cryptographic secret;
obtain an encrypted result of the one or more privacy-preserving computations performed based on the first cryptographically protected data set and the second cryptographically protected data set; and
decrypt the encrypted result to obtain a plaintext result.

### Claim 14 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein the instructions to cryptographically protect the at least portion of the first data set using the cryptographic secret comprise instructions that, as a result of execution, cause the computer system to:
determine that the first portion of the data set is used to test set membership, according to the MPC protocol; and
cryptographically protect data elements of the first portion using a keyed one-way function and the cryptographic secret.

### Claim 15 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein the instructions, as a result of being executed by the one or more processors of the computer system, further cause the system to:
determine that the second portion of the first data set is used to perform at least one of addition or multiplication according to the MPC protocol; and
based on the determination that the second portion of the first data set is used to perform at least one of addition or multiplication, homomorphically encrypt the second portion of the first data set.

### Claim 16 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein the homomorphic encryption scheme implements homomorphic addition but not homomorphic multiplication, or homomorphic multiplication but not homomorphic addition.

### Claim 17 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein the instructions, as a result of being executed by the one or more processors of the computer system, further cause the system to:
obtain, from the third computer system, one or more cryptographically protected results;
determine a plaintext data element;
cryptographically protect the plaintext data element using the cryptographic secret to determine a cryptographically protected data element; and
determine the cryptographically protected data element matches a cryptographically protected result of the one or more cryptographically protected results, thereby indicating the plaintext data element is included in both the first data set and a second plaintext data set used to generate the second cryptographically protected data set.

### Claim 18 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein:
the second cryptographic secret is shared with the second computer system; and
the encrypted result is to be made available to the second computer system according to the MPC protocol.

### Claim 19 (depends on 18)

The non-transitory computer-readable storage medium of claim 18, wherein the second cryptographic secret is a symmetric key and the third computer system lacks access to the second cryptographic secret.

### Claim 20 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein the instructions, as a result of being executed by the one or more processors of the computer system, further cause the system to obtain, from the third computer system, a plaintext result of the privacy-preserving computations.

### Claim 21 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein the homomorphic encryption scheme implements homomorphic addition using an ElGamal crypto system.
