Granted Patent B2

US 12,659,140 · App. 18/773,918 · Granted Jun 16, 2026

Inventors: Eli Simon Fox-Epstein (Los Angeles, CA); Kevin Wei Li Yeo (New York, NY)

Assignee: Google LLC

H04L9/085G06F16/285G06F21/6227

Abstract

Claims (74)

1 . A method, comprising:

receiving, at a server device and from a client device, a batch of queries that includes queries to special buckets across database shards;

generating, by the server device, a set of query results that includes server-encrypted secret shares from the special buckets queried by the batch of queries;

obtaining, at the server device and from the client device, client-encrypted secret shares, wherein the client-encrypted secret shares are client encrypted versions of the secret shares that were included in the set of query results;

receiving, at the server device and from the client device, a set of client-server-encrypted secret shares, wherein the set of client-server-encrypted secret shares are client encrypted versions of a set of server-encrypted secret shares that (i) were transmitted to the client device and (ii) includes server-encrypted secret shares that were not included in the set of query results;

determining, by the server device, how many of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-server-encrypted secret shares received from the client device; and

classifying, by the server device, the client device based on how many of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-server-encrypted secret shares received from the client device.

2 . The method of claim 1 , further comprising:

removing, by the server device, server decryption from the set of client-server-encrypted secret shares received from the client device to obtain a full set of client-encrypted secret shares, wherein determining how many of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-server-encrypted secret shares received from the client device comprises comparing the client-encrypted secret shares received from the client device to the set of client-encrypted secret shares obtained by removing the server decryption from the set of client-server-encrypted secret shares.

3 . The method of claim 2 , wherein classifying the client device comprises determining that the client device is malicious based on a determination that fewer than a required number of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-encrypted secret shares obtained by removing the server decryption from the set of client-server-encrypted secret shares.

4 . The method of claim 3 , further comprising:

receiving, from the client device, a set of client-encrypted entity identifiers;

encrypting, by the server device, the set of client-encrypted entity identifiers to create a set of sever-client-encrypted identifiers;

transmitting, by the server device, the set of server-client-encrypted identifiers to the client device.

5 . The method of claim 4 , further comprising:

generating a partitioned database in which a database is partitioned into multiple database shards each having a shard identifier that logically distinguishes each database shard from other database shards, and database entries in each database shard are partitioned into buckets having a bucket identifier that logically distinguishes each bucket in the shard from other buckets in the shard.

6 . The method of claim 5 , further comprising:

adding a special bucket to each database shard;

including, in each special bucket, special data that is known to the server device, but not the client device; and

after each query to a given shard, updating the special data in the special bucket of the given shard to maintain privacy of information contained in the special bucket of the given shard.

7 . The method of claim 6 , further comprising:

generating, by the client device, a set of queries using the set of server-client-encrypted identifiers;

generating, by the client device, a set of decryption keys using the set of server-client-encrypted identifiers;

encrypting, by the client device, the set of queries to create the batch of client-encrypted queries.

8 . A system comprising:

a database configured to store data; and

a server device configured to process queries using the database and execute instructions that cause the server device to perform operations comprising:

receiving, from a client device, a batch of queries that includes queries to special buckets across database shards;

generating a set of query results that includes server-encrypted secret shares from the special buckets queried by the batch of queries;

obtaining, from the client device, client-encrypted secret shares, wherein the client-encrypted secret shares are client encrypted versions of the secret shares that were included in the set of query results;

receiving, from the client device, a set of client-server-encrypted secret shares, wherein the set of client-server-encrypted secret shares are client encrypted versions of a set of server-encrypted secret shares that (i) were transmitted to the client device and (ii) includes server-encrypted secret shares that were not included in the set of query results;

determining how many of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-server-encrypted secret shares received from the client device; and

classifying the client device based on how many of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-server-encrypted secret shares received from the client device.

9 . The system of claim 8 , wherein the instructions cause the server device to perform operations further comprising:

removing server decryption from the set of client-server-encrypted secret shares received from the client device to obtain a full set of client-encrypted secret shares, wherein determining how many of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-server-encrypted secret shares received from the client device comprises comparing the client-encrypted secret shares received from the client device to the set of client-encrypted secret shares obtained by removing the server decryption from the set of client-server-encrypted secret shares.

10 . The system of claim 9 , wherein classifying the client device comprises determining that the client device is malicious based on a determination that fewer than a required number of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-encrypted secret shares obtained by removing the server decryption from the set of client-server-encrypted secret shares.

