# US 2021/0344489 A1 · Communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer

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

- Number: US 2021/0344489 A1
- Document ID: US20210344489A1
- Status: Published application
- Kind: A1
- Application number: 16/848,963
- Filed: 2020-04-15
- Published: 2021-11-04
- Earliest claimed: 2020-04-15
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Kilian Becher; Axel Schroepfer; Mirko Schaefer
- Web page: https://patentgrep.com/patent/US20210344489A1

## CPC

- H04L 9/008: {involving homomorphic encryption}
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 9/0819: {Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) (network architectures or network communication protocols for key distribution in a packet data network H04L63/062)}
- H04L 9/0825: {using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates}
- H04L 9/085: {Secret sharing or secret splitting, e.g. threshold schemes}
- H04L 9/0869: {involving random numbers or seeds}
- H04L 63/0442: {wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption (cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30)}
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- H04L 2209/50: Oblivious transfer
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The present disclosure involves systems, software, and computer implemented methods for a communication-efficient secret shuffle protocol for encrypted data based on homomorphic encryption and oblivious transfer. A service provider and multiple clients participate in a secret shuffle protocol of randomly shuffling encrypted client-specific secret input values. The protocol includes generation and exchange of random numbers, random permutations and different blinding values, including use of an oblivious transfer mechanism. A last protocol step includes using homomorphism, for each client, to perform computations on intermediate encrypted data to homomorphically remove a first blinding value and a second blinding value, to generate a client-specific rerandomized encrypted secret input value. As a result, the client-specific rerandomized encrypted secret input values are generated in an order that is unmapped to an order of receipt, at the service provider, of the encrypted secret input values.

## Claims

### Claim 1

A system for executing a secret shuffle protocol, the system comprising a plurality of clients and a service provider, wherein each client comprises at least one computing device and the service provider comprises at least one server computing device, and wherein:
each client is configured to:
identify a client-specific secret input value;
encrypt the client-specific secret input value; and
send the encrypted client-specific secret input value to the service provider; and
the service provider is configured to receive, from each client, the encrypted client-specific secret input value; and
each client is further configured to:
generate a client-specific random value;
send the client-specific random value to each of the other clients; and
receive, from each of the other clients, the client-specific random values of each of the other clients; and
the service provider is further configured to select a service provider random value and send the service provider random value to each of the clients; and
each client is further configured to receive the service provider random value from the service provider; and
the service provider is further configured to randomly permute the encrypted client-specific secret input values using a random permutation; and
each client is further configured to:
generate a client-specific list of hashed values using each of the client-specific random values generated by each of the clients and the service provider random value;
determine, using the client-specific list of hashed values, a client-specific random index that is different from client-specific random indices determined by the other clients;
receive, from the service provider, a randomly-determined encrypted blinded input selected based on the client-specific random index; and
the service provider is further configured to:
provide a randomly-determined encrypted blinded input to each client, wherein each randomly-determined encrypted blinded input is selected based on the client-specific random index of the client; and
provide, to each client, a client-specific encrypted first blinding value, wherein the client-specific encrypted first blinding value is an encryption of a client-specific first blinding value included in the randomly-determined encrypted blinded input received by the client; and
each client is further configured to:
receive, from the service provider, the client-specific first encrypted blinding value;
rerandomize the randomly-determined encrypted blinded input to prevent the service provider from learning the client-specific random index of the client;
send, to the service provider, a client-specific rerandomized encrypted blinded input;
generate, using a client-specific second blinding value, a client-specific encrypted and blinded first blinding value; and
send, to the service provider, a client-specific encrypted and blinded first blinding value;
encrypt the client-specific second blinding value; and
send, to the service provider, a client-specific encrypted second blinding value; and
the service provider is further configured to:
receive, from each client, the client-specific rerandomized encrypted blinded input, the client-specific encrypted and blinded first blinding value, and the client-specific encrypted second blinding value; and
decrypt each client-specific encrypted and blinded first blinding value to generate a first client-specific intermediate plaintext for each client;
multiply each first client-specific intermediate plaintext by negative one to generate a second client-specific intermediate plaintext for each client;
encrypt each second client-specific intermediate plaintext to generate an intermediate ciphertext for each client;
multiply, for each client, the intermediate ciphertext by the client-specific rerandomized encrypted blinded input and the client-specific encrypted second blinding value, to homomorphically remove the first blinding value and the second blinding value, to generate a client-specific rerandomized encrypted secret input value, wherein the client-specific rerandomized encrypted secret input values are generated in an order that is unmapped to an order of receipt, at the service provider, of the encrypted secret input values.

