Search

CN-122020696-A - Data retrieval method, device and equipment

CN122020696ACN 122020696 ACN122020696 ACN 122020696ACN-122020696-A

Abstract

A data retrieval method and device relate to the field of computers. The method is applied to a server, the server comprises a plurality of items which are arranged as a first matrix, the method comprises the steps of receiving a query request of a client, wherein the query request comprises a first homomorphic ciphertext, a plaintext of the first homomorphic ciphertext is used for representing the position of the item to be queried in the first matrix, responding to the query request, transforming the first homomorphic ciphertext to obtain a second homomorphic ciphertext, the plaintext of the second homomorphic ciphertext can represent the position of the item to be queried in the second matrix, the second matrix is obtained by transforming the position of the item of the first matrix, calculating a plaintext vector obtained by encoding the item of the second matrix and the second homomorphic ciphertext to obtain a ciphertext of the item to be queried, and sending the ciphertext of the item to be queried to the client.

Inventors

  • LI ZENGPENG
  • LU PENGFEI
  • WANG MEI
  • LI JIE

Assignees

  • 华为技术有限公司
  • 山东大学

Dates

Publication Date
20260512
Application Date
20241112

Claims (20)

  1. 1. A data retrieval method, wherein the method is applied to a server, the server including a plurality of entries arranged as a first matrix, the method comprising: Receiving a query request of a client, wherein the query request comprises a first homomorphic ciphertext, and the plaintext of the first homomorphic ciphertext is used for representing the position of an item to be queried in the first matrix; In response to the query request, transforming the first homomorphic ciphertext to obtain a second homomorphic ciphertext, wherein the plaintext of the second homomorphic ciphertext can represent the position of the item to be queried in a second matrix, and the second matrix is obtained by transforming the item position of the first matrix; carrying out operation on a plaintext vector obtained by encoding the entry of the second matrix and the second homomorphic ciphertext to obtain the ciphertext of the entry to be queried; And sending the ciphertext of the item to be queried to the client.
  2. 2. The method of claim 1, wherein the first homomorphic ciphertext comprises a row homomorphic ciphertext and a column homomorphic ciphertext, and plaintext of the row homomorphic ciphertext and plaintext of the column homomorphic ciphertext are used to represent a row and a column, respectively, in which the item to be queried is located; the responding to the inquiry request transforms the first homomorphic ciphertext to obtain a second homomorphic ciphertext, which comprises the following steps: And responding to the query request, correspondingly rotating the row homomorphic ciphertext and/or the column homomorphic ciphertext according to a transformation rule from the first matrix to the second matrix, and obtaining the second homomorphic ciphertext.
  3. 3. The method according to claim 2, wherein said transforming said first homomorphic ciphertext in response to said query request to obtain a second homomorphic ciphertext, comprises: responding to the query request, if the second matrix is obtained by extracting entries on a diagonal line in the first matrix and arranging the entries into columns, rotating the column homomorphic ciphertext to obtain at least one column rotation ciphertext, so that the position of the entry to be queried in the second matrix can be represented by the second homomorphic ciphertext formed by the column rotation ciphertext and the row homomorphic ciphertext; And if the second matrix is obtained by extracting the items arranged on the diagonal line of the first matrix as rows, rotating the row homomorphic ciphertext to obtain at least one row rotation ciphertext, so that the second homomorphic ciphertext formed by the row rotation ciphertext and the column homomorphic ciphertext can represent the position of the item to be queried in the second matrix.
  4. 4. A method according to claim 2 or 3, characterized in that before said receiving a query request of a client, the method comprises: Receiving a setting request; Traversing the first matrix row by row in response to the setting request, and arranging the items on the main diagonal of the first matrix into a first column of the second matrix; arranging the items on each secondary diagonal parallel to the main diagonal into the remaining columns of the second matrix, wherein any one of the remaining columns further comprises items which are different in row and column from the items on the secondary diagonal in the first matrix, so that the number of the items in the first column is equal to that of the items in the first column; Each column of entries in the second matrix is encoded into one of the plaintext vectors, respectively.
  5. 5. The method of claim 4, wherein the first matrix and the second matrix are each a matrix of v N x v N, N being the number of entries of the plurality of entries, N >1, and wherein plaintext of the homomorphic ciphertext and plaintext of the column homomorphic ciphertext are each a single-heat vector; the responding to the inquiry request transforms the first homomorphic ciphertext to obtain a second homomorphic ciphertext, which comprises the following steps: Responding to the query request, carrying out rotation transformation on the column homomorphic ciphertext for V N-1 times to respectively obtain V N-1 column rotation ciphertext, so that the column homomorphic ciphertext and each column rotation ciphertext are respectively aligned with each column in the second square matrix; The plaintext vector obtained by encoding the entry of the second matrix and the second homomorphic ciphertext are operated to obtain the ciphertext of the entry to be queried, and the method comprises the following steps: And multiplying the column homomorphic ciphertext and each column rotation ciphertext with the plaintext vectors of the aligned columns respectively, and multiplying the accumulated result of the obtained product with the row homomorphic ciphertext to obtain the ciphertext of the item to be queried.
  6. 6. A method according to claim 2 or 3, characterized in that before said receiving a query request of a client, the method comprises: Receiving a setting request; Traversing the first matrix column by column in response to the setting request, and arranging the entries on the main diagonal of the first matrix into a first row of the second matrix; Arranging the items on each secondary diagonal parallel to the main diagonal into the remaining rows of the second matrix, wherein any one of the remaining rows further comprises the items which are different from the items on the secondary diagonal in the first matrix and are in different columns so as to be equal to the first row of items; Each row of entries in the second matrix is encoded into one of the plaintext vectors, respectively.
  7. 7. The method of claim 6, wherein the first matrix and the second matrix are each a matrix of v N x v N, N being the number of entries of the plurality of entries, N >1, and wherein plaintext of the homomorphic ciphertext and plaintext of the column homomorphic ciphertext are each a single-heat vector; the responding to the inquiry request transforms the first homomorphic ciphertext to obtain a second homomorphic ciphertext, which comprises the following steps: Responding to the query request, carrying out rotation transformation on the line homomorphic ciphertext for V N-1 times to respectively obtain V N-1 line rotation ciphertexts, so that the line homomorphic ciphertext and each line rotation ciphertext are respectively aligned with each line in the second square matrix; The plaintext vector obtained by encoding the entry of the second matrix and the second homomorphic ciphertext are operated to obtain the ciphertext of the entry to be queried, and the method comprises the following steps: And multiplying the row homomorphic ciphertext and each row rotation ciphertext with the plaintext vectors of the aligned rows respectively, and multiplying the accumulated result of the obtained product with the column homomorphic ciphertext to obtain the ciphertext of the item to be queried.
  8. 8. The method of claim 1, wherein the server includes a plurality of buckets, each of the buckets including a plurality of entries arranged as the first matrix, and the second matrix being derived from the first matrix transforming the locations of the entries; the method specifically comprises the following steps: Receiving the query requests of the client side for a plurality of items to be queried, wherein the items to be queried respectively belong to different storage barrels, and the plaintext of the first homomorphic ciphertext is used for representing the positions of the items to be queried in the first matrixes respectively according to a preset sequence; responding to the query request, transforming the first homomorphic ciphertext to obtain the second homomorphic ciphertext, wherein the plaintext of the second homomorphic ciphertext can represent the position of each item to be queried in the second matrix to which each item belongs according to the preset sequence; The plaintext vectors obtained by encoding the entries of each second matrix according to the preset sequence are operated with the second homomorphic ciphertext to obtain ciphertext of the plurality of entries to be queried; and sending the ciphertext of the plurality of items to be queried to the client.
  9. 9. The method of claim 8, wherein the first matrix and the second matrix are each a matrix of v N x v N, N being the number of entries of the number of entries, N >1, and wherein prior to receiving the client query request for the target entry, the method comprises: receiving a setting request, wherein the setting request comprises a first parameter, the first parameter is used for describing the number of batch processes supportable by the server, and the first parameter is larger than V N; In response to the setting request, for any one of the first square arrays, arranging the items on the main diagonal of the first square array into a first item group of the second square array, and arranging the items on each diagonal parallel to the main diagonal into the remaining ≡n-1 item groups of the second square array, the item groups being one row or one column, Wherein any one of the remaining item groups further comprises items which are different in row and column from the items on the subordinate diagonal in the first matrix so as to be equal to the items of the first item group; For all the entries of the second matrix, acquiring entries according to preset intervals, and encoding the entries into plaintext vectors, wherein the preset intervals are the ratio of the first parameter to the V N.
  10. 10. A data retrieval apparatus for application to a server, the server including a plurality of entries arranged in a first matrix, the apparatus comprising: The receiving module is used for receiving a query request of the client, wherein the query request comprises a first homomorphic ciphertext, and the plaintext of the first homomorphic ciphertext is used for representing the position of an item to be queried in the first matrix; The processing module is used for responding to the query request, transforming the first homomorphic ciphertext to obtain a second homomorphic ciphertext, wherein the plaintext of the second homomorphic ciphertext can represent the position of the item to be queried in a second matrix, and the second matrix is obtained by transforming the item position of the first matrix; The processing module is further used for calculating a plaintext vector obtained by encoding the entry of the second matrix and the second homomorphic ciphertext to obtain the ciphertext of the entry to be queried; the processing module is further configured to send the ciphertext of the item to be queried to the client.
  11. 11. The apparatus of claim 10, wherein the first homomorphic ciphertext comprises a row homomorphic ciphertext and a column homomorphic ciphertext, the plaintext of the row homomorphic ciphertext and the plaintext of the column homomorphic ciphertext being used to represent the row and column, respectively, in which the item to be queried is located; The processing module is specifically configured to: And responding to the query request, correspondingly rotating the row homomorphic ciphertext and/or the column homomorphic ciphertext according to a transformation rule from the first matrix to the second matrix, and obtaining the second homomorphic ciphertext.
  12. 12. The apparatus of claim 11, wherein the processing module is specifically configured to: responding to the query request, if the second matrix is obtained by extracting entries on a diagonal line in the first matrix and arranging the entries into columns, rotating the column homomorphic ciphertext to obtain at least one column rotation ciphertext, so that the position of the entry to be queried in the second matrix can be represented by the second homomorphic ciphertext formed by the column rotation ciphertext and the row homomorphic ciphertext; And if the second matrix is obtained by extracting the items arranged on the diagonal line of the first matrix as rows, rotating the row homomorphic ciphertext to obtain at least one row rotation ciphertext, so that the second homomorphic ciphertext formed by the row rotation ciphertext and the column homomorphic ciphertext can represent the position of the item to be queried in the second matrix.
  13. 13. The apparatus according to claim 11 or 12, wherein the receiving module is further configured to receive a setting request; The processing module is further used for traversing the first matrix row by row in response to the setting request, and arranging the items on the main diagonal of the first matrix into a first column of the second matrix; The processing module is further configured to arrange the entries on each secondary diagonal parallel to the primary diagonal into remaining columns of the second matrix, where any one of the remaining columns further includes entries in a different row and a different column in the first matrix than the entries on the secondary diagonal, so as to be equal to the number of entries in the first column; the processing module is further configured to encode each column of entries in the second matrix into one of the plaintext vectors.
  14. 14. The apparatus of claim 13, wherein the first matrix and the second matrix are each a matrix of v N x v N, N being the number of entries of the number of entries, N >1, and wherein plaintext of the homomorphic ciphertext and plaintext of the column homomorphic ciphertext are each a single-heat vector; The processing module is specifically configured to: Responding to the query request, carrying out rotation transformation on the column homomorphic ciphertext for V N-1 times to respectively obtain V N-1 column rotation ciphertext, so that the column homomorphic ciphertext and each column rotation ciphertext are respectively aligned with each column in the second square matrix; The plaintext vector obtained by encoding the entry of the second matrix and the second homomorphic ciphertext are operated to obtain the ciphertext of the entry to be queried, and the method comprises the following steps: And multiplying the column homomorphic ciphertext and each column rotation ciphertext with the plaintext vectors of the aligned columns respectively, and multiplying the accumulated result of the obtained product with the row homomorphic ciphertext to obtain the ciphertext of the item to be queried.
  15. 15. The apparatus according to claim 11 or 12, wherein the receiving module is further configured to receive a setting request; the processing module is further configured to respond to the setting request, traverse the first matrix column by column, and arrange the entries located on the main diagonal of the first matrix into a first row of the second matrix; The processing module is further configured to arrange entries on each secondary diagonal parallel to the primary diagonal into remaining rows of the second matrix, where any one of the remaining rows further includes entries in a different row and a different column in the first matrix than the entries on the secondary diagonal, so as to be equal to the number of entries in the first row; The processing module is further configured to encode each row of entries in the second matrix into one of the plaintext vectors.
  16. 16. The apparatus of claim 15, wherein the first matrix and the second matrix are each a matrix of v N x v N, N being the number of entries of the number of entries, N >1, and wherein plaintext of the homomorphic ciphertext and plaintext of the column homomorphic ciphertext are each a single-heat vector; The processing module is specifically configured to: Responding to the query request, carrying out rotation transformation on the line homomorphic ciphertext for V N-1 times to respectively obtain V N-1 line rotation ciphertexts, so that the line homomorphic ciphertext and each line rotation ciphertext are respectively aligned with each line in the second square matrix; The plaintext vector obtained by encoding the entry of the second matrix and the second homomorphic ciphertext are operated to obtain the ciphertext of the entry to be queried, and the method comprises the following steps: And multiplying the row homomorphic ciphertext and each row rotation ciphertext with the plaintext vectors of the aligned rows respectively, and multiplying the accumulated result of the obtained product with the column homomorphic ciphertext to obtain the ciphertext of the item to be queried.
  17. 17. The apparatus of claim 10, wherein the server includes a plurality of buckets, each of the buckets including a plurality of entries arranged as the first matrix, and the second matrix derived from the first matrix transforming the locations of the entries; The receiving module is used for receiving the query requests of the client side for a plurality of items to be queried, the items to be queried respectively belong to different storage barrels, and the plaintext of the first homomorphic ciphertext is used for representing the positions of the items to be queried in the first matrixes respectively according to a preset sequence; The processing module is further configured to transform the first homomorphic ciphertext in response to the query request to obtain the second homomorphic ciphertext, where plaintext of the second homomorphic ciphertext can represent positions of the entries to be queried in the second matrices to which the entries belong according to the preset sequence; The processing module is further configured to operate a plaintext vector obtained by encoding the entries of each second matrix according to the preset sequence and the second homomorphic ciphertext to obtain ciphertext of the plurality of entries to be queried; The processing module is further configured to send ciphertext of the plurality of entries to be queried to the client.
  18. 18. The apparatus of claim 17, wherein the first matrix and the second matrix are each a matrix of v N x v N, N being the number of entries of the number of entries, N >1; The receiving device is further used for receiving a setting request, wherein the setting request comprises a first parameter, the first parameter is used for describing the number of batch processes supportable by the server, and the first parameter is larger than V < N >; the processing module is further configured to, in response to the setting request, arrange, for any one of the first square arrays, the entries located on the main diagonal of the first square array into a first entry group of one of the second square arrays, and arrange the entries located on each of the secondary diagonal parallel to the main diagonal into remaining ∈n-1 entry groups of the second square array, the entry groups being one row or one column, Wherein any one of the remaining item groups further comprises items which are different in row and column from the items on the subordinate diagonal in the first matrix so as to be equal to the items of the first item group; the processing module is further used for collecting entries according to preset intervals aiming at the entries of all the second matrixes, wherein the entries are encoded into plaintext vectors, and the preset intervals are the ratio of the first parameter to the V & lt N & gt.
  19. 19. A server, wherein the server comprises a processor and a memory; the processor is configured to execute instructions stored in the memory, such that the processor performs the method of any one of claims 1-9.
  20. 20. A cluster of computing devices, comprising at least one computing device, each computing device comprising a processor and a memory; the processor of the at least one computing device is configured to execute instructions stored in a memory of the at least one computing device to cause the cluster of computing devices to perform the method of any of claims 1-9.

