# US 2024/0205016 A1 · Searchable encryption

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

- Number: US 2024/0205016 A1
- Document ID: US20240205016A1
- Status: Published application
- Kind: A1
- Application number: 18/552,227
- Filed: 2021-03-23
- Published: 2024-06-20
- Earliest claimed: 2021-03-23
- Assignees: Vaultree Ltd.
- Applicants: Vaultree Ltd.
- Inventors: Shaun MC BREARTY
- Web page: https://patentgrep.com/patent/US20240205016A1

## CPC

- G06F 16/2255: {Hash tables}
- H04L 9/002: {Countermeasures against attacks on cryptographic mechanisms (network architectures or network communication protocols for protection against malicious traffic H04L63/1441)}
- G06F 16/24573: {using data annotations, e.g. user-defined metadata}
- G06F 16/248: Presentation of query results
- G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries}
- G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes}
- G06F 21/72: in cryptographic circuits
- H04L 9/0894: {Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage}
- H04L 9/3213: {using tickets or tokens, e.g. Kerberos (network architectures or network communication protocols for entities authentication using tickets in a packet data network H04L63/0807)}
- H04L 9/3242: {involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC}
- 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

The present disclosure is directed towards a system, method, and computer readable storage medium for searchable encryption. A plurality of search terms are extracted from at least a part of a data structure. A keyed-hash value for each search term is calculated and stored in a list. The value of a bit in a predetermined position within each keyed-hash value is examined. If the value of the bit is a first value for α of the keyed-hash values and a second value for α of the keyed-hash values, wherein α is a number greater or equal to two and the first value is different to the second value, then the set of keyed-hash values is split into two lists. Each list is assigned a search token value.

## Claims

### Claim 1

A system for searchable encryption, comprising:
a client device configured to:
extract a plurality of search terms from at least part of a data structure;
calculate a keyed-hash value for a search term of the plurality of search terms and store the keyed-hash value in a list;
examine a bit in a first predetermined position within the keyed-hash value to obtain the value of the bit;
perform a first determination to determine if it is true that for at least α of the keyed-hash values in the list the value of the bit has a first value, and for at least α of the keyed-hash values the value of the bit has a second value, wherein α is a number greater or equal to two and the first value is different to the second value; and
if the first determination is true:
split the list of keyed-hash values into a first list and a second list; and
assign a first search token value to the first list and a second search token value to the second list, such that each search token value is associated with a plurality of search terms.

### Claim 2 (depends on 1)

The system of claim 1, wherein the first search token value equals the first value and the second search token value equals the second value.

### Claim 3 (depends on 2)

The system of claim 2, wherein the index build module is further configured to:
perform a second determination to determine if it is true that:
for at least α of the keyed-hash values in the first list:
a bit in a second predetermined position has the first value; and
the bit in the second predetermined position has the second value;
for at least α of the keyed-hash values in the second list:
the bit in the second predetermined position has the first value; and
the bit in the second predetermined position has the second value; and
if the second determination is true:
split the first list and the second list, such that the first list is split into a new first list and a new second list, and the second list is split into a new third list and a new fourth list; and
assign a new first search token value to the new first list, a new second search token value to the new second list, a new third search token value to the new third list, and a new fourth search token value to the new fourth list.

### Claim 4 (depends on 3)

The system of claim 3, wherein:
the new first search token value equals the first search token value appended with the first value;
the new second search token value equals the first search token value appended with the second value;
the new third search token value equals the second search token value appended with the first value; and
the new fourth search token value equals the second search token value appended with the second value.

### Claim 5 (depends on 1)

The system of claim 1, wherein the index build module is configured to encrypt the keyed-hash values before the keyed-hash values are provided to a server.

### Claim 6 (depends on 1)

The system of claim 1, wherein the index build module is configured to generate and store a posting list, wherein the posting list is a data structure for storing an identification of each data structure that at least one of the plurality of search terms occurs in.

### Claim 7 (depends on 6)

The system of claim 6, further comprising a search module configured to:
receive a search term from a user;
calculate a keyed-hash value of the search term;
calculate a search token value from the keyed-hash value of the search term by selecting the β most-significant bits of the keyed-hash value of the search term, where 2β is the number of lists; and
forward the search token value to a server.

### Claim 8 (depends on 7)

