# US 11,308,081 B1 · Private information retrieval using one query to perform multiple retrievals > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,308,081 B1 - Document ID: US11308081B1 - Status: Granted - Kind: B1 - Application number: 17/127,127 - Filed: 2020-12-18 - Granted: 2022-04-19 - Earliest claimed: 2020-12-18 - Assignees: Seagate Technology LLC - Applicants: Seagate Technology LLC - Inventors: Vipin Singh Sehrawat; Foo Yee Yeo - Web page: https://patentgrep.com/patent/US11308081B1 ## CPC - G06F 16/244: {Grouping and aggregation} - G06F 16/2237: {Vectors, bitmaps or matrices} - G06F 16/2455: Query execution - G06F 16/248: Presentation of query results - H04L 9/085: {Secret sharing or secret splitting, e.g. threshold schemes} - H04L 9/088: {Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms (network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068)} - H04L 9/0894: {Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage} - 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 A method and apparatus for private information retrieval from a database, wherein the retrieval includes providing a covering vector for a plurality of database entries of the database. The covering vector is defined such that an inner product of the covering vector is zero with more than one member of a covering vector family that includes the covering vector. The retrieval includes generating database queries based on the covering vector and transmitting the database queries to at least two servers. An identical copy of the database may be stored on each of the at least two servers. Shares are received in response to the query, and these shares are aggregated, and a reconstruction algorithm executes to reconstruct the query results. ## Claims ### Claim 1 A method of privately retrieving database entries from a database, the method comprising: providing a covering vector for a plurality of database entries of the database, wherein the covering vector is defined such that an inner product of the covering vector is zero with more than one member of a covering vector family that includes the covering vector; generating database queries based on the covering vector; transmitting the database queries to a plurality of servers; responsive to transmitting the database queries, receiving a plurality of shares: from the plurality of servers; and obtaining an aggregation of database entries based on the plurality of shares. ### Claim 2 (depends on 1) The method of claim 1, wherein generating database queries includes executing a query generation algorithm, and wherein the method comprises: decomposing the query generation algorithm into t query generation algorithms, wherein t corresponds to a count of the plurality of servers. ### Claim 3 (depends on 2) The method of claim 2, further comprising: randomizing the t query generation algorithms based on a set of randomization parameters. ### Claim 4 (depends on 3) The method of claim 3, wherein each randomization parameter of the set of randomization parameters comprises a vector. ### Claim 5 (depends on 3) The method of claim 3, wherein the set of randomization parameters is private to a computer system executing the t query generation algorithms. ### Claim 6 (depends on 5) The method of claim 5, wherein shares of the plurality of shares do not include information identifying the computer system executing the t query generation algorithms. ### Claim 7 (depends on 1) The method of claim 1, further comprising: reconstructing an aggregate of database entries using a reconstruction algorithm, wherein the reconstruction algorithm takes as input the plurality of shares from the plurality of servers. ### Claim 8 (depends on 1) The method of claim 1, wherein the aggregation of database entries comprises a summation of database entries. ### Claim 9 (depends on 1) The method of claim 1, wherein the aggregation of database entries comprises a logical OR of the database entries. ### Claim 10 An apparatus for privately retrieving database entries from a database, the apparatus comprising: a network interface; and a computing apparatus comprising processing circuitry coupled to the network interface and configured to: provide a covering vector for a plurality of database entries of the database, wherein the covering vector is defined such that an inner product of the covering vector is zero with more than one member of a covering vector family that includes the covering vector; generate database queries based on the covering vector; transmit the database queries to a plurality of servers over the network interface; responsive to transmitting the database queries, receive a plurality of shares from the plurality of servers; and obtain an aggregation of database entries based on the plurality of shares. ### Claim 11 (depends on 10) The apparatus of claim 10, wherein the processing circuitry is further configured to: execute a query generation algorithm to generate the database queries; and decompose the query generation algorithm into t query generation algorithms, wherein t corresponds to a count of the plurality of servers. ### Claim 12 (depends on 11) The apparatus of claim 11, wherein the processing circuitry is further configured to: randomize the t query generation algorithms based on a set of randomization parameters. ### Claim 13 (depends on 12) The apparatus of claim 12, wherein each randomization parameter of the set of randomization parameters comprises a vector. ### Claim 14 (depends on 12) The apparatus of claim 12, wherein the set of randomization parameters is private to a computer system executing the t query generation algorithms. ### Claim 15 (depends on 14) The apparatus of claim 14, wherein shares of the plurality of shares do not include information identifying the processing circuitry that executes the t query generation algorithms. ### Claim 16 (depends on 10) The apparatus of claim 10, wherein the processing circuitry is further configured to: reconstruct an aggregate of database entries using a reconstruction algorithm, wherein the reconstruction algorithm takes as input the plurality of shares from the plurality of servers, and wherein the aggregation of database entries comprises a summation of the database entries or a logical OR of the database entries. ### Claim 17 One or more non-transitory tangible processor-readable storage media embodied with instructions for executing on one or more processors and circuits of a device a process for private information retrieval, the instructions directing the one or more processors to perform one or more operations comprising: providing a covering vector for a plurality of database entries of a database, wherein a covering vector is defined such that an inner product of the covering vector is zero with more than one member of a covering vector family that includes the covering vector; generating database queries based on the covering vector; transmitting the database queries to a plurality of servers, the plurality of servers each including a copy of the database; responsive to transmitting the database queries, receiving a plurality of shares from the plurality of servers; and obtaining an aggregation of database entries based on the plurality of shares. ### Claim 18 (depends on 17) The non-transitory tangible processor-readable storage media of claim 17, wherein generating database queries includes executing a query generation algorithm, and wherein the operations include: decomposing the query generation algorithm into t query generation algorithms, wherein t corresponds to a count of the plurality of servers; and randomizing the t query generation algorithms based on a set of randomization parameters. ### Claim 19 (depends on 18) The non-transitory tangible processor-readable storage media of claim 18, wherein each randomization parameter of the set of randomization parameters comprises a vector, and wherein the set of randomization parameters is private to a computer system executing the t query generation algorithms. ### Claim 20 (depends on 17) The non-transitory tangible processor-readable storage media of claim 17, wherein the operations include: reconstructing an aggregate of database entries using a reconstruction algorithm, wherein the reconstruction algorithm takes as input the plurality of shares from the plurality of servers, wherein the aggregation of database entries comprises a summation of database entries or a logical OR of the database entries.