CN115801233A - Method and client for constructing confusion set - Google Patents

Abstract

One or more embodiments of the present specification provide a method and client for implementing the construction of an obfuscation set. In the method, a client sends a sensitive field encrypted by the client to a server, and the same sensitive field encrypted by the server is obtained through interaction with the server; the client side retrieves in the query base according to the sensitive field encrypted by the server side to obtain a first identification set of the matching records; the client selects at least one point except the ID field and the field of interest in the query base, the selected at least one point is used as a retrieval condition, a retrieval statement is constructed according to the retrieval condition and the original field of interest, and retrieval is executed on the query base to obtain a second identification set of the matching records; and the client constructs an confusion set according to the first identification set and the second identification set.

Description

A method and client for realizing the construction of a confusion set

technical field

The embodiments of this specification belong to the technical field of privacy computing, and in particular relate to a method and a client for realizing the construction of a confusion set.

Background technique

Privacy-Preserving Computing (Privacy-Preserving Computing) is a technology collection that realizes data analysis and calculation on the premise of protecting the data itself from leakage, and realizes that the data is available and invisible. Through privacy protection computing technology, the conversion and release of data value can be realized under the premise of fully protecting data and privacy security.

At present, the mainstream technologies for realizing privacy-preserving computing mainly include three directions: the first type is cryptography-based privacy computing technology represented by Secure Multi-Party Computation (SMPC); the second type is federated learning ( Federated Learning (FL) is a technology derived from the fusion of artificial intelligence and privacy protection technology; the third category is Confidential Computing (CC) technology based on trusted hardware represented by Trusted Execution Environment (Trust Execution Environment) . In addition, it also includes differential privacy (DifferentialPrivacy, DP) and so on. Differential Privacy (DP) actually protects the calculation results, not the calculation process; federated learning, secure multi-party computing, and confidential computing protect the calculation process and the intermediate results of the calculation process.

The first type of multi-party secure computing includes four basic technologies, namely Garbled Circuit (GC), Secret Sharing (Secret Sharing), Oblivious Transfer (Oblivious Transfer) and Homomorphic Encryption (HE). Among them, homomorphic encryption is a special encryption algorithm. It is directly calculated on the basis of ciphertext, and the calculation result is the same as that based on the decrypted plaintext. It also includes Partially Homomorphic Encryption (PHE) and identical Fully Homomorphic Encryption (FHE).

Secure multi-party computing relies on its solid security theoretical foundation to provide privacy protection capabilities for inputting secret data, and to achieve privacy-protected computing process security. At present, there are two main implementation technical routes for secure multi-party computation, including general secure multi-party computation and problem-specific secure multi-party computation. The former can solve various computing problems, but this "universal" technical route usually has a huge system and various expenses; the latter designs special protocols for specific problems, such as private set intersection PSI (Private Set Intersection, PSI) , Privacy Information Retrieval (PIR), etc., can often obtain calculation results at a lower cost than general secure multi-party computing protocols, but requires domain experts to carefully design application scenarios, and generally cannot be applied to general scenarios and the design cost higher.

Privacy set intersection is the intersection of the data held by both parties without revealing any additional information. Additional information refers to any information other than the data intersection of the two parties. Privacy set intersection is very useful in real-world scenarios, such as data alignment in vertical federated learning, or friend discovery through address books in social software.

Private information retrieval is a method for clients to retrieve information from a database. During the retrieval process, the query party hides the query target identifier, and the data server provides matching query results but cannot know the specific query object.

Contents of the invention

The purpose of this specification is to provide a method and client for constructing a confusion set, including:

A method for realizing the construction of a confusion set, the client receives the query base sent by the server, and the query base is obtained after being encrypted by the database; the encryption/decryption performed by the client and the server on the same target adopts an exchangeable sequence of encryption /decryption algorithm;

The client sends the encrypted sensitive field to the server, and obtains the same sensitive field encrypted by the server through interaction with the server;

The client retrieves in the query base according to the sensitive field encrypted by the server, and obtains a first identification set of matching records;

The client selects at least one point in the query base except the ID field and the field of interest, uses the selected at least one point as a retrieval condition, constructs a retrieval statement according to the retrieval condition and the original field of interest, and constructs a retrieval statement in the query base Execute retrieval on the above to obtain the second identification set of matching records;

The client constructs a confusion set according to the first identity set and the second identity set.

A client that realizes the construction of a confusion set, the encryption/decryption performed by the client and the server on the same target adopts an encryption/decryption algorithm that can be exchanged, and:

The client is configured with a query base, and the query base is obtained after the server encrypts the database;

The client sends the sensitive field encrypted by itself to the server, and obtains the same sensitive field encrypted by the server through interaction with the server; in the query base, according to the search based on the sensitive field encrypted by the server, a matching record is obtained The first identification set; select at least one point in the query base except the ID field and the field of interest, use the selected at least one point as a retrieval condition, construct a retrieval statement according to the retrieval condition and the original field of interest, and in Searching is performed on the query basis to obtain a second identification set of matching records; a confusion set is constructed according to the first identification set and the second identification set.

A client that implements the construction of a confusion set, including:

processor,

The memory stores a program, wherein the above method is executed when the processor executes the program.

A storage medium is used for storing a program, wherein when the program is executed, the client executes the above-mentioned method.

In the above-mentioned embodiment, by constructing the retrieval statement and executing the retrieval on the query base, the structure of the second identification set is obtained, and then the confusion set is constructed, which can make the confusion set more reasonable, thereby avoiding the privacy leakage of the client due to the unreasonable structure of the confusion set .

Description of drawings

In order to more clearly illustrate the technical solutions of the embodiments of this specification, the following will briefly introduce the drawings that need to be used in the description of the embodiments. Obviously, the drawings in the following description are only some embodiments recorded in this specification. , for those skilled in the art, other drawings can also be obtained according to these drawings without paying creative labor.

Fig. 1 is a schematic flow chart of an embodiment;

Fig. 2 is a schematic flow chart of an embodiment;

Fig. 3 is a schematic flow diagram of an embodiment.

Detailed ways

In order to enable those skilled in the art to better understand the technical solutions in this specification, the technical solutions in the embodiments of this specification will be clearly and completely described below in conjunction with the drawings in the embodiments of this specification. Obviously, the described The embodiments are only some of the embodiments in this specification, not all of them. Based on the embodiments in this specification, all other embodiments obtained by persons of ordinary skill in the art without creative efforts shall fall within the protection scope of this specification.

As mentioned earlier, PIR is a method for clients to retrieve information from a database. The PIR scheme is a scheme proposed by Chor B et al. in 1995 to solve the problem of protecting user query privacy. The main purpose of the PIR scheme is to ensure that the query request submitted by the query user to the database on the server is completed under the condition that the private information queried by the user is not leaked, that is, the server does not know the specific query information of the user and the retrieved information during the retrieval process. data item.

The application scenarios of private information retrieval include:

i. The patient wants to inquire about the treatment drugs for his disease through the medical system. If the disease is named as the query condition, the medical system will know that the patient may suffer from such a disease, and the patient's privacy will be leaked. Query through private information Such leakage problems can be avoided.

ii. During the domain name and trademark application process, users need to first submit their applied domain name or trademark information to the relevant database to check whether it already exists, but if they do not want the service provider to know their applied name, they can pre-register.

iii. In the securities market, a user wants to inquire about a certain stock information, but he cannot disclose the stock he is interested in to the service provider so as to affect the stock price and his own preference.

A simple implementation is that the database sends all data to the client, but it cannot protect the security of the database, that is, the privacy of the server cannot be guaranteed. A PIR that can ensure the privacy and security of the client and the database at the same time is called a symmetrical PIR (Symmetrical PIR, SPIR), and a PIR that can ensure the privacy and security of one of the client and the database at the same time is called an asymmetrical PIR (Asymmetrical PIR, APIR). ). According to the number of database copies, it is divided into multi-copy PIR and single-copy PIR. The multi-copy PIR protocol requires that multiple database copies cannot collude, which is difficult to meet in real-world scenarios, so more consideration is given to single-copy PIR. Single-copy PIR can only achieve Computational PIR (CPIR). In most PIR schemes, it is always assumed that the client knows which bit (single bit) of the database it wants to retrieve. However, in real scenarios, the client often searches based on keywords (it does not know the specific location of the database corresponding to the keyword), and what it wants to get back is a string (multi-bit). All in all, a practical PIR usually needs to meet multiple conditions such as symmetry, single copy, retrieval by keyword, and return string at the same time, and achieve a balance between computing efficiency and communication efficiency. Through cryptographic techniques such as homomorphic encryption, oblivious transfer (Oblivious Transfer, OT), and one-way trapdoor function (One-way Trapdoor Function), the above conditions can be met or partially met.

This specification provides an embodiment of a method for realizing private information retrieval.

In this embodiment, the server (Server) may encrypt the database in advance to obtain the query base, and send the query base to the client.

Generally, the server has a local database, which can be queried by the client. The local database on the server is, for example, as follows:

Table 1. Databases owned by the server

In the above example of Table 1, there are four fields including ID, Name, Age, and Native_place. For example, there are 10 records id_0, ... id_9, and each row is a record. Among them, id_0, ... id_9 is the identification of each row of records.

In order to allow the client to search without exposing the privacy of the server, the server can encrypt the database to obtain the query base. The encryption method can use RSA (a widely used asymmetric encryption algorithm, developed by Ronald Rivest (Ron Rivest), Adi Shamir (Adi Shamir) and Leonard Adleman (Leonard Adleman) in 1977 proposed together) or ECC (Elliptical Curve Cryptography, elliptic curve cryptography) encryption. Specifically, the server can use the RSA private key/ECC private key α to encrypt data, that is, use the RSA private key/ECC private key α to encrypt each field except the ID column (that is, the data in each cell) .

In the case of using the ECC encryption and decryption algorithm, specifically, the server can generate a secret value α and store it properly. The secret value α is also the ECC private key. In addition, the server can convert the value of the name field into a point on the elliptic curve through a hash function, which can be expressed as Hash(C) or H(C).

