CN-117407423-B - Multi-data-source-oriented batch trace query method, system and device

CN117407423BCN 117407423 BCN117407423 BCN 117407423BCN-117407423-B

Abstract

The embodiment of the application discloses a batch trace query method, a system and a device for multiple data sources, wherein the method comprises the steps that a client synchronizes an original polynomial and a polynomial business loop of the original polynomial to each of k service ends; the method comprises the steps of calculating an n-order polynomial according to n query key values to obtain a first polynomial, calculating k second polynomials and k interpolation polynomials by each of k service ends according to respective key value databases, calculating a first calculation result and k second calculation results by a client end and each client end, decomposing the first calculation result according to a preset constraint relation by the client end to obtain a first decomposition result, determining k third calculation results by the k service ends, determining a fourth calculation result according to the k third calculation results and the original polynomials by the client end, and traversing n query key values according to the fourth calculation result by the client end to obtain a query result. By adopting the embodiment of the application, the data query efficiency can be improved.

Inventors

WANG YUKUN
ZHOU BOYANG
FENG XINYU
WANG WANWAN
HE HAO
YAO MING

Assignees

深圳市洞见智慧科技有限公司

Dates

Publication Date: 20260508
Application Date: 20231013

Claims (10)

1. A multi-data source-oriented batch trace query method is characterized by being applied to a multi-party computing system, wherein the multi-party computing system comprises a client and k service ends, the client comprises n query key values, each client in the k service ends comprises a key value database, each key value database comprises a plurality of key value data pairs, each key value data pair comprises a key value and a data, and n and k are positive integers, and the method comprises the following steps: Synchronizing the original polynomial and a polynomial quotient loop of the original polynomial to each of the k service ends by the client; calculating an n-order polynomial according to the n inquiry key values to obtain a first polynomial; Calculating n-order polynomials according to the respective key value database by each of the k service terminals to obtain k second polynomials, and respectively calculating corresponding interpolation polynomials to obtain k interpolation polynomials; The client side respectively carries out operation with each client side in the k service sides based on ring-OLE protocol to obtain a first calculation result and k second calculation results of the client side, wherein one second calculation result corresponding to each service side in the k service sides is obtained, and a preset constraint relation is met between the first calculation result and each second calculation result in the k second calculation results; the first calculation result is decomposed according to the preset constraint relation through the client to obtain a first decomposition result, and the first decomposition result is broadcast to each of the k service ends; Decomposing the corresponding second calculation result by each of the k service ends according to the preset constraint relation to obtain k second decomposition results; Determining an n-order polynomial of each server according to the polynomial quotient loop and the k interpolation polynomials by each server in the k servers to obtain k third polynomials; each of the k service ends carries out operation according to the respective second decomposition result, third polynomial, the second polynomial and the first decomposition result to obtain k third calculation results; determining a fourth calculation result by the client according to the k third calculation results and the original polynomial, and traversing the n query key values according to the fourth calculation result to obtain a target query result.
2. The method of claim 1, wherein the computing, by the client, with each of the k servers based on a ring-OLE protocol, respectively, to obtain a first calculation result and k second calculation results of the client, includes: The client side respectively carries out operation with each client side in the k server sides based on the PCG programmability in the ring-OLE protocol to obtain a first calculation result and k second calculation results of the client side; The first calculation result comprises a first reference polynomial and a second reference polynomial; each second calculation result in the k second calculation results corresponds to a third reference polynomial and a fourth reference polynomial respectively; the second reference polynomial=the first reference polynomial is a target third reference polynomial and a target fourth reference polynomial, and the target third reference polynomial and the target fourth reference polynomial are polynomials of any second calculation result of the k second calculation results.
3. The method of claim 2, wherein when k is 2, the k service terminals include a first service terminal and a second service terminal, and the output of the client terminal satisfies the following relationship: s A ＝a′·e B +r B ＝a′·e C +r C Wherein a' represents the first reference polynomial, s A represents the second reference polynomial, e B 、r B represents the third and fourth reference polynomials of the second calculation result of the first server, e C 、r C represents the third and fourth reference polynomials of the second calculation result of the second server, and s A is a calculation value.
4. A method according to claim 3, wherein decomposing the first calculation result according to the preset constraint relation to obtain a first decomposition result comprises: decomposing the first reference polynomial according to the following formula, wherein the method comprises the following steps of: a′=a′ 0 +a′ 1 ·x n t A ＝p A -a′ 0 Wherein a ' 0 、t A 、a′ 1 、x n represents the first decomposition result, a' represents the first reference polynomial, and p A represents the first polynomial.
5. The method of claim 4, wherein the decomposing, by each of the k service ends, the corresponding second calculation result according to the preset constraint relation to obtain k second decomposition results includes: Decomposing the second calculation result according to the following formula, wherein the second calculation result is specifically as follows: Wherein, the X n represents a second decomposition result of the first server; x n represents a second decomposition result of the second server.
6. The method of claim 5, wherein the k third polynomials include (d B ,g B ) and (d C ,g C ), wherein (d B ,g B ) is the third polynomial of the first server and (d C ,g C ) is the third polynomial of the second server; Each of the k service ends performs an operation according to the respective second decomposition result, third polynomial, the second polynomial and the first decomposition result to obtain k third calculation results, including: The k third calculation results are determined according to the following formula, and the specific steps are as follows: Wherein p B represents a second polynomial of the first server, p C represents a second polynomial of the second server, and F (x) represents the original polynomial; a third calculation result representing the first server; And representing a third calculation result of the second server.
7. The method of claim 6, wherein said determining, by the client, a fourth calculation from the k third calculations and the original polynomial comprises: Wherein U B 、V B represents the fourth calculation result.
8. A multiparty computing system is characterized by comprising a client and k service ends, wherein the client comprises n inquiry key values, each client in the k service ends comprises a key value database, each key value database comprises a plurality of key value data pairs, each key value data pair comprises a key value and a data, n and k are positive integers, The client is used for synchronizing the original polynomial and the polynomial quotient loop of the original polynomial to each of the k service ends; calculating an n-order polynomial according to the n inquiry key values to obtain a first polynomial; each of the k service ends is used for calculating an n-order polynomial according to the respective key value database to obtain k second polynomials, and calculating corresponding interpolation polynomials to obtain k interpolation polynomials; The client is used for respectively carrying out operation with each client in the k service ends based on ring-OLE protocol to obtain a first calculation result and k second calculation results of the client, wherein one second calculation result corresponding to each service end in the k service ends is obtained, and a preset constraint relation is met between the first calculation result and each second calculation result in the k second calculation results; Each of the k service ends is used for decomposing a corresponding second calculation result according to the preset constraint relation to obtain k second decomposition results, determining an n-order polynomial of each service end according to the polynomial quotient loop and the k interpolation polynomials to obtain k third polynomials, and carrying out operation according to the respective second decomposition results, third polynomials, the second polynomials and the first decomposition results to obtain k third calculation results; The client is used for determining a fourth calculation result according to the k third calculation results and the original polynomial, traversing the n query key values according to the fourth calculation result, and obtaining a target query result.
9. An electronic device comprising a processor, a memory for storing one or more programs and configured to be executed by the processor, the programs comprising instructions for performing the steps in the method of any of claims 1-7.
10. A computer-readable storage medium, characterized in that a computer program for electronic data exchange is stored, wherein the computer program causes a computer to perform the method according to any one of claims 1-7.