11 . The system of claim 10 , wherein the instructions cause the server device to perform operations further comprising:

receiving, from the client device, a set of client-encrypted entity identifiers;

encrypting the set of client-encrypted entity identifiers to create a set of sever-client-encrypted identifiers;

transmitting the set of server-client-encrypted identifiers to the client device.

12 . The system of claim 11 , wherein the instructions cause the server device to perform operations further comprising:

generating a partitioned database in which a database is partitioned into multiple database shards each having a shard identifier that logically distinguishes each database shard from other database shards, and database entries in each database shard are partitioned into buckets having a bucket identifier that logically distinguishes each bucket in the shard from other buckets in the shard.

13 . The system of claim 12 , wherein the instructions cause the server device to perform operations further comprising:

adding a special bucket to each database shard;

including, in each special bucket, special data that is known to the server device, but not the client device; and

after each query to a given shard, updating the special data in the special bucket of the given shard to maintain privacy of information contained in the special bucket of the given shard.

14 . The system of claim 13 , wherein the instructions cause the server device to perform operations further comprising:

generating, by the client device, a set of queries using the set of server-client-encrypted identifiers;

generating, by the client device, a set of decryption keys using the set of server-client-encrypted identifiers;

encrypting, by the client device, the set of queries to create the batch of client-encrypted queries.

15 . A non-transitory computer readable medium storing instructions that, upon execution by one or more data processing apparatus, cause the one or more data processing apparatus to perform operations comprising:

receiving, from a client device, a batch of queries that includes queries to special buckets across database shards;

generating a set of query results that includes server-encrypted secret shares from the special buckets queried by the batch of queries;

obtaining, from the client device, client-encrypted secret shares, wherein the client-encrypted secret shares are client encrypted versions of the secret shares that were included in the set of query results;

receiving, from the client device, a set of client-server-encrypted secret shares, wherein the set of client-server-encrypted secret shares are client encrypted versions of a set of server-encrypted secret shares that (i) were transmitted to the client device and (ii) includes server-encrypted secret shares that were not included in the set of query results;

determining how many of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-server-encrypted secret shares received from the client device; and

classifying the client device based on how many of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-server-encrypted secret shares received from the client device.

16 . The non-transitory computer readable medium of claim 15 , wherein the instructions cause the one or more data processing apparatus device to perform operations further comprising:

removing server decryption from the set of client-server-encrypted secret shares received from the client device to obtain a full set of client-encrypted secret shares, wherein determining how many of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-server-encrypted secret shares received from the client device comprises comparing the client-encrypted secret shares received from the client device to the set of client-encrypted secret shares obtained by removing the server decryption from the set of client-server-encrypted secret shares.

17 . The non-transitory computer readable medium of claim 16 , wherein classifying the client device comprises determining that the client device is malicious based on a determination that fewer than a required number of the secret shares are included in both of the client-encrypted secret shares received from the client device and the set of client-encrypted secret shares obtained by removing the server decryption from the set of client-server-encrypted secret shares.

18 . The non-transitory computer readable medium of claim 17 , wherein the instructions cause the one or more data processing apparatus to perform operations further comprising:

receiving, from the client device, a set of client-encrypted entity identifiers;

encrypting the set of client-encrypted entity identifiers to create a set of sever-client-encrypted identifiers;

transmitting the set of server-client-encrypted identifiers to the client device.

19 . The non-transitory computer readable medium of claim 18 , wherein the instructions cause the one or more data processing apparatus to perform operations further comprising:

generating a partitioned database in which a database is partitioned into multiple database shards each having a shard identifier that logically distinguishes each database shard from other database shards, and database entries in each database shard are partitioned into buckets having a bucket identifier that logically distinguishes each bucket in the shard from other buckets in the shard.

20 . The non-transitory computer readable medium of claim 19 , wherein the instructions cause the one or more data processing apparatus to perform operations further comprising:

adding a special bucket to each database shard;

including, in each special bucket, special data that is known to the one or more data processing apparatus, but not the client device; and

after each query to a given shard, updating the special data in the special bucket of the given shard to maintain privacy of information contained in the special bucket of the given shard.

21 . The non-transitory computer readable medium of claim 20 , wherein the instructions cause the one or more data processing apparatus to perform operations further comprising:

generating, by the client device, a set of queries using the set of server-client-encrypted identifiers;

generating, by the client device, a set of decryption keys using the set of server-client-encrypted identifiers;

encrypting, by the client device, the set of queries to create the batch of client-encrypted queries.

Assignments (1)

Continuity (3)

References Cited (38)