According to the operational properties of scalar multiplication on the elliptic curve, it is easy to calculate Q=kP for a point P on the elliptic curve and an integer k, and the obtained result Q is also a point on the elliptic curve; A point pair P, Q of , it is very difficult to find the value of k in Q=kP that makes the equation valid.

Here, it is easy to calculate α·H(C) according to the scalar multiplication operation on the elliptic curve, but it is difficult to calculate the value of α after knowing the result of α·H(C) and H(C). When it is difficult to obtain the value of α, knowing the result of α·H(C) is also difficult to obtain the value of H(C).

Furthermore, the database encrypted by the server using the secret value α is as follows:

Table 2. The query base encrypted by the server using the ECC private key

It should be noted that the above hash function can not only convert the original input into an output with a fixed length and format, but also convert the output into the x-axis coordinate of a point on the elliptic curve. For example, if an elliptic curve such as curve25519 is used, any 256bits data can be used as a legal x-axis coordinate on this elliptic curve. Correspondingly, sha256 or sha3-256 can be used, or 256 bits can be intercepted from the result of sha384, sha512 or sha3-384, sha3-512. More broadly speaking, any hash value (not limited to 256bits) can take the modulus of the order of the elliptic curve, and the product of the modulus result and the generator point (scalar multiplication) is a point on the elliptic curve.

Furthermore, the server can send the query base to the client that needs to retrieve it. In one way, the server can directly send the query base to the client, for example, directly to the client's device, or to the client's proxy server; in another way, the server can be in a uniform resource location system (Uniform ResourceLocator, URL) to publish the query base, and then the client can obtain the query base from the URL.

Correspondingly, the client can receive the query base and store the received query base locally.

Similarly, in the case of RSA, the server can generate a secret value α and store it properly, which is the RSA private key. In addition, the server can convert the value of the name field into a point on the elliptic curve through a hash function, which can be expressed as Hash(C) or H(C).

According to the nature of modular exponentiation, the secret value α is known, and for a large prime number q and base g, it is easy to calculate p=g ^α mod q; on the contrary, if p, q and base g are known, it is easy to solve p=g ^α mod q The value of α for which the equation holds is difficult. The base g is also called the original root.

Here, it is easy to calculate (H(C)) ^α mod q based on simulation operations, but it is difficult to deduce the value of α knowing the result of (H(C)) ^α mod q and H(C) and q. When it is difficult to obtain the value of α, knowing the result of (H(C)) ^α mod q is also difficult to obtain the value of H(C). In the following, an expression of the form (H(C)) ^α mod q will omit mod q, and be simply expressed as (H(C)) ^α .

Furthermore, the database encrypted by the server using the secret value α is as follows:

Table 3. The query base encrypted by the server using the RSA private key

Furthermore, the server can send the query base to the client that needs to retrieve it. Similarly, the server can directly send the query base to the client, such as directly to the client's device, or to the client's proxy server; ResourceLocator, URL), and then the client can obtain the query base from the URL.

Correspondingly, the client can receive the query base and store the received query base locally.

For example, as shown in Figure 1, the interaction process between the client and the server may include the following steps:

S110: The client sends the encrypted sensitive field to the server, and obtains the same sensitive field encrypted by the server through interaction with the server.

For example, the retrieval condition of the client is that the value of the Age field is 25, and 25 is a sensitive field, that is, the peer end is not expected to know. In order to prevent the server from knowing that the retrieval condition of the client is the value 25 of the Age field, the client can encrypt the value 25. For example, RSA/ECC private key encryption is used, and the encryption algorithm used by the client is the same as that used by the server to generate the query base.

Specifically, in the case of RSA private key encryption, the client itself generates the secret β and keeps it properly. Furthermore, the client can encrypt 25 with its own private key β. Specifically, it may be to encrypt 25 or a hash value of 25. Here we take the hash encryption of 25 as an example to illustrate. The situation of direct encryption of 25 is similar, and the client and server use the same hash algorithm. For example, the client uses the same large prime number q as the modulus as the server. The client can perform RSA encryption on the hash value of 25 using β to obtain (H(25)) ^β . Then the sensitive field sent by the client to the server may be (H(25)) ^β , where (H(25)) ^β represents the ciphertext of the value 25 of the sensitive field.

On the other hand, the client can also construct a search statement, encrypt the sensitive fields in the search statement to obtain the private field, replace the sensitive field with the private field, and send the replaced private search statement to the server.

For example, the query statement constructed by the client is select Name where Age=25.

In order to protect privacy, that is, the age=25 condition is what prevents the server from obtaining the query. For example, the privacy of 25 of them is protected, and the result is as follows:

select Name where Age＝?

in,? Indicates the replaced search statement.

Specifically, the client can encrypt 25 with an RSA private key. For example, the client can perform hash calculation on 25 using the same hash function as the server, and then use β to perform RSA encryption on the hash value of 25 to obtain (H(25)) ^β . The query statement sent by the client to the server is, for example, as follows:

select Name where Age＝(H(25)) ^β

As mentioned above, (H(25)) ^β is the ciphertext, that is, the content represented by "?" in the above search statement, and the server cannot know β and 25 in it after obtaining it.

In the case of ECC private key encryption, the client uses the same elliptic curve as the server, that is, has the same elliptic curve parameters and generators. The client itself generates the secret β and keeps it securely. Furthermore, the client can encrypt 25 with its own private key β. Specifically, the hash value of 25 may be encrypted, and the client and server use the same hash algorithm. For example, the client can use β to perform ECC encryption on the hash value of 25 to obtain β·H(25). Then the sensitive field sent by the client to the server may be β·H(25), where β·H(25) represents the ciphertext of the value 25 of the sensitive field.

On the other hand, the client can also construct a search statement, encrypt the sensitive fields in the search statement to obtain the private field, replace the sensitive field with the private field, and send the replaced private search statement to the server.

For example, the query statement constructed by the client is select Name where Age=25.

In order to protect privacy, that is, the age=25 condition is what prevents the server from obtaining the query. For example, the privacy of 25 of them is protected, and the result is as follows:

select Name where Age＝?

in,? Indicates the replaced search statement.

Specifically, the client can encrypt 25 with an ECC private key. For example, the client uses the same elliptic curve as the server, that is, has the same elliptic curve parameters and generators. The client can encrypt and replace the sensitive fields in the search statement with its own ECC private key, and send the replaced private search statement to the server. For example, the client itself generates the secret β and keeps it properly. In addition, the client can perform hash calculation on 25 using the same hash function as the server, and then use β to perform ECC encryption on the hash value of 25 to obtain β·H(25). The query statement sent by the client to the server is, for example, as follows:

select Name where Age＝β·H(25)

As mentioned above, β·H(25) is the ciphertext, that is, the content represented by "?" in the above search statement, and the server cannot know β and 25 in it after obtaining it.

The client obtains the same sensitive field encrypted by the server through interaction with the server, which may include that the server uses its own key to re-encrypt the sensitive field encrypted by the client and sends it to the client, and the client uses its own key to pair The sensitive fields encrypted twice are decrypted to obtain the sensitive fields encrypted by the server. The core of this content is to find an encryption algorithm that satisfies two consecutive encryption operations (two parties encrypt successively) and can exchange order for decryption. According to the cryptographic nature of ECC, the two parties agree to use the same elliptic curve, that is, have the same elliptic curve parameters and generators, each hold the private key α and β, and the encryption operation is scalar multiplication with α (or β), regardless of Whether it is first encrypted with α and then encrypted with β or encrypted with β first and then encrypted with α, it can be decrypted in the same or different order, that is, the encrypted results can be decrypted in different orders. Similarly, according to the cryptographic nature of RSA encryption, the two parties agree to use the same large prime number q and original root g, each holding private keys α and β, and the encryption operation is to use α (or β) to exponentiate and use q to take the modulus, Regardless of first encrypting with α and then encrypting with β or first encrypting with β and then encrypting with α, they can be decrypted in the same or different order, that is, the encrypted results can be decrypted in different orders. On the whole, the encryption/decryption performed by the client and the server on the same target adopts the encryption/decryption algorithm with interchangeable order.

Specifically, it may be that after the server receives the privacy search statement, it encrypts the private field again and returns it to the client, or it may be that after the server receives the sensitive field encrypted by the client itself from the client, the server encrypts the encrypted field. Sensitive fields of the server are encrypted again with the server's own key and returned to the client. Furthermore, the client uses its own key to decrypt the twice-encrypted sensitive field to obtain the sensitive field encrypted by the server.

For example, Case 1: The server can receive (H(25)) ^β sent by the client.

The server may re-encrypt the encrypted sensitive field (ie, the private field), and return the re-encrypted sensitive field to the client. Specifically, the server can re-encrypt the privacy field (H(25)) ^β with its own RSA private key α to obtain ((H(25)) ^β ) ^α .

For example, case 1': the server may receive the privacy search statement select Name whereAge=(H(25)) ^β sent by the client. In this way, the server can obtain the privacy field (H(25)) ^β in the privacy retrieval statement.

The server can re-encrypt the privacy field, and return the re-encrypted privacy field to the client.

Specifically, the server can re-encrypt the privacy field (H(25)) ^β with its own RSA private key α to obtain ((H(25)) ^β ) ^α . The specific process is similar to the above, and will not be repeated here.

For example, case 2: the server can receive the β·H(25) sent by the client.

The server can re-encrypt the privacy field, and return the re-encrypted privacy field to the client. Specifically, the server can re-encrypt the privacy field β·H(25) with its own ECC private key α to obtain α·β·H(25).

For example, case 2': the server may receive the privacy retrieval statement select Name whereAge=β·H(25) sent by the client. In this way, the server can obtain the privacy field β·H(25) in the privacy retrieval sentence.

The server can re-encrypt the privacy field, and return the re-encrypted privacy field to the client.

Specifically, the server can re-encrypt the privacy field β·H(25) with its own ECC private key α to obtain α·β·H(25). The specific process is similar to the above and will not be repeated here.

After the server uses its own key to re-encrypt the sensitive field (that is, the privacy field) encrypted by the client and sends it to the client, the client can use its own key to decrypt the twice-encrypted privacy field to obtain the encrypted data from the server. Sensitive fields.

对两次加密后的敏感字段解密，如下：