Description

Multi-data-source-oriented batch trace query method, system and device Technical Field The application relates to the technical field of privacy computation or computer technology, in particular to a batch trace query method, system and device for multiple data sources. Background In practice, the track query (Private Information Retrieval, PIR) technique allows users to query information in a server database without revealing their actual query content. In conventional track queries, a user sends a query request to a single data source and obtains a response, and as the degree of data dispersion increases, many scenarios require information to be retrieved from multiple data sources. The multi-data-source-oriented trace query technique refers to the fact that in the case of multiple data sources, a user can send a query request in broadcast form to all data sources while maintaining its privacy. The batch trace query technology can enable a user to retrieve a plurality of query results in a single query, and the query efficiency is improved. Therefore, the batch trace query technology for multiple data sources has the advantages that the query efficiency is greatly improved, the privacy is guaranteed, the method is widely applied to the fields of finance, medical care and the like, and currently, only one piece of data can be searched for by a single query of a client in the existing trace query scheme, the query efficiency is low, so that the problem of how to realize batch trace query to improve the query efficiency is urgently solved. Disclosure of Invention The embodiment of the application provides a multi-data-source-oriented batch trace query method, a multi-data-source-oriented batch trace query system and a multi-data-source-oriented batch trace query device, which can realize batch trace query so as to improve query efficiency. In a first aspect, an embodiment of the present application provides a batch trace query method for multiple data sources, which is applied to a multiparty computing system, where the multiparty computing system includes a client and k servers, the client includes n query key values, each of the k servers includes a key value database, each key value database includes multiple key value data pairs, each key value data pair includes a key value and a data, and n and k are positive integers, and the method includes: Synchronizing the original polynomial and a polynomial quotient loop of the original polynomial to each of the k service ends by the client; calculating an n-order polynomial according to the n inquiry key values to obtain a first polynomial; Calculating n-order polynomials according to the respective key value database by each of the k service terminals to obtain k second polynomials, and respectively calculating corresponding interpolation polynomials to obtain k interpolation polynomials; The client side respectively carries out operation with each client side in the k service sides based on ring-OLE protocol to obtain a first calculation result and k second calculation results of the client side, wherein one second calculation result corresponding to each service side in the k service sides is obtained, and a preset constraint relation is met between the first calculation result and each second calculation result in the k second calculation results; the first calculation result is decomposed according to the preset constraint relation through the client to obtain a first decomposition result, and the first decomposition result is broadcast to each of the k service ends; Decomposing the corresponding second calculation result by each of the k service ends according to the preset constraint relation to obtain k second decomposition results; Determining an n-order polynomial of each server according to the polynomial quotient loop and the k interpolation polynomials by each server in the k servers to obtain k third polynomials; each of the k service ends carries out operation according to the respective second decomposition result, third polynomial, the second polynomial and the first decomposition result to obtain k third calculation results; determining a fourth calculation result by the client according to the k third calculation results and the original polynomial, and traversing the n query key values according to the fourth calculation result to obtain a target query result. In a second aspect, an embodiment of the present application provides a multiparty computing system, including a client, k servers, the client including n query keys, each of the k servers including a key database, each key database including a plurality of key data pairs, each key data pair including a key and a data, n, k being positive integers, The client is used for synchronizing the original polynomial and the polynomial quotient loop of the original polynomial to each of the k service ends; calculating an n-order polynomial according to the n inquiry key values to obtain a first