Batch privacy information retrieval method and apparatus

Patent metadata

Field	Value
Publication number	US-12174990-B2
Application number	US-202418632273-A
Country	US
Kind code	B2
Filing date	Apr 10, 2024
Priority date	May 22, 2023
Publication date	Dec 24, 2024
Grant date	Dec 24, 2024

Abstract

A batch private information retrieval method and apparatus, including: agreeing on a hash function, calculating a serial number index in an original database, retaining a result of each serial number index for each hash function, and obtaining a first hash bucket; filling an index of a batch query into a second hash bucket of a same length as the first hash bucket by the client, and encoding a filling result by using a constant weight code encoding manner; encrypting an obtained encoding result as a batch query request by the client; comparing the batch query request with the first hash bucket by the server to obtain a corresponding intermediate result, calculating correspondingly the intermediate result and the original database to obtain a corresponding query result ciphertext; and decrypting the query result ciphertext by the client, and thus simultaneously obtaining a query result of the batch query request.

First claim

What is claimed is:

1. A batch private information retrieval method, comprising:
Agreeing, by a client and a server, on a hash function used in a cuckoo hash technique, calculating, by the cuckoo hash technique, a serial number index in an original database, retaining a result of each serial number index for each hash function, and obtaining a first hash bucket comprising several baskets, wherein the result of the serial number index in the first hash bucket is public to both the server and the client;
filling, by the client, an index of a batch query into a second hash bucket of a same length as the first hash bucket through a cuckoo hash algorithm, wherein a sequence index of the index of the batch query in the corresponding basket of the first hash bucket is filled at a corresponding position, and encoding a filling result by using a constant weight code encoding manner;
encrypting, by the client, an obtained encoding result by using a homomorphic encryption technique as a batch query request, and sending the batch query request to the server;
comparing, by the server, the received batch query request with the first hash bucket by using the homomorphic encryption technique to obtain a corresponding intermediate result;
calculating correspondingly, by the server, the intermediate result and the original database to obtain a query result ciphertext corresponding to the batch query request, and sending the query result ciphertext to the client; and
decrypting, by the client, the query result ciphertext, and thus simultaneously obtaining a query result of the batch query request.

2. The method according to claim 1 , wherein said encoding a filling result by using a constant weight code encoding manner comprises: selecting a length n of a largest basket in the first hash bucket as an encoding domain of a constant weight code, wherein a length corresponding to the constant weight code is m, selecting a number k of 1 in the constant weight code, and mapping the filling result into the constant weight code.

3. The method according to claim 1 , further comprising: encrypting, by the client, the obtained encoding result by using a Single Instruction Multiple Data SIMD technique of homomorphic encryption.

4. The method according to claim 3 , wherein said encrypting, by the client, the obtained encoding result by using a Single Instruction Multiple Data SIMD technique of homomorphic encryption comprises: for a hash bucket of a length B, encrypting B corresponding first bits in the hash bucket into a same ciphertext, encrypting a second bit into a second ciphertext, and so on, wherein when a corresponding position corresponding to the hash bucket is empty, all bits of the constant weight code are 0 by default.

5. The method according to claim 1 , wherein said comparing, by the server, the received batch query request with the first hash bucket by using the homomorphic encryption technique to obtain a corresponding intermediate result comprises:
performing corresponding constant weight code encoding on each sequence index in each basket of the first hash bucket; and
selecting, for each sequence index, a ciphertext corresponding to a bit 1 in a current constant weight code, and calculating a product of all selected ciphertexts by using a SIMD technique of homomorphic encryption to obtain the corresponding intermediate result.

6. The method according to claim 1 , wherein said calculating correspondingly, by the server, the intermediate result and the original database to obtain a query result ciphertext corresponding to the batch query request comprises:
multiplying the intermediate result by a corresponding position of the original database to obtain a ciphertext in the corresponding position of the original database; and
adding all results in each basket to form the query result ciphertext.

7. The method according to claim 6 , further comprising: when a length of content at the corresponding position of the original database exceeds a plaintext domain of a SIMD technique, slicing the content and querying the sliced content, respectively, to form several query result ciphertexts, and sending the query result ciphertexts to the client, respectively.

8. An electronic device, comprising:
one or more processors; and
a memory configured to store one or more programs;
wherein the one or more processors, when executed by the one or more processors, is configured to implement the method according to claim 1 .

9. A non-transitory computer-readable storage medium on which a computer instruction is stored, wherein the computer instruction, when executed by a processor, is configured to implement steps of the method according to claim 1 .

10. A batch private information retrieval apparatus, comprising:
a cuckoo hash module configured to agree on a hash function used in a cuckoo hash technique by a client and a server, calculate a serial number index in an original database by the cuckoo hash technique, retain a result of each serial number index for each hash function, and obtain a first hash bucket comprising several baskets, wherein the result of the serial number index in the first hash bucket is public to both the server and the client;
an encoding module configured to fill an index of a batch query into a second hash bucket of a same length as the first hash bucket through a cuckoo hash algorithm by the client, wherein a sequence index of the index of the batch query in the corresponding basket of the first hash bucket is filled at a corresponding position, and to encode a filling result by using a constant weight code encoding manner;
an encryption module configured to encrypt an obtained encoding result by using a homomorphic encryption technique as a batch query request by the client, and send the batch query request to the server;
a comparison module configured to compare the received batch query request with the first hash bucket by using the homomorphic encryption technique by the server to obtain a corresponding intermediate result;
a calculation module configured to calculate correspondingly the intermediate result and the original database by the server to obtain a query result ciphertext corresponding to the batch query request, and send the query result ciphertext to the client; and
a decryption module configured to decrypt the query result ciphertext by the client, and thus simultaneously obtain a query result of the batch query request.

Assignees

• Univ Zhejiang

Inventors

• Liu Jian
• Li Jingyu
• Wu Di
• Ren Kui

Classifications

• G06F21/602

  Providing cryptographic facilities or services · CPC title

• G06F9/3887

  controlled by a single instruction for multiple data lanes [SIMD] · CPC title

• G06F21/6227 Primary

  where protection concerns the structure of data, e.g. records, types, queries · CPC title