这样，客户端得到由服务端加密的同一敏感字段，即(H(25))^α。For example, corresponding to the above cases 1 and 1', the client receives the ((H(25)) ^β ) ^α sent by the server, and the existence property of the power operation is as follows: ((H(25)) ^β ) ^α = (H(25)) ^βα = (H(25)) ^αβ = ((H(25)) ^α ) ^β . Furthermore, the client can use the inverse of its own private key β

Decrypt the sensitive fields encrypted twice, as follows:

In this way, the client gets the same sensitive field encrypted by the server, namely (H(25)) ^α .

Corresponding to the above cases 2 and 2', the client receives the α·β·H(25) sent by the server, and the existence property of the scalar multiplication operation is as follows: α·β·H(25)=β·α·H(25 ). Furthermore, the client can use the inverse element β ^-1 of its own private key β to decrypt the sensitive fields encrypted twice, as follows: β ^-1 ·α·β·H(25)=β ^-1 ·β·α·H (25)=α·H(25). In this way, the client also gets the same sensitive field encrypted by the server, namely α·H(25).

It should be noted that in RSA, according to Euler's theorem, pk·sk=1mod(p-1)·(q-1), where p and q are two large prime numbers, so pk and sk are inverses of each other. Similarly, in ECC, pk=sk*G, G is a generator on the selected curve of ECC, so pk and sk are also mutually inverse elements.

S120: The client searches in the query base according to the sensitive field encrypted by the server, obtains an identifier of a matching record, and returns the identifier to the server.

After S110 is executed, the client can obtain the same sensitive field encrypted by the server.

Clients can query the query base based on this sensitive field encrypted by the server. For example, the client decrypts and obtains the privacy field α·H(25) or (H(25)) ^α encrypted by the server, so that the client queries in the query base based on the privacy field, for example, in Table 2 or Table 3 Query in , it can be obtained that the record containing the privacy field in Age is the record with ID=d_1, and ID is the identifier of this record. In this way, the client queries the query base based on the private field encrypted by the server, and after matching records, the client can locate and obtain the identification of the matching records.

The client returns the identifier of the matching record to the server, which may include two situations.

One is that in S110, the client constructs a search statement, encrypts sensitive fields in the search statement to obtain a private field, replaces the sensitive field with the private field, and sends the replaced private search statement to the server. In this case, the client can directly return the identifier of the matching record to the server.

The other is in S110, the client sends the value of the sensitive field encrypted by itself to the server. In this case, in S120, the client may construct a search statement, for example, the search statement is:

select Name where ID=id_1

In this way, in S120, the client can send the above constructed search formula to the server, the search formula includes the identification of the matching record, and indicates that the field of interest is Name, that is, the name of the field immediately following select.

In other words, in the two steps of S110 and S120, one of the steps may choose to send a search formula, and the search formula includes the field of interest.

S130: The server returns the value of the field of interest in the record corresponding to the identifier in the database to the client.

Still according to the above example, after receiving the identifier sent by the client, the server can search the database for the record corresponding to the identifier, and retrieve the corresponding value in the found record according to the field of interest in S110 or S120, and Return the retrieved value of the field of interest to the client. For example, return Name=B in the record corresponding to id_1, that is, return B to the client.

In the above embodiment, by pre-configuring the query base in the form of the client, the client can locate the identifier of the field to be queried in the query base by interacting with the server and the query base without exposing the plaintext of the database, and further according to the identifier Initiate a query to the server to obtain the value identifying the field of interest in the corresponding record. Compared with the traditional multi-copy PIR, it obviously does not need the premise that multiple copy databases cannot collude, and the practicability is better. Compared with the situation in which only bits can be retrieved in the traditional single-copy PIR, this embodiment does not need to pay attention to the specific position (bit position) of the keyword to be retrieved in the database, can realize the query of the character string, and can support the structure Structured Query Language (SQL). In this embodiment, the database remains on the server, and at the same time, the query base encrypted by the database is configured to the client, so that the client can locate the data based on the query base to obtain the identification of the record, and the encryption feature of the query base enables the client to The client will not obtain the contents of the database, which ensures the privacy protection of the database by the server. On the whole, the form of database and query base in this embodiment can be called "asymmetric double copy" when a server configures a database and a client configures a query base. The case can be called "asymmetric multi-copy".

In the above embodiment, the client can initiate a query on the field of interest through the SQL query statement, for example, the Name field to be queried in the above select Name.... This somewhat exposes fields of interest to the client. In another way, you can query qualified records, that is, the entire row of data that meets the conditions, which can protect the privacy of the client, but requires the server to return the entire record, which exposes the entire row of data on the server to a certain extent. For example, in S110/S120, a search statement such as "select*where Age=?" or "select*where ID=id_1" is used. In this way, the result returned by the server can be the record of id_1, for example as follows:

id_1B 25shanghai

In addition, in order to ensure the security of the transmission process, the server may encrypt and return the value of the corresponding record in the database/the value of the field of interest in the corresponding record to the client. For example, the server can use the symmetric key negotiated with the client to encrypt the value of the field of interest in the corresponding record/record in the database and return it to the client, or use the asymmetric key of the client to The public key in the key encrypts the corresponding record in the database/the value of the field of interest in the corresponding record and returns it to the client, so that the client can decrypt it with its own private key, and use a digital envelope, etc.

In the above S120, the client directly returns the matched ID to the server. Although the record corresponding to the ID or the field of interest in the record can be obtained from the server, such as S130, this will expose the privacy of the client to a certain extent. , which will let the server know that the identifier that the client wants to query is id_1. In order to protect the privacy of the client, it can be implemented in the following embodiments:

S210: The client sends the encrypted sensitive field to the server, and obtains the same sensitive field encrypted by the server through interaction with the server.

For example, the retrieval condition of the client is that the value of the Age field is 25, and 25 is a sensitive field, that is, the peer end is not expected to know. In order to prevent the server from knowing that the retrieval condition of the client is the value 25 of the Age field, the client can encrypt the value 25. For example, RSA/ECC private key encryption is used, and the encryption algorithm used by the client is the same as that used by the server to generate the query base.

Specifically, in the case of RSA private key encryption, the client itself generates the secret β and keeps it properly. Furthermore, the client can encrypt 25 with its own private key β. Specifically, it may be to encrypt 25 or a hash value of 25. Here we take the hash encryption of 25 as an example to illustrate. The situation of direct encryption of 25 is similar, and the client and server use the same hash algorithm. For example, the client uses the same large prime number q as the modulus as the server. The client can perform RSA encryption on the hash value of 25 using β to obtain (H(25)) ^β . Then the sensitive field sent by the client to the server may be (H(25)) ^β , where (H(25)) ^β represents the ciphertext of the value 25 of the sensitive field.

In the case of ECC private key encryption, the client uses the same elliptic curve as the server, that is, has the same elliptic curve parameters and generators. The client itself generates the secret β and keeps it securely. Furthermore, the client can encrypt 25 with its own private key β. Specifically, the hash value of 25 may be encrypted, and the client and server use the same hash algorithm. For example, the client can use β to perform ECC encryption on the hash value of 25 to obtain β·H(25). Then the sensitive field sent by the client to the server may be β·H(25), where β·H(25) represents the ciphertext of the value 25 of the sensitive field.

The client obtains the same sensitive field encrypted by the server through interaction with the server, which may include that the server uses its own key to re-encrypt the sensitive field encrypted by the client and sends it to the client, and the client uses its own key to pair The sensitive fields encrypted twice are decrypted to obtain the sensitive fields encrypted by the server. The core of this content is to find an encryption algorithm that satisfies two consecutive encryption operations (two parties encrypt successively) and can exchange order for decryption. According to the cryptographic nature of ECC, the two parties agree to use the same elliptic curve, that is, have the same elliptic curve parameters and generators, each hold the private key α and β, and the encryption operation is scalar multiplication with α (or β), regardless of Whether it is first encrypted with α and then encrypted with β or encrypted with β first and then encrypted with α, it can be decrypted in the same or different order, that is, the encrypted results can be decrypted in different orders. Similarly, according to the cryptographic nature of RSA encryption, the two parties agree to use the same large prime number q and original root g, each holding private keys α and β, and the encryption operation is to use α (or β) to exponentiate and use q to take the modulus, Regardless of first encrypting with α and then encrypting with β or first encrypting with β and then encrypting with α, they can be decrypted in the same or different order, that is, the encrypted results can be decrypted in different orders. On the whole, the encryption/decryption performed by the client and the server on the same target adopts the encryption/decryption algorithm with interchangeable order.

Specifically, after the server receives the encrypted sensitive field sent by the client, the server encrypts the encrypted sensitive field again with the server's own key and returns it to the client. Furthermore, the client uses its own key to decrypt the twice-encrypted sensitive field to obtain the sensitive field encrypted by the server.

For example, Case 1: The server can receive (H(25)) ^β sent by the client.

The server may re-encrypt the encrypted sensitive field (ie, the private field), and return the re-encrypted sensitive field to the client. Specifically, the server can re-encrypt the privacy field (H(25)) ^β with its own RSA private key α to obtain ((H(25)) ^β ) ^α .

For example, case 2: the server can receive the β·H(25) sent by the client.

The server can re-encrypt the privacy field, and return the re-encrypted privacy field to the client. Specifically, the server can re-encrypt the privacy field β·H(25) with its own ECC private key α to obtain α·β·H(25).

After the server uses its own key to re-encrypt the sensitive field (that is, the privacy field) encrypted by the client and sends it to the client, the client can use its own key to decrypt the twice-encrypted privacy field to obtain the encrypted data from the server. Sensitive fields.

对两次加密后的敏感字段解密，如下：

这样，客户端得到由服务端加密的同一敏感字段，即(H(25))^α。For example, corresponding to the above case 1, the client receives ((H(25)) ^β ) ^α sent by the server, and the existence property of the power operation is as follows: ((H(25)) ^β ) ^α ＝(H( 25)) ^βα = (H(25)) ^αβ = ((H(25)) ^α ) ^β . Furthermore, the client can use the inverse of its own private key β

Decrypt the sensitive fields encrypted twice, as follows:

