CN-115642999-B - Method and system for efficient retrieval of private information

Abstract

The invention discloses a method for efficient retrieval of private information, which comprises the steps of fitting and obtaining a polynomial function based on data stored in a server, wherein each piece of data comprises a query key and a private information value, the function takes the query key as input and takes the private information value corresponding to the input query key as output, combining coefficients of each item in the function into a vector to serve as a coefficient vector, generating a pair of private key and public key, homomorphic encrypting the coefficient vector based on the public key to obtain a ciphertext coefficient vector, calculating and obtaining a ciphertext query result based on the ciphertext query key vector and the ciphertext coefficient vector when the ciphertext query key vector sent by a user is received, sending the ciphertext query result to the user, and decrypting the ciphertext query result by the user by adopting a decryption key to obtain a plaintext result of the private information value corresponding to the query key. Accordingly, the invention discloses a system for efficient retrieval of private information.

Inventors

• ZHOU QIXIAN
• LUO SAINAN

Assignees

• 支付宝(杭州)信息技术有限公司

Dates

Publication Date

20260508

Application Date

20220913

Claims (20)

1. 1. A method for efficient retrieval of private information, comprising the steps of: fitting to obtain a polynomial function based on data stored in a server, wherein each piece of data comprises a query key and a private information value, the function takes the query key as input and takes the private information value corresponding to the input query key as output; combining coefficients of each item in the function into a vector, and taking the vector as a coefficient vector; generating a pair of private key and public key, and homomorphic encrypting the coefficient vector based on the public key to obtain a ciphertext coefficient vector; When a ciphertext query key vector sent by a user is received, a ciphertext query result is obtained based on the ciphertext query key vector and a ciphertext coefficient vector, wherein the ciphertext query key vector is obtained by homomorphic encryption of the query key vector based on an authorization key sent to the user by a server; and sending the ciphertext query result to the user, and decrypting the ciphertext query result by the user by adopting a decryption key to obtain a plaintext result of the private information value corresponding to the query key.
2. 2. The method for efficient retrieval of private information according to claim 1, wherein the authorization key is obtained based on the steps of: The user sends identity information to a server for registration; the server randomly generates a reversible matrix pair; the server generates the authorization key based on the reversible matrix pair and the private key and sends the authorization key to the user.
3. 3. The method for efficient retrieval of private information according to claim 1, wherein the decryption key is generated based on a generated random matrix and a randomly generated pair of invertible matrices, the decryption key being generated by a client processing module.
4. 4. The method for efficient retrieval of private information according to claim 1, wherein the ciphertext query key vector is obtained based on the steps of: randomly generating a reversible matrix pair; Generating a random matrix; and generating a ciphertext query key vector based on the reversible matrix pair, the random matrix, the query key vector and the authorization key.
5. 5. The method for efficient retrieval of private information according to claim 1, wherein the query key vector is a query key vector matrix constructed based on the number of times information of the function and a plurality of query keys.
6. 6. The method for efficient retrieval of private information according to claim 1, wherein said function is obtained using least squares fitting.
7. 7. A system for efficient retrieval of private information, comprising a server, and a client processing module in data communication with the server, characterized in that: The server fits a polynomial function based on the data stored in the server, wherein each piece of data comprises a query key and a private information value, the function takes the query key as input, and the value corresponding to the input query key as output; the server generates a pair of private key and public key, and homomorphic encryption is carried out on the coefficient vector based on the public key so as to obtain a ciphertext coefficient vector; the user side processing module obtains a query key vector based on the query key and the frequency information of the function sent by the server, and also encrypts the query key vector homomorphically based on the authorization key sent by the server to obtain a ciphertext query key vector and sends the ciphertext query key vector to the server; When the server receives the ciphertext query key vector sent by the user side processing module, calculating based on the ciphertext query key vector and the ciphertext coefficient vector to obtain a ciphertext query result, and sending the ciphertext query result to the user side processing module; and the user side processing module decrypts the ciphertext query result by adopting a decryption key so as to obtain a plaintext result of the private information value corresponding to the query key.
8. 8. The system for efficient retrieval of private information according to claim 7, wherein when said client processing module sends user identity information to a server for registration, said server randomly generates a reversible matrix pair, generates an authorization key based on the reversible matrix pair and said private key, and sends the authorization key to the client processing module.
9. 9. The system for efficient retrieval of private information according to claim 7, wherein said client processing module randomly generates a reversible matrix pair and generates a random matrix, and then generates said decryption key based on said reversible matrix pair and random matrix.
10. 10. The system for efficient retrieval of private information according to claim 7, wherein said client processing module randomly generates a reversible matrix pair and generates a random matrix, and then generates a ciphertext query key vector based on said reversible matrix pair, random matrix, and said obtained query key vector and authorization key.
11. 11. The system for efficient retrieval of private information according to claim 7, wherein said client processing module constructs a query key vector matrix based on the number of times information of said function and a plurality of query keys as said query key vector.
12. 12. The system for efficient retrieval of private information according to claim 7, wherein said server derives said function using least squares fitting.
13. 13. A server for efficient retrieval of private information, characterized in that it is arranged to perform the steps of: fitting to obtain a polynomial function based on data stored in a server, wherein each piece of data comprises a query key and a private information value, the function takes the query key as input and takes the private information value corresponding to the input query key as output; combining coefficients of each item in the function into a vector, and taking the vector as a coefficient vector; generating a pair of private key and public key, and homomorphic encrypting the coefficient vector based on the public key to obtain a ciphertext coefficient vector; the ciphertext query key vector is generated by homomorphic encryption of the query key vector by adopting an authorization key generated by a server, the query key vector is obtained based on the query key and the frequency information of the function, and the frequency information of the function is sent to a user processing module by the server.
14. 14. The server of claim 13, wherein when it receives user identity information from an external transmission, it randomly generates a reversible matrix pair, and generates the authorization key based on the reversible matrix pair and the private key, and transmits the authorization key.
15. 15. The server of claim 13, wherein the function is obtained using a least squares fit.
16. 16. A client processing module for efficient retrieval of private information, characterized in that it is arranged to perform the steps of: obtaining a query key vector based on the query key and the received degree information of the polynomial function; Based on the received authorization key, homomorphic encryption is carried out on the query key vector to obtain a ciphertext query key vector, and the ciphertext query key vector is sent out; and receiving a ciphertext query result obtained based on the ciphertext query key vector, and decrypting the ciphertext query result by adopting a decryption key to obtain a plaintext result of the private information value corresponding to the query key.
17. 17. The client processing module of claim 16, wherein the decryption key is generated based on a generated random matrix and a randomly generated pair of invertible matrices.
18. 18. The client processing module of claim 16, wherein it generates a random matrix and randomly generates a reversible matrix pair, and then generates the ciphertext query key vector based on the reversible matrix pair, the random matrix, the query key vector, and the authorization key.
19. 19. The client processing module of claim 16, wherein the query key vector is a query key vector matrix constructed by the client processing module based on the number of times information of the function and a plurality of query keys.
20. 20. A computer readable storage medium, on which a computer program is stored, characterized in that the computer program, when executed in a computer, causes the computer to perform the steps performed by the server according to any of claims 13-15.