Description

Data retrieval method, device and equipment Technical Field The present application relates to the field of computer technologies, and in particular, to a data retrieval method, apparatus, and device. Background The privacy information retrieval (Private information retrieval, PIR) protocol allows clients to query entries in the retrieval server database without the server knowing the index or key being queried. PIR is widely applied to various hidden inquiry scenes such as finance, medicine and the like, and is one of the most widely applied technologies for current privacy calculation. In general, a stateful PIR protocol may be employed between a client and a server. Specifically, in the preprocessing stage, the client needs to maintain a local state hint information (local STATE HINT) sent by the server in advance, where the information generally includes information for indicating how the client searches for the target data index, masking technical information for confusion query, related access control information, and the like, and if the data is stored in a different server, the hint needs to further include information describing how the data is split. In this way, the client performs on the basis of the state in the subsequent online inquiry, thereby achieving the purpose of more efficient online inquiry. The stateful PIR protocol tends to be very costly to communicate because the hit that the client downloads and maintains during the processing phase tends to be tens of MB (MByte megabytes), and each subsequent online query also requires hundreds of KB (KByte kilobytes) of traffic, making the communication overhead prohibitive. In addition, the stateful PIR protocol may involve complex encryption algorithms and computation procedures, such as when the client-side is based on keyword retrieval, and when the storage level in the database is large (e.g., millions), the server requires more computational effort to perform the cryptographic computation on the query ciphertext, resulting in greater computation costs. Disclosure of Invention The embodiment of the application provides a data retrieval method, a device, equipment, a computer storage medium and a computer program product, which can realize stateless efficient privacy information retrieval and achieve balance of calculation and communication overhead. In a first aspect, an embodiment of the present application provides a data retrieval method, where the method is applied to a server, where the server includes a plurality of entries arranged as a first matrix, and the method includes receiving a query request of a client, where the query request includes a first homomorphic ciphertext, and plaintext of the first homomorphic ciphertext is used to characterize a position of an entry to be queried in the first matrix; the method comprises the steps of responding to a query request, transforming a first homomorphic ciphertext to obtain a second homomorphic ciphertext, enabling the plaintext of the second homomorphic ciphertext to represent the position of an item to be queried in a second matrix, transforming the position of the item of the first matrix to obtain the second matrix, calculating a plaintext vector obtained by encoding the item of the second matrix and the second homomorphic ciphertext to obtain the ciphertext of the item to be queried, and sending the ciphertext of the item to be queried to a client. In this embodiment, the entries are arranged in a matrix (i.e., a first matrix) in the server, and the client may initiate the request by the coordinates (rank position) of the entries in the matrix when querying. The server further reconstructs a second matrix to confuse the positions of the original entries, and then transforms homomorphic encrypted index information (i.e., the first homomorphic ciphertext) in the client request in an encrypted state, so that the ciphertext of the entry to be queried can be calculated in the second matrix. In the whole process, the server does not need to maintain the local state hit by the client, so that the communication traffic between the client and the client can be greatly reduced, the server performs calculation under homomorphic encryption based on the position of the item in the item matrix of the database, the calculation logic complexity is low, the calculation cost is reduced, the balance of communication and calculation cost is achieved, and the query efficiency is improved. The method comprises the steps of receiving a query request of a client, wherein the query request is used for requesting to query a target item according to index information, the index information comprises homomorphic ciphertext of a first single hot vector and a second single hot vector, effective elements in the first single hot vector and effective elements of the second single hot vector respectively correspond to positions of the target item in a first dimension and a second dimension of a first matrix, the