# US 2017/0323118 A1 · Apparatus and Method for Private Information Retrieval

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

- Number: US 2017/0323118 A1
- Document ID: US20170323118A1
- Status: Published application
- Kind: A1
- Application number: 15/586,892
- Filed: 2017-05-04
- Published: 2017-11-09
- Earliest claimed: 2016-05-05
- Assignees: The Johns Hopkins University
- Applicants: The Johns Hopkins University
- Inventors: Russell A. Fink; David R. Zaret; Rachel B. Stonehirsch; Robert M. Seng; Samantha M. Tyson
- Web page: https://patentgrep.com/patent/US20170323118A1

## CPC

- G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes}
- G06F 16/2457: with adaptation to user needs
- G06F 16/9535: Search customisation based on user profiles and personalisation
- G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries}
- H04L 9/008: {involving homomorphic encryption}
- H04L 9/006: {involving public key infrastructure [PKI] trust models (network architecture or network communication protocol for supporting authentication of entities using certificates in a packet data network H04L63/0823)}
- 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

Apparatuses and methods for private information retrieval are provided. One example method may include receiving a query state machine that is an encoding of a search pattern. The query state machine may include a plurality of states and a transition function that defines a plurality of transitions based on the search pattern. The example method may also include performing a private query against a target query string of a target query record by applying the query state machine to the target query string to develop a private encoding. The method may further include transmitting query results based on the private encoding.

## Claims

### Claim 1

A method for conducting private information retrieval comprising:
receiving, at a data repository computer system, a query state machine from a data requesting computer system, wherein the query state machine is an encoding of a search pattern, wherein the query state machine includes a plurality of states and a transition function that defines a plurality of transitions based on the search pattern, wherein the plurality of states includes an initial state and one or more accepting states, and wherein each transition of the transition function indicates (a) a next state based on an input symbol and (b) a private filter value for the next state based on whether the next state is an accepting state or a non-accepting state;
performing a private query against a target query string of a target query record in the data repository computer system by applying the query state machine to the target query string, wherein applying the query state machine to the target query string comprises generating a private encoding using a private filter value of a final state of the query state machine for the target query string, the final state being determined by a traversal through the query state machine based on the target query string, wherein the private encoding is based on target data retrieved from the target query record in response to the final state being an accepting state; and
transmitting query results based on the private encoding.

### Claim 2 (depends on 1)

The method of claim 1, wherein performing the private query further comprises, prior to generating the private encoding:
sequentially inputting subsequent symbols of the target query string into the transition function to determine a next query state; and
inputting a last symbol of the target query string into the transition function to determine the final state of the query state machine for the target query string and to obtain the private filter value for the final state.

### Claim 3 (depends on 1)

The method of claim 1, wherein performing the private query further comprises combining the private encoding in a query results buffer with previous private encodings.

### Claim 4 (depends on 3)

The method of claim 3, wherein combining the private encoding comprises using a multiplicative operation.

### Claim 5 (depends on 1)

The method of claim 1, wherein the query state machine comprises a Deterministic Finite Automaton (DFA).

### Claim 6 (depends on 1)

The method of claim 1, wherein the target query string has an unbounded length.

### Claim 7 (depends on 1)

The method of claim 1, wherein the search pattern includes at least one wildcard symbol.

### Claim 8 (depends on 1)

The method of claim 1, wherein the query state machine comprises additional states and associated transitions associated with dummy search patterns that differ from the search pattern.

### Claim 9 (depends on 1)

The method of claim 1, wherein the query state machine comprises an additional state derived from a selected state of the plurality of states, the additional state having at least one reassigned transition into the selected state to the additional state and at least one copied transition into the additional state from the selected state.

### Claim 10 (depends on 1)

The method of claim 1, wherein the query state machine does not include a subset of states that have no transitions into states that are not members of the subset of states, wherein the subset of states includes at least two states.

### Claim 11

An apparatus for performing private information retrieval comprising:
a data repository computer system comprising
at least one processor; and
at least one memory,
wherein the at least one processor, using the at least one memory, is configured to:
receive a query state machine from a data requesting computer system, wherein the query state machine is an encoding of a search pattern, wherein the query state machine includes a plurality of states and a transition function that defines a plurality of transitions based on the search pattern, wherein the plurality of states includes an initial state and one or more accepting states, and wherein each transition of the transition function indicates (a) a next state based on an input symbol and (b) a private filter value for the next state based on whether the next state is an accepting state or a non-accepting state;
perform a private query against a target query string of a target query record in the data repository computer system by applying the query state machine to the target query string, wherein being configured to apply the query state machine comprises being configured to generate a private encoding using a private filter value of a final state of the query state machine for the target query string, the final state being determined by a traversal through the query state machine based on the target query string, wherein the private encoding is based on target data retrieved from the target query record in response to the final state being an accepting state; and
transmit query results based on the private encoding.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein the at least one processor configured to perform the private query is further configured to:
sequentially input subsequent symbols of the target query string into the transition function to determine a next query state; and
input a last symbol of the target query string into the transition function to determine the final state of the query state machine for the target query string and to obtain the private filter value for the final state.

### Claim 13 (depends on 11)

The apparatus of claim 11, wherein the at least one processor configured to perform the private query is further configured to combine the private encoding in a query results buffer with previous private encodings.

### Claim 14 (depends on 13)

The apparatus of claim 13, wherein the at least one processor are further configured to combine the private encoding using a multiplicative operation.

### Claim 15 (depends on 11)

The apparatus of claim 11, wherein the query state machine comprises a Deterministic Finite Automaton (DFA).

### Claim 16 (depends on 11)

The apparatus of claim 11, wherein the target query string has an unbounded length.

### Claim 17 (depends on 11)

The apparatus of claim 11, wherein the search pattern includes at least one wildcard symbol.

### Claim 18

A method for performing private information retrieval comprising:
receiving, at a data repository computer system, a query state machine from a data requesting computer system, wherein the query state machine is an encoding of a search pattern provided to the data requesting computer system, wherein the search pattern is provided to the data requesting computer system by a data requesting entity to search for and retrieve data at the data repository computer system in a manner that maintains privacy of the search pattern, wherein the query state machine includes a plurality of states and a transition function that defines a plurality of transitions based on the search pattern, wherein the plurality of states includes an initial state and one or more accepting states, and wherein each transition indicates (a) a next state based on an input symbol and (b) a private filter value for the next state based on whether the next state is an accepting state or a non-accepting state;
performing a private query against a target query string of a target query record in the data repository computer system by applying the query state machine to the target query string, wherein applying the query state machine to the target query string comprises:
sequentially inputting subsequent symbols of the target query string into the transition function to determine a next query state;
inputting a last symbol of the target query string into the transition function to determine a final state of the query state machine for the target query string and to obtain a private filter value for the final state;
generating a private encoding based on the private filter value of the final state, wherein the private encoding is based on target data retrieved from the target query record in response to the private filter value indicating that the final state is an accepting state;
combining the private encoding in a query results buffer with previous private encodings; and
transmitting the query results buffer to the data requesting computer system for decrypting the query results buffer, at the data requesting computer system, to retrieve any target data of a target query record that has been included in a private encoding.

### Claim 19 (depends on 18)

The method of claim 18, wherein receiving the query state machine includes receiving the query state machine comprising a Deterministic Finite Automaton (DFA).

### Claim 20 (depends on 18)

The method of claim 18, wherein the search pattern includes at least one wildcard symbol.