The system of claim 7, wherein the search module is further configured to:
receive a noisy access pattern from the server, wherein a noisy access pattern comprises a collection of data structures and data structure identifications associated with more than one search term, wherein at least one data structure in the collection is associated with the search term received from the user;
match the data structure identifications received in the noisy access pattern with the identification of the data structures associated with the search term in the posting list; and
remove the data structures from the noisy access pattern that do not have a matching identification.

### Claim 9

A method for searchable encryption, comprising:
extracting a plurality of search terms from at least a part of a data structure;
calculating a keyed-hash value for a search term of the plurality of search terms and store the keyed-hash value in a list;
examining a bit in a first predetermined position in the keyed-hash value to obtain the bit;
performing a first determination to determine if it is true that for at least α of the keyed-hash values in the list the bit has a first value, and for at least α of the keyed-hash values the bit has a second value, wherein α is greater or equal to two and the first value is different to the second value; and
if the first determination is true:
splitting the list of keyed-hash values into a first list and a second list; and
assigning a first search token value to the first list and second search token value to the second list, such that each search token value is associated with a plurality of search terms.

### Claim 10 (depends on 9)

The method of claim 9, wherein the first search token value equals the first value and the second search token value equals the second value.

### Claim 11 (depends on 10)

The method of claim 10, further comprising:
performing a second determination to determine if it is true that:
for at least α of the keyed-hash values in the first list:
a bit in a second predetermined position has the first value; and
the bit in the second predetermined position has the second value;
for at least α of the keyed-hash values in the second list:
the bit in the second predetermined position has the first value; and
the bit in the second predetermined position has the second value; and
if the second determination is true:
splitting the first list and second list, such that the first list is split into a new first list and a new second list, and the second list is split into a new third list and a new fourth list; and
assigning a new first search token value to the new first list, a new second search token value to the new second list, a new third search token value to the new third list, and a new fourth search token value to the new fourth list.

### Claim 12 (depends on 11)

The method of claim 11, wherein:
the new first search token value equals the first search token value appended with the first value;
the new second search token value equals the first search token value appended with the second value;
the new third search token value equals the second search token value appended with the first value; and
the new fourth search token value equals the second search token value appended with the second value.

### Claim 13 (depends on 9)

The method of claim 9, comprising encrypting the keyed-hash values before the keyed-hash values are provided to a server.

### Claim 14 (depends on 9)

The method of claim 9, comprising generating and storing a posting list, wherein the posting list is a data structure for storing an identification of each data structure that at least one of the plurality of search terms occurs in.

### Claim 15

A computer readable storage medium comprising a set of instructions which, when executed by a processor, cause the processor to:
extract a plurality of search terms from at least a part of a data structure;
calculate a keyed-hash value for a search term of the plurality of search terms and store the keyed-hash value in a list;
examine a bit in a first predetermined position in the keyed-hash value to obtain the value of the bit;
perform a first determination to determine if it is true that for at least α of the keyed-hash values in the list the value of the bit has a first value, and for at least α of the keyed-hash values the value of the bit has a second value, wherein α is greater or equal to two and the first value is different to the second value; and
if the first determination is true:
split the list of keyed-hash values into a first list and a second list; and
assign a first search token value to the first list and second search token value to the second list, such that each search token value is associated with a plurality of search terms.

### Claim 16 (depends on 15)

The method of claim 15, wherein the first search token value equals the first value, and the second search token value equals the second value.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
performing a second determination to determine if it is true that:
for at least α of the keyed-hash values in the first list:
a bit in a second predetermined position has the first value; and
the bit in the second predetermined position has the second value;
for at least α of the keyed-hash values in the second list:
the bit in the second predetermined position has the first value; and
the bit in the second predetermined position has the second value; and
if the second determination is true:
splitting the first list and second list, such that the first list is split into a new first list and a new second list, and the second list is split into a new third list and a new fourth list; and
assigning a new first search token value to the new first list, a new second search token value to the new second list, a new third search token value to the new third list, and a new fourth search token value to the new fourth list.

### Claim 18 (depends on 17)

The method of claim 17, wherein:
the new first search token value equals the first search token value appended with the first value;
the new second search token value equals the first search token value appended with the second value;
the new third search token value equals the second search token value appended with the first value; and
the new fourth search token value equals the second search token value appended with the second value.

### Claim 19 (depends on 15)

The method of claim 15, comprising encrypting the keyed-hash values before the keyed-hash values are provided to a server.

### Claim 20 (depends on 15)

The method of claim 15, comprising generating and storing a posting list, wherein the posting list is a data structure for storing an identification of each data structure that at least one of the plurality of search terms occurs in.