Description

Method and system for efficient retrieval of private information Technical Field The present invention relates to computer technology, and more particularly, to a method and system for private information retrieval. Background With the application and development of computer technology in various fields, the privacy calculation capable of realizing the availability of data and invisible has an increasingly important meaning in the aspect of protecting the data privacy, in particular in the fields of confidential medical health, military, financial services and the like. Among them, private information retrieval (private information retrieval) (abbreviated PIR) is an important issue in privacy computing. The technical problem to be solved by private information retrieval is how to complete the query under the condition that the private information of a user is not revealed when the user submits the query to a database, wherein the fact that the private information is not revealed comprises that the private information is not revealed to a third party and also comprises that the private information is not revealed to a server. In the prior art, some technical solutions for implementing private information inquiry are known. For example, private information retrieval is performed based on homomorphic encryption. However, private information retrieval based on homomorphic encryption requires multiple multiplication operations, which greatly reduces the retrieval efficiency of private information. In view of this, it is desirable to obtain a new private information retrieval scheme that can significantly improve the private information retrieval efficiency while protecting private information from being revealed. Disclosure of Invention One of the purposes of the invention is to provide a method for efficient retrieval of private information, which is characterized in that when private information retrieval is carried out, multiple multiplication calculation of ciphertext is converted into one matrix operation, so that the information retrieval efficiency is obviously improved while the private information is protected from being revealed. Based on the above object, the present invention proposes a method for efficient retrieval of private information, comprising the steps of: fitting to obtain a polynomial function based on data stored in a server, wherein each piece of data comprises a query key and a private information value, the function takes the query key as input and takes the private information value corresponding to the input query key as output; combining coefficients of each item in the function into a vector, and taking the vector as a coefficient vector; generating a pair of private key and public key, and homomorphic encrypting the coefficient vector based on the public key to obtain a ciphertext coefficient vector; when a ciphertext query key vector sent by a user is received, a ciphertext query result is obtained based on the ciphertext query key vector and the ciphertext coefficient vector, wherein the ciphertext query key vector is obtained by homomorphic encryption of the query key vector based on an authorization key sent by the user to the user by the server; and sending the ciphertext query result to the user, and decrypting the ciphertext query result by the user by adopting a decryption key to obtain a plaintext result of the private information value corresponding to the query key. In the present invention, for n pieces of data stored in a server (each piece of data includes a query key and a private information value corresponding to the query key), a polynomial function with the highest degree n may be fitted, where the function may be expressed as f (x) =a nxn+an-1xn-1+…+a1x+a0. It can be seen that the function contains coefficient information a n、an-1、……、a1、a0 and order information n, n-1. The coefficient vector X can be obtained based on the coefficient information, and the query key vector K can be obtained based on the number of times information. The method is different from the homomorphic encryption in the prior art, the method carries out homomorphic encryption on the coefficient vector X based on a public key generated by a server to obtain the ciphertext coefficient vector X c, and calculates the ciphertext query result V c＝Kc×Xc based on the ciphertext query key vector K c and the ciphertext coefficient vector X c obtained by the query key vector K, so that multiple multiplication operations of the homomorphic encryption are converted into one-time matrix operation, and the operation efficiency is greatly improved. Further, in some embodiments, the authorization key is obtained based on the steps of: The user sends identity information to a server for registration; the server randomly generates a reversible matrix pair; the server generates an authorization key based on the reversible matrix pair and the private key and sends the authorization key to the user. Still furth