Private information retrieval using one query to perform multiple retrievals

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.

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.