### Claim 2 (depends on 1)

The system of claim 1, wherein the service provider comprises a cloud-based service executed on one or more servers.

### Claim 3 (depends on 1)

The system of claim 1, wherein each client creates the client-specific list of hashed values by:
concatenating each of the client-specific random values generated by each of the clients with the service provider random value; and
creating a hash value of each concatenation.

### Claim 4 (depends on 3)

The system of claim 3, wherein each client is further configured to, before generating the client-specific list of hashed values:
determine whether each of the client-specific random values generated by the clients is unique; and
in response to determining that at least two of the client-specific random values generated by the clients are not unique, abort the secret shuffling protocol.

### Claim 5 (depends on 1)

The system of claim 1, wherein each client determines the client-specific random index by:
sorting the list of client-specific hashed values to create a sorted list of hashed values;
determining, as the client-specific random index for the client, a position in the sorted list of hashed values that corresponds to the client-specific random value generated by the client.

### Claim 6 (depends on 1)

The system of claim 1, wherein the randomly-determined encrypted blinded input received by a respective client is provided to the client using a first oblivious transfer.

### Claim 7 (depends on 6)

The system of claim 6, wherein the first oblivious transfer of a randomly-determined encrypted blinded input to a respective client comprises the client receiving only one encrypted blinded input from among a set of encrypted blinded inputs having a count equal to the number of clients.

### Claim 8 (depends on 7)

The system of claim 7, wherein the service provider does not learn, from the first oblivious transfer of the randomly-determined encrypted blinded input to a respective client, which encrypted blinded input of the set of encrypted blinded inputs is received by the client from the first oblivious transfer.

### Claim 9 (depends on 1)

The system of claim 1, wherein the client-specific encrypted first blinding value is received by a respective client using a second oblivious transfer.

### Claim 10 (depends on 1)

The system of claim 1, wherein each client encrypts the client-specific secret input value using a first cryptosystem.

### Claim 11 (depends on 9)

The system of claim 9, wherein the service provider selects, as the service provider random value, a first random value from a plaintext space of the first cryptosystem.

### Claim 12

A computer-implemented method for executing a secret shuffle protocol, comprising:
receiving, from each of multiple clients, an encrypted client-specific secret input value;
selecting a service provider random value;
sending the service provider random value to each of the clients;
randomly permuting the received encrypted client-specific secret input values using a random permutation;
providing, to each client, a randomly-determined encrypted blinded input from the received encrypted client-specific secret input values, wherein each randomly-determined encrypted blinded input is selected for a client based on a random index of the client;
providing, to each client, a client-specific encrypted first blinding value, wherein the client-specific encrypted first blinding value is an encryption of a client-specific first blinding value included in the randomly-determined encrypted blinded input received by the client;
receiving, from each client, a client-specific rerandomized encrypted blinded input, wherein the client-specific rerandomized encrypted blinded input is a rerandomization of the randomly-determined encrypted blinded input provided to the client;
receiving, from each client, a client-specific encrypted and blinded first blinding value, wherein the client-specific encrypted and blinded first blinding value encrypts a blinded first blinding value that is blinded by a client-specific second blinding value;
receiving, from each client, a client-specific encrypted second blinding value;
decrypting each client-specific encrypted and blinded first blinding value to generate a first client-specific intermediate plaintext for each client;
multiplying each first client-specific intermediate plaintext by negative one to generate a second client-specific intermediate plaintext for each client;
encrypting each second client-specific intermediate plaintext to generate a client-specific intermediate ciphertext for each client; and
multiplying, for each client, the intermediate ciphertext by the client-specific rerandomized encrypted blinded input and the client-specific encrypted second blinding value, to homomorphically remove the first blinding value and the second blinding value, to generate a client-specific rerandomized encrypted secret input value, wherein the client-specific rerandomized encrypted secret input values are generated in an order that is unmapped to an order of receipt, at the service provider, of the encrypted secret input values.