In this way, the client gets the same sensitive field encrypted by the server, namely (H(25)) ^α .

Corresponding to the above case 2, the client receives the α·β·H(25) sent by the server, and the existence property of the scalar multiplication operation is as follows: α·β·H(25)=β·α·H(25). Furthermore, the client can use the inverse element β ^-1 of its own private key β to decrypt the sensitive fields encrypted twice, as follows: β ^-1 ·α·β·H(25)=β ^-1 ·β·α·H (25)=α·H(25). In this way, the client also gets the same sensitive field encrypted by the server, namely α·H(25).

It should be noted that in RSA, according to Euler's theorem, pk·sk=1mod(p-1)·(q-1), where p and q are two large prime numbers, so pk and sk are inverses of each other. Similarly, in ECC, pk=sk·G, G is a generating element on the selected curve of ECC, so pk and sk are also mutually inverse elements.

S220: The client searches in the query base according to the sensitive field encrypted by the server, and obtains the identifier of the matching record.

After S210 is executed, the client can obtain the same sensitive field encrypted by the server.

Clients can query the query base based on this sensitive field encrypted by the server. For example, the client decrypts and obtains the privacy field α·H(25) or (H(25)) ^α encrypted by the server, so that the client queries in the query base based on the privacy field, for example, in Table 2 or Table 3 Query in , it can be obtained that the record containing the privacy field in Age is the record with ID=d_1, and ID is the identifier of this record. In this way, the client queries the query base based on the private field encrypted by the server, and after matching records, the client can locate and obtain the identification of the matching records.

S230: The server returns, to the client, the value of the field of interest in the record corresponding to the identifier set of a predetermined size including the matching identifier in the database by means of inadvertent transmission.

In S220, the client does not return the matching ID to the server, so that the server cannot know which record or records the client wants to find; the sensitive field encrypted by the client sent by the client in S210 This makes it impossible for the server to know which record or records will be hit by the sensitive fields searched by the client, and only the client knows. In this way, the privacy of the client is protected. However, the retrieval still needs to be completed in the end, which requires the server to return the records that the client wants to query to the client.

Here, the server can use the oblivious transmission mode.

Oblivious Transfer (OT) can be implemented based on RSA, ECC, etc., and can realize multiple OTs such as 2 to 1, n to 1, m to 1, m to k (k<m<n). Take 2 choose 1OT as an example to illustrate the principle. The sender has two secrets, namely m1 and m2, and needs to send two secrets to the receiver. The receiver can only choose to decrypt one of them and cannot know the other. At the same time, send The recipient also has no way of knowing which one the recipient has chosen. Taking RSA as an example, a simple implementation process of choosing 1 from 2 is as follows:

First, the sender generates two different pairs of public and private keys, and discloses the two public keys, which are recorded as public key 1 and public key 2 respectively. Suppose the receiver wants to know m1, but does not want the sender to know that he wants m1. The receiver generates a random number r, encrypts r with the public key 1, and sends it to the sender. The sender uses his own two private keys to decrypt the encrypted r, decrypts with private key 1 to obtain r1, and decrypts with private key 2 to obtain r2. Obviously, only r1 is equal to r, and r2 is a series of meaningless numbers (also the result of decryption). But the sender does not know which public key the receiver uses for encryption, so the sender does not know which of the r1 and r2 calculated by himself is the real r. After receiving m1 and m2, the sender uses r1 to symmetric encrypt m1, uses r2 to symmetric encrypt m2, and sends the two symmetric encryption results to the receiver. The receiver has r=r1 locally, so the receiver uses r to symmetrically decrypt the two sent results to get m1, but cannot decrypt to get m2, because the receiver has r≠r2, and the receiver also It is impossible to decrypt with the correct symmetric key to obtain the value of m2. In this process, the sender does not know which of m1 and m2 is calculated by the receiver.

With 2 to 1 as the basis, 2 public-private key pairs can be expanded into n public-private key pairs, which becomes an OT of n to 1. The core of choosing 1 from n is that the server uses n different keys to encrypt the n records in the data table/values of the fields of interest in the corresponding records to obtain n encryption results, and send the n encryption results to the client end; the client uses the key corresponding to the matching identifier to decrypt one encrypted result corresponding to the matching identifier among the n encrypted results sent by the server.

In combination with the above-mentioned embodiments of this specification, it is assumed that there are a total of n records in the data table of the server, so that the query base of the client also has n encrypted records correspondingly. For convenience, the IDs of the data records are identified as id_0, id_1, id_2, . . . id_n-1 in sequence. A simple implementation process is as follows:

S231: The server pre-generates n pairs of different public-private key pairs and discloses the public keys.

Here n is equal to the number of records in the database.

The server generates n pairs of different public-private key pairs (pk-sk; pk is a public key, indicating a public key; sk is a secretkey, indicating a private key; the public key can be made public, and the private key needs to be kept secret), for example, pk ₀ -sk ₀ , pk ₁ -sk ₁ , pk ₂ -sk ₂ , ..., pk _n-1 -sk _n-1 , and publicize these n public keys, that is, publicize pk ₀ , pk ₁ , pk ₂ , ... , pk _n-1 . After the server discloses the n ordered public keys, the client can obtain the n public keys.

S232: The client generates a random number r, encrypts r with the public key corresponding to the desired ID, and sends it to the server.

Here it is assumed that the client wants to obtain the record of id_1, and at the same time does not want the server to know that the record the client wants to obtain is the record of id_1. In this way, the client can use pk ₁ to encrypt r and send it to the server. The order mentioned above mainly means that there is a corresponding relationship between the ID and the public key, and such a corresponding relationship can be known by the client. For example, in the above example, the client wants to obtain the record of id_1 but does not want the server to know that the record that the client wants to obtain is the record of id_1. The client can use the pk ₁ corresponding to id_1 to encrypt r and send it to Server; similarly, the client wants to obtain the record of id_t but at the same time does not want the server to know that the record that the client wants to obtain is the record of id_t. The client can use the pk _t corresponding to id_t to encrypt r and send it to the server.

S233: After receiving the encrypted r, the server uses n private keys to decrypt it respectively.

The server uses sk ₀ , sk ₁ , sk ₂ , ..., sk _n-1 to decrypt the random number r encrypted by pk ₁ respectively. For example, the server decrypts with sk ₀ to obtain r0, decrypts with sk ₁ to obtain r1, ..., and decrypts with sk _n-1 to obtain r(n-1).

Obviously _, only r1 is equal to r, because only those decrypted with sk ₁ are encrypted with the corresponding pk ₁ ; and decrypted with sk ₀ , sk ₂ , ..., sk _{n-1 that do not correspond to pk 1} to get The results of r0, r2, ..., r(n-1) will not be the same as r. Through decryption, the server only gets the decryption result in the same form, and does not know what the real r is, nor does it know which public key the client uses for encryption. In other words, the server does not know which public key the client uses to encrypt r, so the server does not know which of the n results r0, r1, r2, ..., r(n-1) obtained by decryption is the real r.

S234: The server performs symmetric encryption on each record in the database according to the serial number using the decryption result corresponding to the serial number, and sends the symmetrically encrypted result to the client.

For example, the server uses r0 for symmetric encryption of the id_0 record, uses r1 for symmetric encryption of the id_1 record, ..., uses r(n-1) for symmetric encryption of the id_n-1 record, and The n symmetric encryption results are sent to the client.

S235: The client uses the random number r to perform symmetric decryption on the encrypted result corresponding to the desired ID in the symmetric encrypted result to obtain a search result.

The client uses the random number r to symmetrically decrypt the encrypted result corresponding to the desired ID in the symmetric encrypted result. Specifically, for example, what the client expects to obtain in S232 above is the value of the field of interest in the record/record corresponding to id_1, then the client uses the corresponding public key pk ₁ to encrypt the random number r; in S233 , the server uses the corresponding private key sk ₁ to decrypt the decryption result, and the obtained r1=r, and uses sk ₀ , sk ₂ , ..., sk _n-1 that do not correspond to pk ₁ to decrypt the results r0, r2 , ..., r(n-1) will not be the same as r; in S234, the server uses r0, r1, r2, ..., r(n-1) to match the corresponding id_0, id_1, ... ., id_n-1 these records/values of interest fields in the records are symmetrically encrypted, and the n symmetric encryption results are sent to the client; in S235, the client uses the random number r to encrypt the n symmetric The encrypted result is symmetrically decrypted. Among them, among the n symmetric decryption results, only the encrypted result of id_1 is encrypted symmetrically with r, so here only the encrypted result of id_1 is decrypted with r to obtain the correct value. Therefore, the client can obtain a correct retrieval result, that is, obtain the corresponding record/the value of the field of interest in the corresponding record.

Of course, in order to reduce the amount of calculation, the client may only use the random number r to perform symmetric decryption on the encryption result corresponding to the desired ID among the n symmetric encryption results, that is, the client only uses r to decrypt the encryption result of id_1 Decrypt to obtain the corresponding record of id_1/the value of the field of interest in the corresponding record, without using r to perform symmetric decryption on the symmetric encryption results of id_0, id_2, ..., id_n-1, because the client can know these encryption results It is not symmetric encryption using r, even if r is used for symmetric decryption, the correct result cannot be solved.

For a clearer presentation, the client uses the random number r to perform symmetric decryption on the n symmetric encryption results, as follows:

In S234, the server uses r0, r1, r2, ..., r(n-1) to symmetrize the values of the fields of interest in the records/records corresponding to id_0, id_1, ..., id_n-1 encryption:

Enc(id_0, r0), where r0≠r;

Enc(id_1, r1), where r1 = r;

Enc(id_2, r2), where r2≠r;

...

Enc(id_n-1, r(n-1)), where r(n-1)≠r;

The above Enc means encryption (Encrypt). The id_0, id_1, id_2, ..., id_n-1 of the former part in the Enc() brackets represent the value of the field of interest in n records/n records, and the r0, id_n-1 of the latter part r1, r2, . . . , r(n-1) represent encryption keys.

In S235, the client uses the random number r to symmetrically decrypt the encryption result in S234. Specifically, the client uses the random number r to symmetrically decrypt the following content respectively:

Dec(Enc(id_0, r0), r), where r0≠r;