### Claim 13 (depends on 12)

The method of claim 12, wherein the randomly-determined encrypted blinded input is provided to a respective client using a first oblivious transfer.

### Claim 14 (depends on 13)

The method of claim 13, wherein the first oblivious transfer of a randomly-determined encrypted blinded input to a respective client comprises the client receiving only one encrypted blinded input from among a set of encrypted blinded inputs having a count equal to the number of clients.

### Claim 15 (depends on 14)

The method of claim 14, wherein the first oblivious transfer of the randomly-determined encrypted blinded input to a respective client is performed without revealing to any party other than the client which encrypted blinded input of the set of encrypted blinded inputs is received by the client.

### Claim 16 (depends on 12)

The method of claim 12, wherein the client-specific secret input values are encrypted using a first cryptosystem.

### Claim 17 (depends on 16)

The method of claim 16, wherein the client-specific encrypted first blinding value is encrypted using a second cryptosystem that is different from the first cryptosystem.

### Claim 18

A computer program product encoded on a non-transitory storage medium, the product comprising non-transitory, computer readable instructions for causing one or more processors to perform operations comprising:
receiving, from each of multiple clients, an encrypted client-specific secret input value;
selecting a service provider random value;
sending the service provider random value to each of the clients;
randomly permuting the received encrypted client-specific secret input values using a random permutation;
providing, to each client, a randomly-determined encrypted blinded input from the received encrypted client-specific secret input values, wherein each randomly-determined encrypted blinded input is selected for a client based on a random index of the client;
providing, to each client, a client-specific encrypted first blinding value, wherein the client-specific encrypted first blinding value is an encryption of a client-specific first blinding value included in the randomly-determined encrypted blinded input received by the client;
receiving, from each client, a client-specific rerandomized encrypted blinded input, wherein the client-specific rerandomized encrypted blinded input is a rerandomization of the randomly-determined encrypted blinded input provided to the client;
receiving, from each client, a client-specific encrypted and blinded first blinding value, wherein the client-specific encrypted and blinded first blinding value encrypts a blinding of the first blinding value by a client-specific second blinding value;
receiving, from each client, a client-specific encrypted second blinding value;
decrypting each client-specific encrypted and blinded first blinding value to generate a first client-specific intermediate plaintext for each client;
multiplying each first client-specific intermediate plaintext by negative one to generate a second client-specific intermediate plaintext for each client;
encrypting each second client-specific intermediate plaintext to generate an intermediate ciphertext for each client; and
multiplying, for each client, the intermediate ciphertext by the client-specific rerandomized encrypted blinded input and the client-specific encrypted second blinding value, to homomorphically remove the first blinding value and the second blinding value, to generate a client-specific rerandomized encrypted secret input value, wherein the client-specific rerandomized encrypted secret input values are generated in an order that is unmapped to an order of receipt, at the service provider, of the encrypted secret input values.

### Claim 19 (depends on 18)

The computer program product of claim 18, wherein the randomly-determined encrypted blinded input is provided to a respective client using a first oblivious transfer.

### Claim 20 (depends on 19)

The computer program product of claim 19, wherein the first oblivious transfer of the randomly-determined encrypted blinded input to a respective client is performed without revealing to any party other than the client which encrypted blinded input of the set of encrypted blinded inputs is received by the client.