Dec(Enc(id_1, r1), r), where r1=r;

Dec(Enc(id_2, r2), r), where r2≠r;

...

Dec(Enc(id_n-1, r(n-1), r), where r(n-1)≠r;

The above-mentioned Dec means decryption (Decrypt), the first part in Dec() means the decryption object, which is the above encryption result, and the latter part in Dec() means the key used for decryption.

It can be seen that the client can only decrypt the record with id_1, but cannot infer other records. This is because the server only uses random number r for symmetric encryption on the record of id_1, but uses non-random number r for symmetric encryption on other IDs, and the client cannot obtain r0, r2,...,r(n-1).

It should be noted that S231 may be after S230 or before S230, which is not limited here.

The above is that when the number of matching records retrieved by the client in the query base is 1, it selects 1 from n and inadvertently transmits all the corresponding records/corresponding records of the identification including the matching identification in the database The value of the field of interest is transmitted to the client.

In the above embodiment, the server does not know which ID or IDs the client is querying, but encrypts all the records in the database and returns them to the client, which protects the privacy of the client. However, in S233, the server uses n private keys to decrypt the received encrypted r respectively, so that a large number of asymmetric decryption calculations need to consume a large amount of CPU and memory resources. Moreover, the transmission of n symmetrically encrypted results in S234 will also occupy a large amount of bandwidth. Especially when the number of n is relatively large, the calculation amount of the server is relatively large, and the bandwidth occupation is also large.

(C表示组合公式，n里任选k个构成的组合的数量)。接下来，采用

选1的不经意传输方式将所述数据库中包含所述匹配标识在内的所有所述标识对应记录/对应记录中感兴趣字段的值传输至所述客户端。

选1的不经意传输方式，实现过程类似于上述n选1不经意传输的实现过程。即所述服务端用

个不同密钥分别加密所述数据表中的每k个记录/对应记录中感兴趣字段的值得到

个加密结果，并发送该

个加密结果至客户端；所述客户端采用匹配标识对应的密钥解密所述服务端发送的

个加密结果中匹配标识对应的1个加密结果。具体实现类似上述S231-S235的过程，这里不再赘述。In addition, it is possible that the matching result is greater than 1, for example, k items (k>1), which can be realized by selecting n from k and inadvertently transmitting. As for choosing k from n, one implementation scheme is to form a set of each k of n records, and each set corresponds to a public-private key pair, so that there will be a total of

(C represents the combination formula, the number of combinations composed of k optional in n). Next, use

In the inadvertent transmission mode of selecting 1, all records corresponding to the identifier/values of fields of interest in the corresponding records including the matching identifier in the database are transmitted to the client.

The realization process of the oblivious transmission mode of choosing 1 is similar to the realization process of the above-mentioned n choosing 1 oblivious transmission. That is, the server uses

A different key encrypts the value of the field of interest in each k record/corresponding record in the data table respectively to obtain

encrypted results, and send the

encrypted results to the client; the client uses the key corresponding to the matching identifier to decrypt the message sent by the server

One encrypted result corresponding to the matching identifier among the encrypted results. The specific implementation of the process similar to the above S231-S235 will not be repeated here.

It should be noted that the above r can also be the public key in the asymmetric key, so that after receiving the result encrypted by r, the client can use its own private key to decrypt it to obtain the result. That is, in S234 and S235, the server asymmetrically encrypts the id_0 record using r0, uses r1 to asymmetrically encrypt the id_1 record, ..., uses r(n-1) for the id_n-1 record Perform asymmetric encryption and send the n encrypted results to the client. After receiving the encrypted results, the client can use its own private key to asymmetrically decrypt the encrypted results corresponding to the desired ID to obtain the results. The following is also similar and will not be repeated.

Based on this, this specification provides the following implementation mode with the addition of constructing confusion sets:

S310: The client sends the encrypted sensitive field to the server, and obtains the same sensitive field encrypted by the server through interaction with the server.

For example, the retrieval condition of the client is that the value of the Age field is 25, and 25 is a sensitive field, that is, the peer end is not expected to know. In order to prevent the server from knowing that the retrieval condition of the client is the value 25 of the Age field, the client can encrypt the value 25. For example, RSA/ECC private key encryption is used, and the encryption algorithm used by the client is the same as that used by the server to generate the query base.

Specifically, in the case of RSA private key encryption, the client itself generates the secret β and keeps it properly. Furthermore, the client can encrypt 25 with its own private key β. Specifically, it may be to encrypt 25 or a hash value of 25. Here we take the hash encryption of 25 as an example to illustrate. The situation of direct encryption of 25 is similar, and the client and server use the same hash algorithm. For example, the client uses the same large prime number q as the modulus as the server. The client can perform RSA encryption on the hash value of 25 using β to obtain (H(25)) ^β . Then the sensitive field sent by the client to the server may be (H(25)) ^β , where (H(25)) ^β represents the ciphertext of the value 25 of the sensitive field.

In the case of ECC private key encryption, the client uses the same elliptic curve as the server, that is, has the same elliptic curve parameters and generators. The client itself generates the secret β and keeps it securely. Furthermore, the client can encrypt 25 with its own private key β. Specifically, the hash value of 25 may be encrypted, and the client and server use the same hash algorithm. For example, the client can use β to perform ECC encryption on the hash value of 25 to obtain β·H(25). Then the sensitive field sent by the client to the server may be β·H(25), where β·H(25) represents the ciphertext of the value 25 of the sensitive field.

The client obtains the same sensitive field encrypted by the server through interaction with the server, which may include that the server uses its own key to re-encrypt the sensitive field encrypted by the client and sends it to the client, and the client uses its own key to pair The sensitive fields encrypted twice are decrypted to obtain the sensitive fields encrypted by the server. The core of this content is to find an encryption algorithm that satisfies two consecutive encryption operations (two parties encrypt successively) and can exchange order for decryption. According to the cryptographic nature of ECC, the two parties agree to use the same elliptic curve, that is, have the same elliptic curve parameters and generators, each hold the private key α and β, and the encryption operation is scalar multiplication with α (or β), regardless of Whether it is first encrypted with α and then encrypted with β or encrypted with β first and then encrypted with α, it can be decrypted in the same or different order, that is, the encrypted results can be decrypted in different orders. Similarly, according to the cryptographic nature of RSA encryption, the two parties agree to use the same large prime number q and original root g, each holding private keys α and β, and the encryption operation is to use α (or β) to exponentiate and use q to take the modulus, Regardless of first encrypting with α and then encrypting with β or first encrypting with β and then encrypting with α, they can be decrypted in the same or different order, that is, the encrypted results can be decrypted in different orders. On the whole, the encryption/decryption performed by the client and the server on the same target adopts the encryption/decryption algorithm with interchangeable order.

Specifically, after the server receives the encrypted sensitive field sent by the client, the server encrypts the encrypted sensitive field again with the server's own key and returns it to the client. Furthermore, the client uses its own key to decrypt the twice-encrypted sensitive field to obtain the sensitive field encrypted by the server.

For example, Case 1: The server can receive (H(25)) ^β sent by the client.

The server may re-encrypt the encrypted sensitive field (ie, the private field), and return the re-encrypted sensitive field to the client. Specifically, the server can re-encrypt the privacy field (H(25)) ^β with its own RSA private key α to obtain ((H(25)) ^β ) ^α .

For example, case 2: the server can receive the β·H(25) sent by the client.

The server can re-encrypt the privacy field, and return the re-encrypted privacy field to the client. Specifically, the server can re-encrypt the privacy field β·H(25) with its own ECC private key α to obtain α·β·H(25).

After the server uses its own key to re-encrypt the sensitive field (that is, the privacy field) encrypted by the client and sends it to the client, the client can use its own key to decrypt the twice-encrypted privacy field to obtain the encrypted data from the server. Sensitive fields.

对两次加密后的敏感字段解密，如下：

这样，客户端得到由服务端加密的同一敏感字段，即(H(25))^α。For example, corresponding to the above case 1, the client receives ((H(25)) ^β ) ^α sent by the server, and the existence property of the power operation is as follows: ((H(25)) ^β ) ^α ＝(H( 25)) ^βα = (H(25)) ^αβ = ((H(25)) ^α ) ^β . Furthermore, the client can use the inverse of its own private key β

Decrypt the sensitive fields encrypted twice, as follows:

In this way, the client gets the same sensitive field encrypted by the server, namely (H(25)) ^α .

Corresponding to the above case 2, the client receives the α·β·H(25) sent by the server, and the existence property of the scalar multiplication operation is as follows: α·β·H(25)=β·α·H(25). Furthermore, the client can use the inverse element β ^-1 of its own private key β to decrypt the sensitive fields encrypted twice, as follows: β ^-1 ·α·β·H(25)=β ^-1 ·β·α·H (25)=α·H(25). In this way, the client also gets the same sensitive field encrypted by the server, namely α·H(25).

It should be noted that in RSA, according to Euler's theorem, pk·sk=1mod(p-1)·(q-1), where p and q are two large prime numbers, so pk and sk are inverses of each other. Similarly, in ECC, pk=sk·G, G is a generating element on the selected curve of ECC, so pk and sk are also mutually inverse elements.

S320: The client searches in the query base according to the sensitive field encrypted by the server, and obtains an identifier of a matching record.

After S310 is executed, the client can obtain the same sensitive field encrypted by the server.

Clients can query the query base based on this sensitive field encrypted by the server. For example, the client decrypts and obtains the privacy field α·H(25) or (H(25)) ^α encrypted by the server, so that the client queries in the query base based on the privacy field, for example, in Table 2 or Table 3 Query in , it can be obtained that the record containing the privacy field in Age is the record with ID=d_1, and ID is the identifier of this record. In this way, the client queries the query base based on the private field encrypted by the server, and after matching records, the client can locate and obtain the identification of the matching records.

S330: The server returns, to the client, the value of the field of interest in the record corresponding to the identifier set of a predetermined size including the matching identifier in the database by means of inadvertent transmission.

The encrypted sensitive field sent by the client in S310 makes it impossible for the server to know which record the sensitive field searched by the client will hit, and only the client knows. In this way, the privacy of the client is protected. However, the retrieval still needs to be completed in the end, which requires the server to return the records that the client wants to query to the client.

The above-mentioned embodiment corresponding to FIG. 2 provides an implementation manner of choosing 1 from n for oblivious transmission. Here, the oblivious transmission of selecting 1 from m may be used, where m<n. In S320, the client can also not return the matched ID to the server separately, but mix the matched ID with other forged IDs to form a confusion set, and send the confusion set to the server, thus The server cannot know exactly which record in the confusion set the client wants to find, and it needs to ensure that the client can only get the record it wants to find, but not other records. In S320, the confusion set sent by the client may be sent together with a search statement, for example, select Name where ID=confusion set. Alternatively, the confusion set can also be sent in the following S332, which is not limited here.

In combination with the above-mentioned embodiments of this specification, it is assumed that there are a total of n records in the data table of the server, so that the query base of the client also has n encrypted records correspondingly. For convenience, the IDs of the data records are identified as id_0, id_1, id_2, . . . id_n-1 in sequence. A simple implementation process is as follows:

S331: The server pre-generates n pairs of different public-private key pairs and discloses the public keys.

The server generates n pairs of different public-private key pairs (pk-sk; pk is a public key, indicating a public key; sk is a secretkey, indicating a private key), for example, pk ₀ -sk ₀ , pk ₁ -sk ₁ , pk ₂ -sk ₂ , ..., pk _n-1 -sk _n-1 , and publicize these n public keys, that is, publicize pk ₀ , pk ₁ , pk ₂ , ..., pk _n-1 . After the server discloses the n ordered public keys, the client can obtain the n public keys.

S332: The client generates a confusion set of size m including the desired ID, generates a random number r, encrypts r with the public key corresponding to the desired ID, and sends it to the server together with the confusion set.

Here, it is assumed that the client wants to obtain the record of id_1, and at the same time does not want the server to know that the record that the client wants to obtain is the record of id_1, so it generates a confusion set of m size. When m=4, the confusion set is, for example: { id_1, id_2, id_3, id_4}.

These 4 IDs have the following corresponding relationship with the public key pair, for example:

pk ₁ , id_1

_pk2 , id_2

pk ₃ , id_3

pk ₄ , id_4

The client can use pk ₁ to encrypt r and send it to the server together with the confusion set. For example:

In addition, the client can send the confusion set together with the retrieval statement to the server. In this way, the client can use pk ₁ to encrypt r and send it together with the retrieval statement containing the confusion set, for example:

select Name where ID={id_1,id_2,id_3,id_4}|Enc(r,pk ₁ )

Among them, "|" is used to separate the previous search statement from the encrypted random number, the same below.

S333: After receiving the confusion set and the encrypted r, the server uses the corresponding m private keys to decrypt the encrypted r respectively.

The server uses sk ₁ , sk ₂ , sk ₃ , and sk ₄ to decrypt the random number r encrypted by pk ₁ respectively. For example, the server decrypts with sk ₁ to obtain r1, decrypts with sk ₂ to obtain r2, decrypts with sk ₃ to obtain r3, and decrypts with sk ₄ to obtain r4.

_Obviously , _only r1 is equal to r, because only those decrypted with sk ₁ are _encrypted with the corresponding pk ₁ ; and the results r2, _r3 , Neither r4 will be the same as r. Through decryption, the server only gets the decryption result in the same form, and does not know what the real r is, nor does it know which public key the client uses for encryption. In other words, the server does not know which public key the client uses to encrypt r, so the server does not know which of the four decrypted results r1, r2, r3, and r4 is the real r.

In addition, after the server receives the confusion set {id_1, id_2, id_3, id_4}, it can know from the confusion set that the data the client wants to obtain is one of the 4 IDs in the confusion set, but it is not sure which one it is , thereby protecting the privacy of the client.

S334: The server performs symmetric encryption on the records specified in the confusion set using the decryption result of the corresponding serial number, and sends the symmetric encrypted result to the client.

For example, the server encrypts the record id_1 using r1 for symmetric encryption, the record id_2 uses r2 for symmetric encryption, the record id_3 uses r3 for symmetric encryption, the record id_4 uses r4 for symmetric encryption, and These 4 symmetric encrypted results are sent to the client.

S335: The client uses the random number r to perform symmetric decryption on the encrypted result corresponding to the desired ID in the symmetric encrypted result to obtain a search result.

The client uses the random number r to symmetrically decrypt the encrypted result corresponding to the desired ID in the symmetric encrypted result. Specifically, for example, what the client expects to obtain in S332 above is the value of the field of interest in the record/record corresponding to id_1, then the client uses the corresponding public key pk ₁ to encrypt the random number r; in S333 , the server uses the corresponding private key sk ₁ to decrypt the decryption result, and the obtained r1=r, and the results r2, r3, and r4 obtained by decrypting with sk ₂ , sk ₃ , and sk ₄ that do not correspond to pk ₁ will not be consistent with r is the same; in S334, the server uses r1, r2, r3, and r4 to symmetrically encrypt the values of the fields of interest in the corresponding records/records of id_1, id_2, id_3, and id_4, and send the symmetric encryption result to Client; In S335, the client uses the random number r to symmetrically decrypt the four symmetric encryption results. Among them, among the four symmetric decryption results, only the encrypted result of id_1 is symmetrically encrypted with r, so here only the encrypted result of id_1 is decrypted with r to get the correct value. Therefore, the client can obtain a correct retrieval result, that is, obtain the corresponding record/the value of the field of interest in the corresponding record.

Of course, in order to reduce the amount of calculation, the client can only use the random number r to perform symmetric decryption on the encryption result corresponding to the expected ID among the four symmetric encryption results, that is, the client only uses r to decrypt the encryption result of id_1 Decrypt to obtain the corresponding record of id_1/the value of the field of interest in the corresponding record, without using r to perform symmetric decryption on the symmetric encryption results of id_2, id_3, id_4, because the client can know that these encryption results are not symmetric using r Encryption, even if r is used for symmetric decryption, the correct result cannot be solved.

The foregoing S331 to S335 are only exemplary implementation manners. In another implementation, the construction and transmission of the confusion set can be decoupled from the execution of the OT protocol, and the key can be transmitted using the OT protocol. Specifically, on the one hand, the client can send the m-size confusion set to the server. Of course, the client knows which number in the m-size confusion set is the identity of the result it really wants to obtain. On the other hand, the server can Generate m symmetric keys, and through the OT of selecting 1 from m, the client can obtain one of the specified symmetric keys, that is, the client obtains the symmetric key corresponding to the identity that the client really wants to obtain. In this way, the server can encrypt the records corresponding to the m identifiers in the client confusion set with the corresponding symmetric keys and send them to the client, so that the client can decrypt the results that the client really wants to obtain with the correct symmetric key, thus obtaining result. Among them, the server can pre-generate m symmetric keys, so that the key preparation can be completed in batches before OT interaction without taking up the execution time of the OT protocol.

The above is that when the number of matching records retrieved by the client in the query base is 1, the server selects 1 from m and inadvertently transmits, and the server identifies the corresponding records/the values of the fields of interest in the corresponding records specified in the confusion set transmitted to the client. In addition, if the possible matching results are greater than 1, for example k (k>1), it can be realized by selecting k from m and inadvertently transmitting. The core of m choosing k inadvertent transmission is that the client constructs m-sized confusion sets and sends them to the server, 1<m<n, one of the m confusion sets contains the identifiers of the matching k records, for example m = 4, k = 2, the matching identifiers are id_1 and id_3, then the constructed confusion set is, for example, {{id_1, id_3}, {id_2 and id_4}, {id_3 and id_4}, {id_2}}, obviously the first one In order to match the sub-set formed by the identity; furthermore, the server generates m symmetric keys, and the client obtains the symmetric key specified by it through the OT protocol where m selects 1; the server uses m different symmetric keys to encrypt all Obtain m subsets of encrypted results from the m subsets in the above obfuscation set, and send the m subsets of encrypted results to the client; the client uses the obtained symmetric key to decrypt the subset composed of k matching identities to obtain the correct The decryption result. The specific implementation is similar to the above-mentioned process of decoupling the construction and transmission of the confusion set from the execution of the OT protocol, and using the OT protocol to transmit the key, and will not be expanded.

The above examples of S310-S330 provide a solution for constructing a confusion set to protect the privacy of the client. In some cases, the confusion set may be constructed unreasonably, but it is still easy for the server to guess the ID that the client really wants to query.

For example, in the example in Table 1 above, it can be noticed that the Age and Native_place in the two rows of id_4 and id_7 are respectively the same, that is, the two rows cannot be distinguished by Age and Native_place. In the above S332, for example, the confusion set constructed by the client is {id_1,id_4}, and the constructed retrieval statement is:

select Name where ID={id_1,id_4}

After the server receives the search statement containing the confusion set, it can know that the field of interest in the search statement is Name, not Age and Native_place, which means that the sensitive field of the client in S310 and S320 should be Age and/or Native_place. The element id_4 in the confusion set cannot be distinguished from the row id_7 from Age and/or Native_place. That is to say, if the elements in the confusion set are located through the sensitive field Age and/or Native_place, it is unreasonable to only have id_4 but not id_7. In this search statement, if there is id_4 in the confusion set, there should also be id_7. In this way, the server can speculate that in the existing confusion set {id_1, id_4}, id_4 is a forged element, and id_1 is the real ID to be queried, thus causing the privacy of the client to be leaked to a certain extent.

The above content is an example of the leakage of client privacy caused by the unreasonable construction of the confusion set. In order to avoid unreasonable construction of the confusion set, this specification also provides an embodiment of constructing the confusion set.

Then the method for constructing the confusion set may include as shown in Figure 3:

S410: The client sends the encrypted sensitive field to the server, and obtains the same sensitive field encrypted by the server through interaction with the server.

S420: The client searches in the query base according to the sensitive field encrypted by the server, and obtains a first identification set of matching records.

S410 and S420 are similar to the aforementioned S310 and S320 respectively, and will not be repeated here. Suppose the sensitive field sent by the client to the server is (H(25)) ^β or β·H(25), then the client receives the same sensitive field encrypted by the server through the interaction with the server as ((H(25) ) ^β ) ^α or α·β·H(25). The client can use its private key β to decrypt the twice-encrypted sensitive field, for example, (H(25)) ^α or α·H(25). In this way, the client searches in the local query base according to the sensitive field (H(25)) ^α or α·H(25) encrypted by the server, and obtains the first identifier of the matching record as id_1. In the following, Table 2 will be used as an example for illustration.

S430: The client selects at least one point in the query base except for the ID field and the field of interest, uses the selected at least one point as a retrieval condition, constructs a retrieval statement according to the retrieval condition and the original field of interest, and generates the query in the query base. Execute retrieval on the above to obtain the second identification set of matching records.

Suppose the size of the confusion set is n, that is, the confusion set contains n elements. According to the embodiment of this specification, a confusion set composed of n elements can be generated, for example, each element is an identifier, and the n identifiers include identifiers of matching records, that is, the aforementioned first identifier set.

In S430, still taking Table 2 or Table 3 as an example, the client selects at least one point in the query base except the ID field and the field of interest, for example, one point, for example, select the point α·H(34) . A point in the query base can be defined as a field value determined by rows and columns.

Furthermore, the client may use at least one selected point as a retrieval condition, and construct a retrieval statement according to the retrieval condition and the original field of interest. The original interest refers to the field of interest that the client originally expected to query, for example, it originally wanted to query Name. For example, if the point α·H(34) is selected, and the corresponding field name is Age, then the constructed search statement can be as follows:

select Name where Age＝α·H(34)

The client can execute the search statement on the query basis, and obtain the second identifiers of the matching records as id_4 and id_7 as the second identifier set {id_4, id_7}.

In addition, you can further select points in the query base other than the ID field and the field of interest, use the selected point as a retrieval condition, construct a retrieval statement based on the retrieval condition and the original field of interest, and execute the retrieval on the query base , and the identifiers of the matching records are obtained and added to the second identifier set. For example, the search statement constructed is as follows:

select Name where Native_place=α·H(anhui)

Then the identifiers of the matching records are id_0 and id_2.

Add id_0 and id_2 into the second identity set to obtain the second identity set: {{id_4, id_7}, {id_0, id_2}}.

S440: The client constructs a confusion set according to the first identity set and the second identity set.

The client may use the first identifier id_1 and the second identifier id_4 and id_7 together as a confusion set, that is, the confusion set is {id_1, id_4, id_7}. In this way, a confusion set of n=3 is obtained. Furthermore, executing other steps in S331-S335 can make the confusion set more reasonable, thereby avoiding privacy leakage of the client due to unreasonable structure of the confusion set. Finally, the server can return the value of the field of real interest to the client through 1-of-3 inadvertent transmission.

Among them, the order of the elements in the confusion set is not limited, for example, it can be {id_4, id_1, id_7}, {id_4, id_7, id_1}, {id_7, id_1, id_4}, {id_7, id_4, id_1}, {id_1, id_7 , id_4} and the like can be in random order, as long as the real ID to be transmitted can be specified in OT later. The same is true in the following examples, which will not be illustrated again.

In addition, it can also be n=2, for example, the confusion set is {id_1, {id_4, id_7}}, that is, the second element in the confusion set is the set {id_4, id_7}. Finally, the server can return the value of the field of real interest to the client through 2-to-1 inadvertent transmission. In addition, it can also be {id_1, {id_4, id_7}, {id_0, id_2}}, at this time n=3, that is, choose 1 from 3.

In addition, the sensitive field in S410 and S420 is, for example, α·H(25), then the obtained first identification set is {id_1}. For example, the second identification set is the result obtained by searching respectively through the constructed search formulas select Name where Age=α·H(46) and selectName where Age=α·H(56), and the second identification set is {id_3, id_9}. Then, the client constructs a confusion set according to the first identity set and the second identity set, which may be formed by tiling elements in the first identity set and the second identity set. Thus, the confusion set is eg {id_1, id_3, id_9}. Furthermore, the value of the field of real interest can be returned to the client by inadvertent transmission of n to 1, where n=3, the number of matching records in the confusion set is 1, that is, the value of the Name field in id_0 can be returned to the client through inadvertent transmission of 3 to 1 client. In addition, when the number of elements in the first identity set is k, k can be selected from n for inadvertent transmission.

In addition to tiling elements in the first identification set and the second identification set to form a confusion set, elements in the first identification set may also be tiled and together with the second identification set to form a confusion set. For example, as mentioned above, the first identity set is {id_0, id_6}. For example, the second identification set is still {id_3, id_9}, and the confusion set may be {id_0, id_6, {id_3, id_9}}. Furthermore, the value of the field of real interest can be returned to the client by using n selection and k inadvertent transmission, where n=3, and the number of matching records in the confusion set is 2, that is, the value of the Name field in id_0 and id_6 can be inadvertently transmitted by 3 selections and 2 Return to client. When the element in the first identification set is 1, n choose k is n choose 1.

Similarly, elements in the second identification set may also be tiled to form a confusion set together with the first identification set. For example, as mentioned above, the first identification set is {id_0, id_6}. For example, the second identification set is the result obtained by searching respectively through the constructed retrieval formulas select Name where Age=α·H(46) and select Name where Age=α·H(56), and the second identification set is {id_3, id_9} . Then the confusion set can be {{id_0, id_6}, id_3, id_9}. Furthermore, the value of the field of real interest can be returned to the client by using n selection and k inadvertent transmission, where n=3, the number of matching records in the confusion set is 1, and the identifiers of these two matching records are regarded as a set called 1 in the confusion set element, that is, the value of the Name field in {id_0, id_6} can be returned to the client through inadvertent transmission of 1 out of 3.

However, the IDs of at least two rows corresponding to indistinguishable at least one selected point other than the ID field and the field of interest cannot be split into different sets. For example, the first identity set is {id_0, id_6}, and the second identity set is {{id_4, id_7}, id_3, id_9}. Among them, as mentioned above, in addition to the ID field and the field of interest Name, the remaining fields Age and Native_place cannot distinguish between id_4 and id_7, so id_4 and id_7 need to be put into the same set, that is, {id_4, id_7}, cannot be split. Conversely, the identifiers of indistinguishable rows in the confusion set except for the ID field and the field of interest are placed in the same minimum set, which also meets the requirements of other implementations, thereby avoiding unreasonable construction of the confusion set.

In addition, elements in the first identification set and the second identification set may also be mixed to form a confusion set. For example, as mentioned above, the first identification set is {id_0, id_6}, for example, the second identification set is still {id_3, id_9}, then the confusion set can be {{id_0, id_6}, {id_0, id_3}, id_9}. id_3 and id_9 can be distinguished except for the ID field and the field of interest, so the identifiers of the corresponding rows can also be split, that is, they are not placed in the same minimum set. Furthermore, the value of the field of real interest can be returned to the client by using n selection and k inadvertent transmission, where n=3, the number of matching records in the confusion set is 2, and the identifiers of these two matching records are regarded as a set called the confusion set 1 element, that is, the value of the Name field in {id_0, id_6} can be returned to the client through inadvertent transmission of 1 out of 3.

The above example shows the case of one conditional field, and it is similar for two or more conditional fields. Specifically, in S430, still taking Table 2 as an example, the client selects two points in the query base except the ID field and the field of interest, for example, select α·H(34) and α·H(shanghai) 2 points.

Furthermore, the client can use the selected two points as retrieval conditions, and construct a retrieval statement based on the retrieval conditions and the original fields of interest. The original interest refers to the field of interest that the client originally expected to query, for example, it originally wanted to query Name. For example, if two points α·H(34) and α·H(shanghai) are selected, and the corresponding field names are Age and Native_place respectively, then the constructed search statement can be as follows:

select Name where Age=α·H(34) or Native_place=α·H(shanghai)

The client can execute the search statement on the query basis, and obtain the matched second identifiers as id_4, id_7, id_1, id_5 as the second identifier set {id_4, id_7, id_1, id_5}.

In the above retrieval statement, in the retrieval condition of where, Age=α·H(34) is a predicate in SQL, and Native_place=α·H(shanghai) is another predicate in SQL. The connecting word between two predicates, here is or, and it can also be and and the like. In other words, a connective can be a random kind of connective. More broadly, when there are more than two predicates, the connectives between two adjacent predicates are random ones.

The following introduces a client that implements the construction of a confusion set in an embodiment of this specification. The encryption/decryption performed by the client and the server on the same target adopts an encryption/decryption algorithm that can be exchanged, and:

The client is configured with a query base, and the query base is obtained after the server encrypts the database;

The client sends the sensitive field encrypted by itself to the server, and obtains the same sensitive field encrypted by the server through interaction with the server; in the query base, according to the search based on the sensitive field encrypted by the server, a matching record is obtained The first identification set; select at least one point in the query base except the ID field and the field of interest, use the selected at least one point as a retrieval condition, construct a retrieval statement according to the retrieval condition and the original field of interest, and in Searching is performed on the query basis to obtain a second identification set of matching records; a confusion set is constructed according to the first identification set and the second identification set.

The following introduces a client that implements the construction of a confusion set in an embodiment of this specification, including:

processor,

The memory stores a program, wherein when the processor executes the program, the above-mentioned method in FIG. 3 is executed.

A storage medium in an embodiment of this specification is introduced below, which is used to store a program, wherein the program causes the client to execute the method in FIG. 3 above when executed.

In the 1990s, the improvement of a technology can be clearly distinguished as an improvement in hardware (for example, improvements in circuit structures such as diodes, transistors, and switches) or improvements in software (improvement in method flow). However, with the development of technology, the improvement of many current method flows can be regarded as the direct improvement of the hardware circuit structure. Designers almost always get the corresponding hardware circuit structure by programming the improved method flow into the hardware circuit. Therefore, it cannot be said that the improvement of a method flow cannot be realized by hardware physical modules. For example, a Programmable Logic Device (Programmable Logic Device, PLD) (such as a Field Programmable Gate Array (Field Programmable Gate Array, FPGA)) is such an integrated circuit, and its logic function is determined by programming the device by a user. It is programmed by the designer to "integrate" a digital system on a PLD, instead of asking a chip manufacturer to design and make a dedicated integrated circuit chip. Moreover, nowadays, instead of making integrated circuit chips by hand, this kind of programming is mostly realized by "logic compiler (logic compiler)" software, which is similar to the software compiler used when writing programs. The original code of the computer must also be written in a specific programming language, which is called a hardware description language (Hardware Description Language, HDL), and there is not only one kind of HDL, but many kinds, such as ABEL (Advanced Boolean Expression Language) , AHDL (Altera Hardware Description Language), Confluence, CUPL (Cornell University Programming Language), HDCal, JHDL (Java Hardware Description Language), Lava, Lola, MyHDL, PALASM, RHDL (Ruby Hardware Description Language), etc., currently the most commonly used is VHDL (Very-High-Speed Integrated Circuit Hardware Description Language) and Verilog. It should also be clear to those skilled in the art that only a little logical programming of the method flow in the above-mentioned hardware description languages and programming into an integrated circuit can easily obtain a hardware circuit for realizing the logic method flow.

The controller may be implemented in any suitable way, for example the controller may take the form of a microprocessor or processor and a computer readable medium storing computer readable program code (such as software or firmware) executable by the (micro)processor , logic gates, switches, Application Specific Integrated Circuits (ASICs), programmable logic controllers, and embedded microcontrollers, examples of controllers include but are not limited to the following microcontrollers: ARC 625D, Atmel AT91SAM, Microchip PIC18F26K20 and Silicone Labs C8051F320, the memory controller can also be implemented as part of the memory's control logic. Those skilled in the art also know that, in addition to realizing the controller in a purely computer-readable program code mode, it is entirely possible to make the controller use logic gates, switches, application-specific integrated circuits, programmable logic controllers, and embedded The same function can be realized in the form of a microcontroller or the like. Therefore, such a controller can be regarded as a hardware component, and the devices included in it for realizing various functions can also be regarded as structures within the hardware component. Or even, means for realizing various functions can be regarded as a structure within both a software module realizing a method and a hardware component.

The systems, devices, modules, or units described in the above embodiments can be specifically implemented by computer chips or entities, or by products with certain functions. A typical implementation device is a server system. Of course, this description does not exclude that with the development of future computer technology, the computer that realizes the functions of the above embodiments may be, for example, a personal computer, a laptop computer, a vehicle-mounted human-computer interaction device, a cellular phone, a camera phone, a smart phone, a personal digital assistant , media players, navigation devices, email devices, game consoles, tablet computers, wearable devices, or any combination of these devices.

Although one or more embodiments of the present specification provide the operation steps of the method described in the embodiment or the flowchart, more or fewer operation steps may be included based on conventional or non-inventive means. The sequence of steps enumerated in the embodiments is only one of the execution sequences of many steps, and does not represent the only execution sequence. When an actual device or terminal product is executed, the methods shown in the embodiments or drawings can be executed sequentially or in parallel (such as a parallel processor or multi-thread processing environment, or even a distributed data processing environment). The term "comprising", "comprising" or any other variation thereof is intended to cover a non-exclusive inclusion such that a process, method, product, or apparatus comprising a set of elements includes not only those elements, but also other elements not expressly listed elements, or also elements inherent in such a process, method, product, or apparatus. Without further limitations, it is not excluded that there are additional identical or equivalent elements in a process, method, product or device comprising said elements. For example, if the words first, second, etc. are used, they are used to indicate names and do not indicate any specific order.

For the convenience of description, when describing the above devices, functions are divided into various modules and described separately. Of course, when implementing one or more of this specification, the functions of each module can be realized in the same or more software and/or hardware, and the modules that realize the same function can also be realized by a combination of multiple submodules or subunits, etc. . The device embodiments described above are only illustrative. For example, the division of the units is only a logical function division. In actual implementation, there may be other division methods. For example, multiple units or components can be combined or integrated. to another system, or some features may be ignored, or not implemented. In another point, the mutual coupling or direct coupling or communication connection shown or discussed may be through some interfaces, and the indirect coupling or communication connection of devices or units may be in electrical, mechanical or other forms.

The description is described with reference to flowcharts and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the description. It should be understood that each procedure and/or block in the flowchart and/or block diagram, and a combination of procedures and/or blocks in the flowchart and/or block diagram can be realized by computer program instructions. These computer program instructions may be provided to a general purpose computer, special purpose computer, embedded processor, or processor of other programmable data processing equipment to produce a machine such that the instructions executed by the processor of the computer or other programmable data processing equipment produce a An apparatus for realizing the functions specified in one or more procedures of the flowchart and/or one or more blocks of the block diagram.

These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing apparatus to operate in a specific manner, such that the instructions stored in the computer-readable memory produce an article of manufacture comprising instruction means, the instructions The device realizes the function specified in one or more procedures of the flowchart and/or one or more blocks of the block diagram.

These computer program instructions can also be loaded onto a computer or other programmable data processing device, causing a series of operational steps to be performed on the computer or other programmable device to produce a computer-implemented process, thereby The instructions provide steps for implementing the functions specified in the flow chart or blocks of the flowchart and/or the block or blocks of the block diagrams.

In a typical configuration, a computing device includes one or more processors (CPUs), input/output interfaces, network interfaces, and memory.

Memory may include non-permanent storage in computer readable media, in the form of random access memory (RAM) and/or nonvolatile memory such as read only memory (ROM) or flash RAM. Memory is an example of computer readable media.

Computer-readable media, including both permanent and non-permanent, removable and non-removable media, can be implemented by any method or technology for storage of information. Information may be computer readable instructions, data structures, modules of a program, or other data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read only memory (ROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), Flash memory or other memory technology, Compact Disc Read-Only Memory (CD-ROM), Digital Versatile Disc (DVD) or other optical storage, Magnetic cassettes, magnetic tape magnetic disk storage, graphene storage or other magnetic storage devices or any other non-transmission medium that can be used to store information that can be accessed by computing devices. As defined herein, computer-readable media excludes transitory computer-readable media, such as modulated data signals and carrier waves.

Those skilled in the art should understand that one or more embodiments of this specification may be provided as a method, system or computer program product. Accordingly, one or more embodiments of the present description may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, one or more embodiments of the present description may employ a computer program embodied on one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein. The form of the product.

One or more embodiments of this specification may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. One or more embodiments of the present specification may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including storage devices.

Each embodiment in this specification is described in a progressive manner, the same and similar parts of each embodiment can be referred to each other, and each embodiment focuses on the differences from other embodiments. In particular, for the system embodiment, since it is basically similar to the method embodiment, the description is relatively simple, and for relevant parts, refer to part of the description of the method embodiment. In the description of this specification, descriptions referring to the terms "one embodiment", "some embodiments", "example", "specific examples", or "some examples" mean that specific features described in connection with the embodiment or example , structures, materials or features are included in at least one embodiment or example of this specification. In this specification, the schematic representations of the above terms are not necessarily directed to the same embodiment or example. Furthermore, the described specific features, structures, materials or characteristics may be combined in any suitable manner in any one or more embodiments or examples. In addition, those skilled in the art can combine and combine different embodiments or examples and features of different embodiments or examples described in this specification without conflicting with each other.

The above description is only an example of one or more embodiments of this specification, and is not intended to limit one or more embodiments of this specification. For those skilled in the art, various modifications and changes may occur in one or more embodiments of this description. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of this specification shall be included in the scope of the claims.

Claims (11)

1. A method for realizing the construction of a confusion set, the client receives the query base sent by the server, and the query base is obtained after being encrypted by the database; the encryption/decryption performed by the client and the server on the same target adopts an exchangeable order encryption/decryption algorithm; The client sends the encrypted sensitive field to the server, and obtains the same sensitive field encrypted by the server through interaction with the server; The client retrieves in the query base according to the sensitive field encrypted by the server, and obtains a first identification set of matching records; The client selects at least one point in the query base except the ID field and the field of interest, uses the selected at least one point as a retrieval condition, constructs a retrieval statement according to the retrieval condition and the original field of interest, and constructs a retrieval statement in the query base Execute retrieval on the above to obtain the second identification set of matching records; The client constructs a confusion set according to the first identity set and the second identity set. 2. The method according to claim 1, the client constructs a confusion set according to the first identity set and the second identity set, comprising: The client forms a confusion set after tiling elements in the first identification set and the second identification set. 3. The method according to claim 1, the client constructs a confusion set according to the first identity set and the second identity set, comprising: The client tiles the elements in the first identification set, and forms a confusion set together with the second identification set. 4. The method according to claim 1, the client constructs a confusion set according to the first identity set and the second identity set, comprising: The client tiles the elements in the second identification set, and forms a confusion set together with the first identification set. 5. The method according to claim 1, the client constructs a confusion set according to the first identity set and the second identity set, comprising: The client forms a confusion set by mixing elements in the first identity set and the second identity set. 6. The method according to claim 1, when the retrieval condition includes at least two predicates, the connecting words between two adjacent predicates are random connecting words. 7. The method of claim 1, the order of elements in the obfuscated set is a random order. 8. The method according to any one of claims 1-7, wherein identifiers of indistinguishable rows in the confusion set except the ID field and the field of interest are placed in the same minimum set. 9. A client that realizes the construction of a confusion set, the encryption/decryption performed by the client and the server on the same target adopts an encryption/decryption algorithm that can be exchanged, and: The client is configured with a query base, and the query base is obtained after the server encrypts the database; The client sends the sensitive field encrypted by itself to the server, and obtains the same sensitive field encrypted by the server through interaction with the server; in the query base, according to the search based on the sensitive field encrypted by the server, a matching record is obtained The first identification set; select at least one point in the query base except the ID field and the field of interest, use the selected at least one point as a retrieval condition, construct a retrieval statement according to the retrieval condition and the original field of interest, and in Searching is performed on the query basis to obtain a second identification set of matching records; a confusion set is constructed according to the first identification set and the second identification set. 10. A client that realizes the construction of a confusion set, comprising: processor, A memory storing a program, wherein when the processor executes the program, the method according to any one of claims 1-8 is performed. 11. A storage medium for storing a program, wherein when the program is executed, the client executes the method according to any one of claims 1-8.

Images