CN115664722A

CN115664722A - Method, system, server and client for realizing private information retrieval

Info

Publication number: CN115664722A
Application number: CN202211216293.8A
Authority: CN
Inventors: 吴炜; 魏长征; 陆林鹏; 吴行行; 闫莺; 张辉
Original assignee: Ant Blockchain Technology Shanghai Co Ltd
Current assignee: Ant Blockchain Technology Shanghai Co Ltd
Priority date: 2022-09-30
Filing date: 2022-09-30
Publication date: 2023-01-31
Also published as: WO2024066015A1

Abstract

One or more embodiments of the present specification provide a method, system, server and client for implementing private information retrieval. In the method, a server encrypts a database to obtain a query base and sends the query base to a client; the client and the server execute encryption/decryption on the same target by adopting encryption/decryption algorithms which can be exchanged in sequence; in a retrieval process, the method comprises the following steps: 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 side retrieves in a query base according to the sensitive field encrypted by the server side to obtain the identification of the matching record; and the server side and the client side transmit the value of the field of interest in the record/corresponding record corresponding to the preset size identification set containing the matching identification in the database to the client side in an accidental transmission mode.

Description

Method, system, server and client for realizing private information retrieval

Technical Field

The embodiment of the specification belongs to the technical field of privacy computing, and particularly relates to a method, a system, a server and a client for realizing privacy information retrieval.

Background

Privacy-Preserving Computing (Privacy-Preserving Computing) is a technical set for realizing data analysis and computation on the premise of protecting data from being leaked to the outside, and the data can be used but not be visible. By means of the privacy protection computing technology, the conversion and release of data values can be achieved on the premise that data and privacy security are fully protected.

Currently, the mainstream technologies for implementing privacy protection calculation mainly include three major directions: the first category is a cryptology-based privacy computing technology represented by Secure Multi-Party computing (SMPC); the second category is a technology derived from the fusion of artificial intelligence represented by Federal Learning (FL) and privacy protection technology; the third type is a trusted hardware-based Confidential Computing (CC) technology represented by a trusted Execution Environment (Trust Environment). Also, differential Privacy (DP) and the like are included. Differential Privacy (DP) is actually protection of the computation results, not for the computation process; federal learning, secure multiparty computing, and confidential computing protect the computing process and the results in between.

The first type of multi-party security computation includes four basic technologies, namely Garbled Circuit (GC), secret Sharing (Secret Sharing), oblivious transmission (Oblivious Transfer) and Homomorphic Encryption (HE). The Homomorphic Encryption is a special Encryption algorithm, the calculation is directly carried out on the basis of a ciphertext, the calculation result is the same as that based on a decrypted plaintext, and the Homomorphic Encryption comprises semi-Homomorphic Encryption (PHE) and Full Homomorphic Encryption (FHE).

The secure multi-party computing provides the privacy protection capability of the input secret data by means of the solid security theoretical foundation, and the security of the privacy protection computing process is realized. At present, two main implementation technical routes of safe multi-party computation are provided, including general safe multi-party computation and problem-specific safe multi-party computation. The former can solve various calculation problems, but the universal technical route is usually huge in system and large in various expenses; the latter designs a special protocol for a specific problem, such as Privacy Set Interaction (PSI), privacy Information Retrieval (PIR), and the like, and often obtains a calculation result at a lower cost than a general secure multiparty calculation protocol, but needs a domain expert to elaborate a design for an application scenario, and is generally not applicable to a general scenario and has a higher design cost.

The privacy set intersection is the intersection of the data held by the two parties under the condition that the two parties are not disclosed with any additional information. Additional information refers to any information other than the data intersection of the two parties. The privacy aggregation requirement is very useful in real scenes, such as data alignment in longitudinal federal learning, friend discovery through an address book in social software, and the like.

Private information retrieval is one method by which a client retrieves information from a database. In the retrieval process, the inquiring party hides the inquiry target identification, and the data service party provides a matched inquiry result but cannot acquire a specific inquiry object.

Disclosure of Invention

The present specification aims to provide a method, a system, a server and a client for realizing private information retrieval, which includes:

a method for realizing private information retrieval, a server encrypts a database to obtain a query base, and sends the query base to a client; the client and the server execute encryption/decryption on the same target by adopting encryption/decryption algorithms which can be exchanged in sequence;

in a retrieval process, the method comprises the following steps:

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

s220: the client side retrieves in a query base according to the sensitive field encrypted by the server side to obtain the identification of the matching record;

s230: and the server side and the client side transmit the value of the field of interest in the record/corresponding record corresponding to the preset size identification set containing the matching identification in the database to the client side in an accidental transmission mode.

A system for realizing private information retrieval comprises a server and a client, wherein the client and the server execute encryption/decryption on the same target by adopting encryption/decryption algorithms capable of exchanging sequences, and the system comprises:

the server side is provided with a database, encrypts the database to obtain a query base and sends the query base to the client side;

in a retrieval process:

the client sends the sensitive field encrypted by the client to the server, and obtains the same sensitive field encrypted by the server 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 the identifier of the matching record;

and the server side and the client side transmit the value of the field of interest in the record/corresponding record corresponding to the preset size identification set containing the matching identification in the database to the client side in an accidental transmission mode.

A server for realizing private information retrieval, wherein encryption/decryption executed by the server and a client on the same target adopt encryption/decryption algorithms which can be exchanged in sequence, and the server and the client are characterized in that:

in a retrieval process:

the server receives the sensitive field which is sent by the client and encrypted by the server, encrypts the sensitive field again and returns the encrypted sensitive field to the client; and the server side and the client side transmit the value of the field of interest in the record/corresponding record corresponding to the preset size identification set containing the matching identification in the database to the client side in an inadvertent transmission mode.

A client for realizing private information retrieval, wherein encryption/decryption executed by the client and a server on the same target adopt encryption/decryption algorithms which can exchange sequences, and the client and the server:

the client is configured with a query base, and the query base is obtained by encrypting a database by the server;

in a retrieval process:

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 also retrieves in a query base according to the sensitive field encrypted by the server to obtain an identifier of the matching record; and the client and the server also obtain the value of the field of interest in the record/corresponding record corresponding to the matching identifier in the database in an inadvertent transmission mode.

In the embodiment, the query bases are configured to the client in advance, so that the client can locate the identifiers of the fields to be queried in the query bases through interaction with the server and the query bases without exposing the plaintext of the database, and further initiate queries to the server according to the identifiers, thereby ensuring the privacy protection of the database by the server and supporting the structured query statement. Moreover, the values of the fields of interest in the records/corresponding records corresponding to the matching identifiers are transmitted between the server and the client, and an accidental transmission mode is adopted, so that the matching identifiers of the client cannot be exposed to the server, and the privacy of the client is protected.

Drawings

In order to more clearly illustrate the technical solutions of the embodiments in the present specification, the drawings required to be used in the description of the embodiments will be briefly introduced below, and it is obvious that the drawings in the following description are only some embodiments described in the present specification, and it is obvious for those skilled in the art that other drawings may be obtained according to these drawings without inventive labor.

FIG. 1 is a schematic flow diagram of an embodiment;

FIG. 2 is a schematic flow diagram of an embodiment.

Detailed Description

In order to make those skilled in the art better understand the technical solutions in the present specification, the technical solutions in the embodiments of the present specification will be clearly and completely described below with reference to the drawings in the embodiments of the present specification, and it is obvious that the described embodiments are only a part of the embodiments of the present specification, and not all of the embodiments. All other embodiments obtained by a person skilled in the art based on the embodiments in the present specification without any inventive step should fall within the scope of protection of the present specification.

As previously mentioned, PIR is a method by which a client retrieves information from a database. The PIR scheme is a solution proposed by Chor B et al in 1995 to protect the privacy of user queries. The PIR scheme mainly aims to ensure that a query user submits a query request to a database on a server, and completes the query under the condition that privacy information queried by the user is not leaked, namely the server does not know specific query information of the user and retrieved data items in the retrieval process.

The application scenes for retrieving the private information comprise:

i. the patient wants to inquire about the treatment medicine of his disease through the medical system, if the name of the disease is used as the inquiry condition, the medical system will know that the patient may suffer from the disease, so that the privacy of the patient is revealed, and the privacy information inquiry can avoid the revealing problem.

in the domain name and trademark application process, a user needs to firstly submit domain name or trademark information applied by the user to a relevant database to inquire whether the domain name or trademark information exists, but does not want a service provider to know the application name of the user, so that the user can register the domain name or trademark information in advance.

in the stock market, a user wants to inquire about stock information, but cannot reveal interested stocks to the server, so that the stock price and the preference of the user are influenced.

A simple implementation is that the database sends all data to the client, but the database cannot be secured, i.e. the privacy of the server cannot be guaranteed. PIR, which can guarantee the privacy of both the client and the database, is called Symmetric PIR (SPIR), while PIR, which guarantees the privacy of either the client or the database, is called asymmetric PIR (SPIR). And dividing the data into a multi-copy PIR and a single-copy PIR according to the number of the database copies. The multi-copy PIR protocol requires no collusion between multiple database copies, which is difficult to satisfy in real-world scenarios, so more is considered a single copy PIR. Single copy PIR can only achieve Computational safety (CPIR). In most PIR schemes it is always assumed that the client knows that it wants to retrieve the few bits (single bit) of the database. In real-world scenarios, however, the client will often retrieve based on a key (without knowing the specific location of the key with respect to the database), and it is the string (multi-bit) that it wishes to retrieve. In summary, a functional PIR is generally required to satisfy multiple conditions, such as symmetry, single copy, keyword-by-keyword search, string return, etc., at the same time, and to achieve a balance between computational efficiency and communication efficiency. The above conditions may be met or partially met by cryptographic techniques such as homomorphic encryption, oblivious Transfer (OT), one-way Trapdoor Function (One-way Trapdoor Function), and the like.

The present specification provides a method embodiment for implementing 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 database locally, which can be queried by the client. The local database of the server is, for example, as follows:

ID	Name	Age	Native_place
				id_0	A	24	anhui
id_1	B	25	shanghai
				id_2	C	30	anhui
id_3	D	46	henan
				id_4	E	34	shandong
id_5	F	54	shanghai
				id_6	G	24	beijing
id_7	H	34	shandong
				id_8	I	42	guangdong
id_9	J	56	zhejiang

TABLE 1 database the server has

In the example of table 1, there are 4 fields, i.e. ID _0,. 10 records in total, including ID, name, age, and Native _ place, and there is one record for each row. Id _9 is the identifier of each line record.

In order to allow the client to perform retrieval without exposing the privacy security of the server, the server may encrypt the database to obtain the query base. The encryption scheme may be implemented using RSA (a widely used asymmetric encryption algorithm, proposed in 1977 by rond listeriost (Ron Rivest), addi samhr (Adi Shamir) and lenard aldman (leonarard Adleman)) or ECC (elliptic Curve Cryptography). Specifically, the server may encrypt the data using the RSA private key/ECC private key α, that is, encrypt each field (i.e., data in each cell) except the ID column using the RSA private key/ECC private key α.

In the case of using the ECC encryption/decryption algorithm, specifically, the server may generate and properly store a secret value α, which 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, and the value can be expressed as Hash (C) or H (C).

According to the operation property of scalar multiplication on the elliptic curve, a point P and an integer k on the elliptic curve are easy to calculate Q = kP, and the obtained result Q is also a point on the elliptic curve; on the contrary, if one point pair P, Q on the elliptic curve is known, it is difficult to solve the value of k for which the equation holds in Q = kP.

Here, the value α · H (C) is easily calculated by scalar multiplication on an elliptic curve, but it is difficult to estimate the value α from the result of α · H (C) and H (C). When it is difficult to obtain the value of α, it is difficult to obtain the result of α · H (C) and also the value of H (C).

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

ID	Name	Age	Native_place
				id_0	α·H(A)	α·H(24)	α·H(anhui)
id_1	α·H(B)	α·H(25)	α·H(shanghai)
				id_2	α·H(C)	α·H(30)	α·H(anhui)
id_3	α·H(D)	α·H(46)	α·H(henan)
				id_4	α·H(E)	α·H(34)	α·H(shandong)
id_5	α·H(F)	α·H(54)	α·H(shanghai)
				id_6	α·H(G)	α·H(24)	α·H(beijing)
id_7	α·H(H)	α·H(34)	α·H(shangdong)
				id_8	α·H(I)	α·H(42)	α·H(guangdong)
id_9	α·H(J)	α·H(56)	α·H(zhejiang)

table 2, query base of server side encrypted by ECC private key

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

Furthermore, the server can send the query base to the client needing to be retrieved. In one approach, the server may send the query base directly to the client, such as directly to a device of the client, or to a proxy server of the client; in another way, the server may issue the query base on a Uniform Resource Locator (URL), and the client may obtain the query base from the URL.

Accordingly, the client may receive the query base and store the received query base locally.

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

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

Here, calculation (H (C)) ^α mod q is easy, but knows (H (C)) ^α The result of mod q and H (C), q make it difficult to deduce the value of α. When it is difficult to obtain the value of alpha, (H (C)) ^α It is also difficult to know the value of H (C) as a result of mod q. Subsequently, the shape is as (H (C)) ^α Expression for mod q is omitted, and is briefly represented as (H (C)) ^α 。

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

ID	Name	Age	Native_place
				id_0	(H(A)) ^α	(H(24)) ^α	(H(anhui)) ^α
id_1	(H(B)) ^α	(H(25)) ^α	(H(shanghai)) ^α
				id_2	(H(C)) ^α	(H(30)) ^α	(H(anhui)) ^α
id_3	(H(D)) ^α	(H(46)) ^α	(H(henan)) ^α
				id_4	(H(E)) ^α	(H(34)) ^α	(H(shandong)) ^α
id_5	(H(F)) ^α	(H(54)) ^α	(H(shanghai)) ^α
				id_6	(H(G)) ^α	(H(24)) ^α	(H(beijing)) ^α
id_7	(H(H)) ^α	(H(34)) ^α	(H(shandong)) ^α
				id_8	(H(I)) ^α	(H(42)) ^α	(H(guangdong)) ^α
id_9	(H(J)) ^α	(H(56)) ^α	(H(zhejiang)) ^α

table 3, the query base after the server side adopts RSA private key to encrypt

Furthermore, the server can send the query base to the client needing to be retrieved. Similarly, the server may send the query base directly to the client, for example, directly to a device of the client, or to a proxy server of the client; in another way, the server may issue the query base on a Uniform Resource Locator (URL), and the client may obtain the query base from the URL.

S110: the client sends the sensitive field encrypted by the client 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 Age field value is 25, and 25 is a sensitive field, i.e. it is not desirable to let the opposite end know. To avoid letting the server know that the client retrieval condition is the value 25 of the Age field, the client may encrypt this 25. For example, the client side adopts the same encryption algorithm as the server side generates the query base by adopting RSA/ECC private key encryption.

Specifically, under the condition of adopting RSA private key encryption, the client generates the secret beta and stores the secret beta properly. Further, the client may encrypt 25 with its own private key β. In particular toMay be to 25 or to the hash value of 25. Here, the hash encryption of 25 is taken as an example, and similarly to the case of directly encrypting 25, the client and the server use the same hash algorithm. For example, the client uses the same large prime q as the server as the modulus. The client can RSA encrypt the hash value of 25 with beta pair 25 to obtain (H (25)) ^β . The sensitive field sent by the client to the server may be (H (25)) ^β Wherein (H (25)) ^β A ciphertext representing a value 25 of the sensitive field.

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

For example, the client constructs a query statement as select Name where Age =25.

To protect privacy, that is, not let the service end obtain the query, it is the condition of Age =25, for example, 25 privacy is protected, and the result is as follows:

select Name where Age＝？

wherein? Representing the replaced search statement.

In particular, the client may encrypt 25 with the RSA private key. For example, the client may perform hash calculation on the pair 25 by using the same hash function as the server, and then perform RSA encryption on the hash value of the pair 25 by using β 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 previously described, (H (25)) ^β Is the ciphertext, i.e., "? "the server side cannot know the beta and the beta 25 of the content.

Under the condition of adopting ECC private key encryption, the client side adopts the elliptic curve which is the same as that of the server side, namely the elliptic curve has the same elliptic curve parameters and generation elements. The client itself generates the secret beta and saves it properly. Further, the client may encrypt 25 with its own private key β. Specifically, the hash value of 25 may be encrypted, and the client and the server use the same hash algorithm. For example, the client may perform ECC encryption on the hash value of 25 using β to obtain β · H (25). 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.

select Name where Age＝？

wherein? Representing the replaced retrieval statement.

Specifically, the client may encrypt 25 with the ECC private key. For example, the client uses the same elliptic curve as the server, i.e. has the same elliptic curve parameters and generator. The client side can encrypt and replace the sensitive fields in the retrieval statement by using the ECC private key of the client side, and sends the replaced privacy retrieval statement to the server side. For example, the client itself generates the secret β and holds it properly. The client may perform hash calculation on the pair 25 by using the same hash function as that of the server, and then perform ECC encryption on the hash value of the pair 25 by using β, thereby obtaining β · H (25). The query statement sent by the client to the server is, for example, as follows:

select Name where Age＝β·H(25)

as described above, β · H (25) is a ciphertext, which is "? "the server side cannot know the beta and the beta 25 of the content.

The client obtains the same sensitive field encrypted by the server through interaction with the server, and can include that the server encrypts the sensitive field encrypted by the client again by adopting a self key and sends the encrypted sensitive field to the client, and the client decrypts the sensitive field encrypted twice by adopting the self key to obtain the sensitive field encrypted by the server. The core of the content is to find an encryption algorithm which can perform decryption in an exchange sequence according to two continuous encryption operations (encryption by two parties in sequence). According to the cryptology property of ECC, two parties agree to use the same elliptic curve, namely, the elliptic curve has the same elliptic curve parameter and generator, and respectively hold private keys alpha and beta, the encryption operation is scalar multiplication operation by alpha (or beta), and the encryption can be decrypted in the same or different order regardless of whether the alpha is used for encryption and then the beta is used for encryption or the beta is used for encryption and then the alpha is used for encryption, namely, the encryption result can be decrypted in different order. Similarly, according to the cryptology property of RSA, two parties agree to use a same large prime number q and primitive root g, which respectively hold private keys alpha and beta, the encryption operation is to use alpha (or beta) to carry out exponentiation and use q to get modulus, and the encryption can be decrypted in the same or different orders regardless of whether alpha encryption is used first and then beta encryption or beta encryption is used first and then alpha encryption, namely, the encryption result can be decrypted in different orders. Overall, here, encryption/decryption algorithms that can exchange orders are adopted by the client and the server for the same target.

Specifically, after receiving the privacy retrieval statement, the server encrypts the privacy field again and returns the encrypted privacy field to the client, or after receiving the sensitive field which is sent by the client and encrypted by the client, the server encrypts the encrypted sensitive field again by using the server own key and returns the encrypted sensitive field to the client. And then, the client decrypts the sensitive field encrypted twice by adopting the own key to obtain the sensitive field encrypted by the server.

For example, case 1: the server can receive the data sent by the client (H (25)) ^β 。

The server may re-encrypt the encrypted sensitive field (i.e., the privacy field) and return the re-encrypted sensitive field to the client. In particular, the server may be paired with a privacy field (H (25)) ^β Adopting the RSA private key alpha of the user to carry out encryption again to obtain ((H (25)) ^β ) ^α 。

For example, case 1': the server can receive the clientPrivacy retrieval statement select Name where Age = (H (25)) ^β . Thus, the server can obtain the privacy field (H (25)) ^β 。

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

In particular, the server may be paired with a privacy field (H (25)) ^β Adopting the private key alpha of the RSA to carry out encryption again to obtain (H (25)) ^β ) ^α The specific process is similar to the above, and is not described herein again.

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

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

For example, case 2': the server may receive a privacy retrieval statement select Name where Age = β · H (25) sent by the client. Thus, the server can obtain the privacy field β · H (25) in the privacy search term.

Specifically, the server may encrypt the privacy field β · H (25) again by using its own ECC private key α to obtain α · β · H (25), and the specific process is similar to the above and is not described here again.

After the server side encrypts the sensitive field (namely the privacy field) encrypted by the client side again by using the self key and sends the encrypted sensitive field to the client side, the client side can decrypt the privacy field encrypted twice by using the self key to obtain the sensitive field encrypted by the server side.

For example, corresponding to cases 1 and 1' above, the client receives the message ((H (25)) ^β ) ^α The power operation has the following properties: ((H (25)) ^β ) ^α ＝(H(25)) ^βα ＝(H(25)) ^αβ ＝((H(25)) ^α ) ^β . Furthermore, the client can adopt the inverse element of the own private key beta

And decrypting the sensitive field after twice encryption as follows:

thus, the client gets the same sensitive field encrypted by the server, i.e. (H (25)) ^α 。

Corresponding to the above cases 2 and 2', the client receives α · β · H (25) sent by the server, where the scalar multiplication existence property is as follows: α · β · H (25) = β · α · H (25). Furthermore, the client can adopt the inverse element beta of the self private key beta ^-1 And decrypting the sensitive field after twice encryption as follows: beta is a beta ^-1 ·α·β·H(25)＝β ^-1 β · α · H (25) = α · H (25). In this way, the client also gets the same sensitive field encrypted by the server, i.e. α · H (25).

In RSA, pk · sk =1mod (p-1) · (q-1) according to euler's theorem, where p and q are two large prime numbers, so pk and sk are inverse elements of each other. Similarly, in ECC, pk = sk × G and G are a generator on the curve selected by ECC, so pk and sk are also inverse elements of each other.

S120: and the client side searches in the query base according to the sensitive field encrypted by the server side to obtain the identifier of the matching record, and returns the identifier to the server side.

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

The client may query in a query base based on the sensitive field encrypted by the server. For example, the client decrypts to obtain the privacy field α · H (25) or (H (25)) ^α Therefore, the client queries in a query base based on the privacy field, for example, queries in table 2 or table 3, respectively, and may obtain the record with ID = d _1, which includes the privacy field, in Age, where ID is the identifier of the record. Thus, the customer is based on the uniformAnd inquiring the private field encrypted by the server in the inquiry base, and positioning to obtain the identifier of the matched record after the record is matched.

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

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

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

select Name where ID＝id_1

thus, in S120, the client may send the constructed search formula to the server, where the search formula includes the identifier of the matching record and indicates that the field of interest is Name, that is, the Name of the field immediately following the select.

In other words, in both steps S110 and S120, one of the steps may be selected to send a search formula, which includes the field of interest.

S130: and 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 may search the database for the record corresponding to the identifier, retrieve the corresponding value in the retrieved 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 id _1 corresponds to Name = B in the record, i.e. return B to the client.

In the embodiment, the query bases are configured to the client in advance, so that the client can locate the identifiers of the fields to be queried in the query bases through interaction with the server and the query bases under the condition of not exposing the plaintext of the database, and further, the query is initiated to the server according to the identifiers, so as to obtain the values of the fields of interest in the records corresponding to the identifiers. Compared with the traditional multi-copy PIR, the method obviously does not need the premise assumption that collusion cannot be carried out among a plurality of copy databases, and has better practicability. Compared with the traditional situation that only bit retrieval can be realized in a single copy PIR, the present embodiment does not need to pay attention to the specific position (bit position) of the keyword to be retrieved in the database, can realize Query of the character string, and can support Structured Query Language (SQL). In the embodiment, the database is still kept at the server, and the query base obtained by encrypting the database is configured to the client, so that the client can conveniently perform data positioning to obtain the recorded identifier based on the query base during retrieval, and the client cannot obtain the content of the database due to the encryption characteristic of the query base, thereby ensuring the privacy protection of the server on the database. In general, in this embodiment, the form of the database and the query bases may be referred to as "asymmetric double copy" in the case of one server configuration database and one client configuration query base, and may be referred to as "asymmetric multiple copy" in the case of multiple client configuration query bases.

In the above embodiment, through the SQL query statement, the client may initiate a query on the field of interest, for example, the Name field to be queried in the above select Name. This exposes the fields of interest of the client to some extent. In another way, a qualified record, i.e. a whole line of data, can be queried, which can protect the privacy of the client, but the server is required to return the whole record, which exposes the whole line of data of the server to some extent. For example, by "select". Word Age =? And a search statement "or" select × where ID = ID _1 ". Thus, the result returned by the server may be a record of id _1, for example, as follows:

id_1 B 25 shanghai

in addition, in order to ensure the security of the transmission process, the server may encrypt and return the value of the field of interest in the identification correspondence record/correspondence record in the database to the client. For example, the server may encrypt the value of the field of interest in the record/record corresponding to the identifier in the database by using a symmetric key obtained through negotiation with the client, and return the encrypted value to the client, or encrypt the value of the field of interest in the record/record corresponding to the identifier in the database by using a public key in an asymmetric key of the client, and return the encrypted value to the client, so that the client may decrypt the encrypted value by using its own private key, and use a digital envelope method, and so on.

In the above S120, the client directly returns the ID obtained by matching to the server, although the record corresponding to the ID or the field of interest in the record may be obtained from the server, as in S130, this may expose the privacy of the client to a certain extent, that is, the server may know that the identifier that the client wants to query is ID _1. In order to protect the privacy of the client, the method can be realized by the following embodiments:

s210: the client sends the sensitive field encrypted by the client 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 Age field value is 25, and 25 is a sensitive field, i.e. it is not desirable to let the opposite end know. To avoid letting the server know that the client retrieval condition is the value 25 of the Age field, the client may encrypt this 25. For example, the private key encryption of RSA/ECC is adopted, and the encryption algorithm adopted by the client is the same as that adopted by the server for generating the query base.

Specifically, under the condition of adopting RSA private key encryption, the client generates secret beta and stores the secret beta properly. Further, the client may encrypt 25 with its own private key β. Specifically, the hash value of 25 or 25 may be encrypted. Here, the hash encryption of 25 is taken as an example, and the client and the server use the same hash algorithm similarly to the case of directly encrypting 25. For example, the client uses the same large prime q as the server as the modulus. The client can RSA encrypt the hash value of 25 with beta pair 25 to obtain (H (25)) ^β . The sensitive field sent by the client to the server can be (H (25)) ^β Wherein (H (25)) ^β Ciphertext representing the value 25 of the sensitive field.

Under the condition of adopting ECC private key encryption, the client side adopts the elliptic curve which is the same as that of the server side, namely the elliptic curve has the same elliptic curve parameters and generation elements. The client itself generates the secret beta and saves it properly. Further, the client may encrypt 25 with its own private key β. Specifically, the hash value of 25 may be encrypted, and the same hash algorithm is used by the client and the server. For example, the client may perform ECC encryption on the hash value of 25 using β to obtain β · H (25). 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, and can include that the server encrypts the sensitive field encrypted by the client again by adopting a self key and sends the encrypted sensitive field to the client, and the client decrypts the sensitive field encrypted twice by adopting the self key to obtain the sensitive field encrypted by the server. The core of the content is to find an encryption algorithm which can perform decryption in an exchange sequence according to two continuous encryption operations (encryption by two parties in sequence). According to the cryptology property of ECC, two parties agree to use the same elliptic curve, namely, the elliptic curve has the same elliptic curve parameter and generator, and respectively hold private keys alpha and beta, the encryption operation is scalar multiplication operation by alpha (or beta), and the encryption can be decrypted in the same or different order regardless of whether the alpha is used for encryption and then the beta is used for encryption or the beta is used for encryption and then the alpha is used for encryption, namely, the encryption result can be decrypted in different order. Similarly, according to the cryptographic property of RSA, two parties agree to use a same large prime number q and primitive root g, each holding a private key α and β, the encryption operation is exponentiation with α (or β) and modulo q, and the decryption can be performed in the same or different order, regardless of whether the encryption is performed by α first and then β or by β first and then α, i.e., the decryption can be performed in different order on the encrypted result. In general, encryption/decryption algorithms which can be exchanged in sequence are adopted by the client and the server to perform encryption/decryption on the same target.

Specifically, after receiving the sensitive field sent by the client and encrypted by the client, the server encrypts the encrypted sensitive field again with the server's own key and returns the encrypted sensitive field to the client. And then, the client decrypts the sensitive field encrypted twice by adopting the own key to obtain the sensitive field encrypted by the server.

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

For example, corresponding to case 1 above, the client receives the message ((H (25)) ^β ) ^α The power operation has the following properties: ((H (25)) ^β ) ^α ＝(H(25)) ^βα ＝(H(25)) ^αβ ＝((H(25)) ^α ) ^β . Furthermore, the client can adopt the inverse element of the own private key beta

And decrypting the sensitive field after twice encryption as follows:

Corresponding to the above case 2, the client receives α · β · H (25) sent by the server, and scalar multiplication existence properties in the α · β · H are as follows: α · β · H (25) = β · α · H (25). Furthermore, the client can adopt the inverse element beta of the own private key beta ^-1 And decrypting the sensitive field after twice encryption as follows: beta is a ^-1 ·α·β·H(25)＝β ^-1 β · α · H (25) = α · H (25). In this way, the client also gets the same sensitive field encrypted by the server, i.e. α · H (25).

In RSA, pk · sk =1mod (p-1) · (q-1) according to euler's theorem, where p and q are two large prime numbers, so pk and sk are inverse elements of each other. Similarly, in ECC, pk = sk · G, and G is a generator on the ECC selection curve, so pk and sk are also inverse elements of each other.

S220: and the client retrieves in the query base according to the sensitive field encrypted by the server to obtain the identifier of the matching record.

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

The client may query in a query base based on the sensitive field encrypted by the server. For example, the client decrypts to obtain the privacy field α · H (25) or (H (25)) ^α Therefore, the client queries in a query base based on the privacy field, for example, queries in table 2 or table 3, respectively, and may obtain the record with ID = d _1, which includes the privacy field, in Age, where ID is the identifier of the record. Therefore, the client queries in the query base based on the privacy field encrypted by the server side, and can locate and obtain the identification of the matched record after the record is matched.

S230: and the server returns the value of the field of interest in the record corresponding to the identifier set with the preset size including the matching identifier in the database to the client in an accidental transmission mode.

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

Here, the server may adopt an inadvertent transmission mode.

The Oblivious Transfer (OT) can be realized based on RSA, ECC, etc., and various OTs such as 2-from-1, n-from-1, m-from-k (k < m < n), etc. can be realized. To explain the principle by taking an example of 2 to 1OT, a sender has two secrets, m1 and m2 respectively, and needs to send 2 secrets to a receiver, and the receiver can only select to decrypt 1 secret but cannot know the other secret, and meanwhile, the sender cannot know which secret the receiver selects. Taking RSA as an example, a simple implementation procedure of 1 in option 2 is as follows:

first, the sender generates two different pairs of public and private keys and publishes two public keys, which are denoted as public key 1 and public key 2, respectively. Suppose the recipient 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 transmits to the sender. The sender decrypts the encrypted r by using two private keys of the sender, obtains r1 by using a private key 1, and obtains r2 by using a private key 2. Obviously, only r1 is equal to r, and r2 is a string of meaningless numbers (and the decryption result). However, the sender does not know which public key the receiver uses for encryption, and therefore the sender does not know which of r1 and r2 calculated by the sender is the true r. And after receiving the m1 and the m2, the sender uses the r1 to symmetrically encrypt the m1 and uses the r2 to symmetrically encrypt the m2, and sends two symmetric encryption results to the receiver. Since the receiver has r = r1 locally, the receiver can obtain m1 by symmetrically decrypting the two transmitted results with r, but cannot obtain m2 by decrypting, because r ≠ r2 the receiver has, the receiver cannot obtain the value of m2 by decrypting with a correct symmetric key. In this process, the sender does not know which of m1 and m2 the recipient calculated.

With 1 of 2 choices as the basis, 2 public and private key pairs can be expanded into n public and private key pairs, which becomes OT of 1 of n choices. The core of n-selected 1 is that the server side encrypts the values of the interested fields in n records/corresponding records in the data table respectively by using n different keys to obtain n encryption results, and sends the n encryption results to the client side; and the client decrypts 1 encryption result corresponding to the matching identifier in the n encryption results sent by the server by adopting the key corresponding to the matching identifier.

In the above embodiments, it is assumed that the data table of the server has n total records, and thus, the query base of the client also has n encrypted records. For convenience, the IDs of the data records are identified in order as ID _0, ID _1, ID _2,.. ID _ n-1. A simple implementation is as follows:

s231: the server generates n pairs of different public and private key pairs in advance and discloses a public key.

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

The server generates n pairs of different public and private key pairs (pk-sk; pk is public key and represents public key; sk is secret key and represents private key; the public key can be public and the private key needs to be kept secret), for example, pk is respectively ₀ -sk ₀ ，pk ₁ -sk ₁ ，pk ₂ -sk ₂ ，...，pk _n-1 -sk _n-1 And publishes the n public keys, i.e. publishes pk ₀ ，pk ₁ ，pk ₂ ，...，pk _n-1 . After the server side publishes the n ordered public keys, the client side can obtain the n public keys.

S232: the client generates a random number r, encrypts the r by using a public key corresponding to the expected ID and sends the r to the server.

It is assumed here that the client wants to obtain the record of id _1, while the server does not want to know that the record the client wants to obtain is the one of id _1. Thus, the client can adopt pk ₁ And encrypting r and then sending the r to the server. The above order, mainIt is meant that the ID and the public key have a correspondence, and such a correspondence may 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, and the client can use the pk corresponding to id _1 ₁ Encrypting r and then sending the r to a server; similarly, the client wants to obtain the record of id _ t but does not want the server to know that the record that the client wants to obtain is the record of id _ t, and the client can use pk corresponding to id _ t _t And encrypting r and then sending the r to the server.

S233: and after receiving the encrypted r, the server decrypts the r by using n private keys respectively.

The service ends respectively use the sk ₀ ，sk ₁ ，sk ₂ ，...，sk _n-1 Respectively decrypt through pk ₁ An encrypted random number r. For example, sk for server ₀ Decrypting to obtain r0, using sk ₁ Decrypting to obtain r1, using sk _n-1 Decryption yields r (n-1).

Obviously, only r1 is equal to r, since only sk is used ₁ It is the corresponding pk that is used for decryption ₁ Encryption; without corresponding pk ₁ Sk of (1) ₀ 、sk ₂ 、...、sk _n-1 The decryption results r0, r2,. And r (n-1) are not the same as r. Through decryption, the server only obtains the decryption result in the same form, and does not know what the true 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, and therefore the server does not know which of the n results r0, r1, r2,. And r (n-1) obtained by decryption is the true r.

S234: and the server side symmetrically encrypts each record in the database by adopting a decryption result of the corresponding serial number according to the serial number, and sends the symmetrically encrypted result to the client side.

For example, the server side symmetrically encrypts the record of id _0 by using r0, symmetrically encrypts the record of id _1 by using r1, symmetrically encrypts the record of id _ n-1 by using r (n-1), and sends the n symmetric encryption results to the client side.

S235: and the client side symmetrically decrypts the encryption result corresponding to the ID expected to be obtained in the symmetric encryption result by adopting the random number r to obtain a retrieval result.

And the client side symmetrically decrypts the encryption result corresponding to the ID expected to be obtained in the symmetric encryption result by adopting the random number r. Specifically, for example, in S232, the client desires to obtain the value of the field of interest in the record/record corresponding to id _1, the client uses the corresponding public key pk ₁ Encrypting the random number r; in S233, the server uses the corresponding private key sk ₁ Decrypting the decrypted result to obtain r1= r without corresponding pk ₁ Sk of (1) ₀ 、sk ₂ 、...、sk _n-1 The results r0, r2,. And r (n-1) obtained by decryption are not the same as r; in S234, the server performs symmetric encryption on the values of the fields of interest in the records/records, i.e., id _0, id _1, r., id _ n-1, respectively, by using r0, r1, r2,. And r (n-1), and sends the n symmetric encryption results to the client; in S235, the client performs symmetric decryption on the n symmetric encryption results by using the random number r. In the n symmetric decryption results, only the encryption result of id _1 is symmetrically encrypted by r, so that only the encryption result of id _1 is decrypted by r to obtain a correct value. Thus, the client can obtain the correct retrieval result, i.e., obtain the value of the field of interest in the corresponding record.

Of course, in order to reduce the amount of computation, the client may symmetrically decrypt the encrypted result corresponding to the ID expected to be obtained from the n symmetric encrypted results by using only the random number r, that is, the client decrypts the encrypted result of ID _1 by using only r, so as to obtain the value of the field of interest in the corresponding record/corresponding record of ID _1, without using r to symmetrically decrypt the symmetric encrypted results of ID _0, ID _2, ID.

For a clearer presentation, the client is here explained as follows to symmetrically decrypt the n symmetric encryption results with the random number r:

in S234, the server performs symmetric encryption on the values of the fields of interest in the corresponding records/records id _0, id _1, r., id _ n-1 by using r0, r1, r2,. And r (n-1), respectively:

enc (id _0, r 0), wherein r0 ≠ r;

enc (id _1, r 1), where r1= r;

enc (id _2, r 2), wherein r2 ≠ r;

...

enc (id _ n-1, r (n-1)), where r (n-1) ≠ r;

the Enc represents encryption (Encrypt), id _0, id _1, id _2,. And id _ n-1 of the previous part in the Enc () brackets represent the values of the fields of interest in n records/n records, and r0, r1, r2,. And r (n-1) of the latter part represent encryption keys.

In S235, the client performs symmetric decryption on the encrypted result in S234 by using the random number r. Specifically, the client uses the random number r to symmetrically decrypt the following contents:

dec (Enc (id _0, r 0), r), where r0 ≠ r;

dec (Enc (id _1, r 1), r), wherein r1= r;

dec (Enc (id _2, r 2), r), where r2 ≠ r;

...

dec (Enc (id _ n-1, r (n-1), r), where r (n-1) ≠ r;

the above Dec represents decryption (decryption), the former part of Dec () represents a decryption object, here, the above encryption result, and the latter part of Dec () represents a key used for decryption.

As can be seen, the client can only decrypt the record that gets id _1, but cannot speculate on other records. This is because the server only symmetrically encrypts only the record of ID _1 with the random number r, and symmetrically encrypts other IDs with the non-random number r, and the client cannot obtain r0, r2,. And r (n-1) except r1= r.

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

When the number of the matched records retrieved by the client in the query base is 1, the values of the fields of interest in all the records/corresponding records corresponding to the identifiers, including the matched identifiers, in the database are transmitted to the client through the inadvertent transmission of selecting 1 by n.

In the embodiment, the server does not know which ID or IDs the client inquires, but encrypts all records in the database and returns the encrypted records to the client, so that the privacy of the client is protected. However, in S233, the server decrypts the r encrypted by using n private keys, which requires a large amount of CPU and memory resources for performing a large amount of asymmetric decryption calculation. 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 large, the calculation amount of the server is large, and the bandwidth occupation is also large.

Furthermore, the result of a possible match is greater than 1, e.g., k (k) strips>1) This can be achieved by an inadvertent transmission of n-out-of-k. With respect to n-select k, one implementation is to group every k of n records into a set, each set corresponding to a public-private key pair, so that there will be a total of n sets

(C represents a combination formula, and the number of k optional combinations in n). Next, adopt

And 1, transmitting the values of the fields of interest in all records/corresponding records corresponding to the identifiers including the matching identifiers in the database to the client in an accidental transmission mode.

The implementation process of the inadvertent transmission mode of the option 1 is similar to the implementation process of the inadvertent transmission mode of the option 1. Namely for the server

Encrypting the value of the field of interest in each k records/corresponding records in the data table by different keys

Encrypting the result, and transmitting the result

Sending the encryption result to the client; the client side adopts the key corresponding to the matching identifier to decrypt the key sent by the server side

And 1 encryption result corresponding to the matching identifier in the encryption results. The specific implementation is similar to the above-mentioned processes of S231-S235, and is not described herein again.

It should be noted that r may also be a public key in the asymmetric key, so that after receiving the result encrypted by r, the client may decrypt the result by using its own private key. In S234 and S235, the server performs asymmetric encryption on the record of ID _0 by using r0, performs asymmetric encryption on the record of ID _1 by using r1, performs asymmetric encryption on the record of ID _ n-1 by using r (n-1), and sends the n encryption results to the client, and after receiving the encryption results, the client may perform asymmetric decryption on the encryption result corresponding to the ID that is expected to be obtained by using its own private key to obtain the result. The following is also similar and will not be repeated.

Based on this, the present specification gives the following one embodiment with an added confusion set of configurations:

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 Age field value is 25, and 25 is a sensitive field, i.e. it is not desirable to let the opposite end know. To avoid letting the server know that the client retrieve condition is the value 25 of the Age field, the client may encrypt this 25. For example, the client side adopts the same encryption algorithm as the server side generates the query base by adopting RSA/ECC private key encryption.

Specifically, under the condition of adopting RSA private key encryption, the client generates secret beta and stores the secret beta properly. Further, the client may encrypt 25 with its own private key β. Specifically, 25 or the hash value of 25 may be encrypted. Here, the hash encryption of 25 is taken as an example, and similarly to the case of directly encrypting 25, the client and the server use the same hash algorithm. For example, the client uses the same large prime q as the server as the modulus. The client can RSA encrypt the hash value of 25 using beta pair 25 to obtain (H (25)) ^β . The sensitive field sent by the client to the server can be (H (25)) ^β Wherein (H (25)) ^β A ciphertext representing a value 25 of the sensitive field.

Under the condition of adopting ECC private key encryption, the client side adopts the elliptic curve which is the same as that of the server side, namely the elliptic curve has the same elliptic curve parameters and generation elements. The client itself generates the secret beta and keeps it properly. Further, the client may encrypt 25 with its own private key β. Specifically, the hash value of 25 may be encrypted, and the client and the server use the same hash algorithm. For example, the client may perform ECC encryption on the hash value of 25 using β to obtain β · H (25). 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, and can include that the server encrypts the sensitive field encrypted by the client again by adopting a self key and sends the encrypted sensitive field to the client, and the client decrypts the sensitive field encrypted twice by adopting the self key to obtain the sensitive field encrypted by the server. The core of the content is to find an encryption algorithm which can perform decryption in an exchange sequence according to two continuous encryption operations (encryption by two parties in sequence). According to the cryptology property of ECC, two parties agree to use the same elliptic curve, namely, the elliptic curve has the same elliptic curve parameter and generator, and each of them holds private key alpha and beta, the encryption operation is scalar multiplication operation by alpha (or beta), and the decryption can be performed in the same or different order regardless of whether alpha encryption is performed first and then beta encryption is performed or beta encryption is performed first and then alpha encryption is performed, namely, the decryption can be performed in different order on the encryption result. Similarly, according to the cryptology property of RSA, two parties agree to use a same large prime number q and primitive root g, which respectively hold private keys alpha and beta, the encryption operation is to use alpha (or beta) to carry out exponentiation and use q to get modulus, and the encryption can be decrypted in the same or different orders regardless of whether alpha encryption is used first and then beta encryption or beta encryption is used first and then alpha encryption, namely, the encryption result can be decrypted in different orders. Overall, here, encryption/decryption algorithms that can exchange orders are adopted by the client and the server for the same target.

The server may re-encrypt the encrypted sensitive field (i.e., the privacy field) and return the re-encrypted sensitive field to the client. In particular, the server may be paired with a privacy field (H (25)) ^β Adopting the private key alpha of the RSA to carry out encryption again to obtain (H (25)) ^β ) ^α 。

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

For example, in case 1 above, the client receives the message ((H (25)) ^β ) ^α The power operation has the following properties: ((H (25)) ^β ) ^α ＝(H(25)) ^βα ＝(H(25)) ^αβ ＝((H(25)) ^α ) Beta is used as the reference. Furthermore, the client can adopt the inverse element of the self private key beta

And decrypting the sensitive field after twice encryption as follows:

S320: and the client retrieves in the query base according to the sensitive field encrypted by the server to obtain the identifier of the matching record.

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

The client may query in a query base based on the sensitive field encrypted by the server. For example, the client solutionAfter encryption, the privacy field alpha.H (25) or (H (25)) ^α Therefore, the client queries in a query base based on the privacy field, for example, queries in table 2 or table 3, respectively, and may obtain the record with ID = d _1, which includes the privacy field, in Age, where ID is the identifier of the record. Therefore, the client queries in the query base based on the privacy field encrypted by the server, and can locate and obtain the identification of the matched record after the record is matched.

S330: and the server returns the value of the field of interest in the record corresponding to the identifier set with the preset size including the matching identifier in the database to the client in an accidental transmission mode.

The sensitive field sent by the client and encrypted by the client in S310 makes the server unable to know which record the sensitive field searched by the client hits, and only the client knows itself. In this way, the privacy of the client is protected. However, the retrieval still needs to be completed finally, which requires the server to return the record that the client wants to query to the client.

The above embodiment corresponding to fig. 2 shows an implementation of n-out-of-1 inadvertent transmission, and here, m-out-of-1 inadvertent transmission may be adopted, where m < n. In S320, the client may also not separately return the ID obtained by matching to the server, but confuse and combine the ID obtained by matching with some other forged IDs to form a confusion set, and send the confusion set to the server, so that the server cannot accurately know which record in the confusion set the client wants to search for, and it is necessary to ensure that the client can only obtain the record to be searched for, but cannot obtain other records. In S320, the confusion set sent by the client may be sent together with the retrieval statement, for example, select Name where ID = confusion set. Alternatively, the confusion set may be sent in S332, which is not limited herein.

In the above embodiment in connection with this specification, it is assumed that the data table of the server has n records in total, and thus, the query base of the client also has n encrypted records correspondingly. For convenience, the IDs of the data records are identified in order as ID _0, ID _1, ID _2,.. ID _ n-1. One simple implementation is as follows:

s331: the server generates n pairs of different public and private key pairs in advance and discloses a public key.

The server generates n different public and private key pairs (pk-sk; pk is public key and represents public key, sk is secret key and represents private key), for example, pk is respectively ₀ -sk ₀ ，pk ₁ -sk ₁ ，pk ₂ -sk ₂ ，...，pk _n-1 -sk _n-1 And publishes the n public keys, i.e. publishes pk ₀ ，pk ₁ ，pk ₂ ，...，pk _n-1 . After the server side publishes the n ordered public keys, the client side can obtain the n public keys.

S332: the client generates an m-sized confusion set containing the expected ID, generates a random number r, encrypts the r by using a public key corresponding to the expected ID, and then sends the r and the confusion set to the server.

Assuming that the client wants to obtain the record of id _1 and does not want the server to know that the record that the client wants to obtain is the record of id _1, an obfuscated set with a size of m is generated, and this obfuscated set when m =4 is, for example: { id _1, id _2, id _3, id _4}.

These 4 ID and public key pairs have, for example, the following correspondence:

pk ₁ ，id_1

pk ₂ ，id_2

pk ₃ ，id_3

pk ₄ ，id_4

the client can adopt pk ₁ And (5) encrypting the r and then sending the encrypted r and the obfuscated set to the server. For example:

in addition, the client can send the confusion set to the server together with the search statement. Thus, the client can adopt pk ₁ After being encrypted, r is sent together with a search statement containing an obfuscated set, for example:

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

here, "|" is used to divide the preceding search sentence and the following encrypted random number, the same applies below.

S333: and after receiving the confusion set and the encrypted r, the server decrypts the encrypted r by using the corresponding m private keys respectively.

The service terminals respectively use the sk ₁ ，sk ₂ ，sk ₃ ，sk ₄ Respectively decrypt through pk ₁ An encrypted random number r. For example, sk for server ₁ Decrypting to obtain r1, using sk ₂ Decrypting to obtain r2, using sk ₃ Decrypting to obtain r3, using sk ₄ Decryption yields r4.

Obviously, only r1 is equal to r, since only sk is used ₁ It is the corresponding pk that is used for decryption ₁ Encrypted; without corresponding pk ₁ Sk of (1) ₂ 、sk ₃ 、sk ₄ The decryption results r2, r3, r4 are not identical to r. Through decryption, the server only obtains the decryption result in the same form, and does not know what the real r is, nor 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, and therefore the server does not know which of the 4 results r1, r2, r3, and r4 obtained by decryption is the true r.

In addition, after the server receives the confusion sets { ID _1, ID _2, ID _3and ID _4}, the server can know that the data which the client wants to acquire is 1 of the 4 IDs in the confusion sets but does not determine which one of the 4 IDs, so that the privacy of the client is protected.

S334: and the server side symmetrically encrypts the specified records in the confusion set by adopting decryption results of corresponding serial numbers, and sends the symmetrically encrypted results to the client side.

For example, the server performs symmetric encryption on the record id _1 by using r1, performs symmetric encryption on the record id _2 by using r2, performs symmetric encryption on the record id _3 by using r3, performs symmetric encryption on the record id _4 by using r4, and sends the 4 symmetric encryption results to the client.

S335: and the client side symmetrically decrypts the encryption result corresponding to the ID expected to be obtained in the symmetric encryption result by adopting the random number r to obtain a retrieval result.

And the client side symmetrically decrypts the encryption result corresponding to the ID expected to be obtained in the symmetric encryption result by using the random number r. Specifically, for example, in S332 above, the client desires to obtain the value of the field of interest in the record/record corresponding to id _1, and the client uses the corresponding public key pk ₁ Encrypting the random number r; in S333, the server uses the corresponding private key sk ₁ Decrypting the decrypted result to obtain r1= r without corresponding pk ₁ Sk of (1) ₂ 、sk ₃ 、sk ₄ The results r2, r3 and r4 obtained by decryption are not the same as r; in S334, the server uses r1, r2, r3, and r4 to symmetrically encrypt the values of the fields of interest in the records/records, i.e., id _1, id _2, id _3, and id _4, respectively, and sends the symmetric encryption result to the client; in S335, the client performs symmetric decryption on the 4 symmetric encryption results by using the random number r. Among the 4 symmetric decryption results, only the encryption result of id _1 is symmetrically encrypted by r, so that only the encryption result of id _1 is decrypted by r to obtain a correct value. Thus, the client can obtain a correct retrieval result, i.e., obtain the value of the field of interest in the corresponding record/corresponding record.

Of course, in order to reduce the amount of computation, the client may perform symmetric decryption on the encrypted result corresponding to the ID expected to be obtained from the 4 symmetric encrypted results only by using the random number r, that is, the client may perform decryption on the encrypted result of ID _1 only by using r, so as to obtain the value of the field of interest in the corresponding record/corresponding record of ID _1, without using r to perform symmetric decryption on the symmetric encrypted results of ID _2, ID _3, and ID _4, because the client may know that the encrypted results are not symmetric encryption performed by using r, and the correct result cannot be obtained even if the symmetric decryption is performed by using r.

S331-S335 described above are merely exemplary implementations. In another implementation, the construction and transmission of the confusion set may be decoupled from the execution of the OT protocol, which is used to transmit keys. Specifically, on one hand, the client may send an m-sized confusion set to the server, and certainly, the client knows that the several in the m-sized confusion set are identifiers of results really intended to be obtained, and on the other hand, the server may generate m symmetric keys, and through selecting an OT of 1 from m, the client may obtain one specified symmetric key, that is, the client obtains a symmetric key corresponding to the identifier really intended to obtain the result. Therefore, the server side can encrypt the records corresponding to the m identifiers in the client side confusion set by adopting the corresponding symmetric keys and then send the encrypted records to the client side, so that the client side decrypts the result really required to be obtained by adopting the correct symmetric key, and the result is obtained. The server side can generate m symmetric keys in advance, so that the key preparation can be completed in batch before OT interaction, and the execution time of the OT protocol is not occupied.

When the number of the matched records retrieved by the client in the query basis is 1, the matched records are inadvertently transmitted by selecting 1 from m, and the server transmits the values of the fields of interest in the m identification corresponding records/corresponding records indicated in the confusion set to the client. Furthermore, the result of a possible match is greater than 1, e.g., k (k > 1), which can be achieved by inadvertent transmission of m-out-of-k. The core of m-to-k oblivious transmission is that a client constructs an m-sized confusion set and sends the confusion set to a server, 1 is constructed into m and n, 1 in the m confusion sets comprises identifications of k records of the matching, such as m =4, k =2, matching identifications are id _1 and id _3, then the constructed confusion set is { { id _1, id_3 }, { id _2 and id _4}, { id _3 and id _4}, and { id _2}, obviously the first one is a subset formed by matching identifications; furthermore, the server generates m symmetric keys, and the client obtains the specified symmetric key through an OT protocol of m-selected-1; the server side encrypts m subsets in the confusion set respectively by using m different symmetric keys to obtain m encryption result subsets, and sends the m encryption result subsets to the client side; the client side decrypts the subset formed by the k matching identifications by using the obtained symmetric key, so that a correct decryption result is obtained. The specific implementation is similar to the process of decoupling the construction and transmission of the confusion set from the execution of the OT protocol and transmitting the key by the OT protocol, and the process is not expanded.

The following introduces a system for implementing private information retrieval in an embodiment of this specification, including a server and a client, where the client and the server perform encryption/decryption on a same target by using an encryption/decryption algorithm that can exchange sequences, and:

in a retrieval process:

the client side retrieves in a query base according to the sensitive field encrypted by the server side to obtain the identification of the matching record;

A server for implementing private information retrieval in an embodiment of this specification is introduced below, where encryption/decryption performed on the same target by the server and a client use encryption/decryption algorithms that can exchange sequences, and:

in a retrieval process:

the server receives the encrypted sensitive field sent by the client, encrypts the sensitive field again and returns the encrypted sensitive field to the client; and the server side and the client side transmit the value of the field of interest in the record/corresponding record corresponding to the preset size identification set containing the matching identification in the database to the client side in an inadvertent transmission mode.

A client for implementing private information retrieval in an embodiment of this specification is introduced below, where encryption/decryption performed on the same target by the client and the server use encryption/decryption algorithms that can exchange orders, and:

in a retrieval process:

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 also retrieves in the query base according to the sensitive field encrypted by the server to obtain the identifier of the matching record; and the client and the server also obtain the value of the field of interest in the record/corresponding record corresponding to the matching identifier in the database in an inadvertent transmission mode.

In the 90 s of the 20 th century, improvements in a technology could clearly distinguish between improvements in hardware (e.g., improvements in circuit structures such as diodes, transistors, switches, etc.) and improvements in software (improvements in process flow). However, as technology advances, many of today's process flow improvements have been seen as direct improvements in hardware circuit architecture. Designers almost always obtain the corresponding hardware circuit structure by programming an improved method flow into the hardware circuit. Thus, it cannot be said that an improvement in the process flow cannot be realized by hardware physical modules. For example, a Programmable Logic Device (PLD), such as a Field Programmable Gate Array (FPGA), is an integrated circuit whose Logic functions are determined by programming the Device by a user. A digital system is "integrated" on a PLD by the designer's own programming without requiring the chip manufacturer to design and fabricate application-specific integrated circuit chips. Furthermore, nowadays, instead of manually manufacturing an Integrated Circuit chip, such Programming is often implemented by "logic compiler" software, which is similar to a software compiler used in program development and writing, but the original code before compiling is also written by a specific Programming Language, which is called Hardware Description Language (HDL), and HDL is not only one but many, such as ABEL (Advanced Boolean Expression Language), AHDL (alternate Hardware Description Language), traffic, CUPL (core universal Programming Language), HDCal, jhddl (Java Hardware Description Language), lava, lola, HDL, PALASM, rhyd (Hardware Description Language), and vhigh-Language (Hardware Description Language), which is currently used in most popular applications. It will also be apparent to those skilled in the art that hardware circuitry for implementing the logical method flows can be readily obtained by a mere need to program the method flows with some of the hardware description languages described above and into an integrated circuit.

The controller may be implemented in any suitable manner, for example, the controller may take the form of, for example, a microprocessor or processor and a computer-readable medium storing computer-readable program code (e.g., software or firmware) executable by the (micro) processor, logic gates, switches, an Application Specific Integrated Circuit (ASIC), a programmable logic controller, and an embedded microcontroller, examples of which include, but are not limited to, the following microcontrollers: ARC 625D, atmel AT91SAM, microchip PIC18F26K20, and Silicone Labs C8051F320, the memory controller may also be implemented as part of the control logic for the memory. Those skilled in the art will also appreciate that, in addition to implementing the controller in purely computer readable program code means, the same functionality can be implemented by logically programming method steps such that the controller is in the form of logic gates, switches, application specific integrated circuits, programmable logic controllers, embedded microcontrollers and the like. Such a controller may thus be considered a hardware component, and the means included therein for performing the various functions may also be considered as a structure within the hardware component. Or even means for performing the functions may be conceived to be both a software module implementing the method and a structure within a hardware component.

The systems, devices, modules or units illustrated in the above embodiments may be implemented by a computer chip or an entity, or by a product with certain functions. One typical implementation device is a server system. Of course, this description does not exclude that, as future computer technology advances, the computer implementing the functionality of the above-described embodiments may be, for example, a personal computer, a laptop computer, a vehicle-mounted human-computer interaction device, a cellular telephone, a camera phone, a smart phone, a personal digital assistant, a media player, a navigation device, an email device, a game console, a tablet computer, a wearable device, or a combination of any of these devices.

Although one or more embodiments of the present description provide method operation steps as described in the embodiments or flowcharts, more or fewer operation steps may be included based on conventional or non-inventive means. The order of steps recited in the embodiments is merely one manner of performing the steps in a multitude of orders and does not represent the only order of execution. When an actual apparatus or end product executes, it may execute sequentially or in parallel (e.g., parallel processors or multi-threaded environments, or even distributed data processing environments) according to the method shown in the embodiment or the figures. The terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, the presence of additional identical or equivalent elements in processes, methods, articles, or apparatus that include the recited elements is not excluded. For example, the use of the terms first, second, etc. are used to denote names, but not to denote any particular order.

For convenience of description, the above devices are described as being divided into various modules by functions, and are described separately. Of course, when implementing one or more of the present description, the functions of each module may be implemented in one or more software and/or hardware, or a module implementing the same function may be implemented by a combination of multiple sub-modules or sub-units, etc. The above-described embodiments of the apparatus are merely illustrative, and for example, the division of the units is only one logical division, and other divisions may be realized in practice, for example, a plurality of units or components may be combined or integrated into another system, or some features may be omitted, or not executed. In addition, the shown or discussed mutual coupling or direct coupling or communication connection may be an indirect coupling or communication connection through some interfaces, devices or units, and may be in an electrical, mechanical or other form.

The description has been described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the description. It will be understood that each flow and/or block of the flowchart illustrations and/or block diagrams, and combinations of flows and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

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

The memory may include forms of volatile memory in a computer readable medium, random Access Memory (RAM) and/or non-volatile memory, such as Read Only Memory (ROM) or flash memory (flash RAM). Memory is an example of a computer-readable medium.

Computer-readable media, including both permanent and non-permanent, removable and non-removable media, may implement the information storage by any method or technology. The 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 Discs (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 a computing device. As defined herein, a computer readable medium does not include a transitory computer readable medium such as a modulated data signal and a carrier wave.

As will be appreciated by one skilled in the art, one or more embodiments of the present description 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 take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.

One or more embodiments of the 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 can 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 memory storage devices.

All the embodiments in the present specification are described in a progressive manner, and the same and similar parts among the embodiments are referred to each other, and each embodiment focuses on the differences from other embodiments. In particular, as for the system embodiment, since it is substantially similar to the method embodiment, the description is relatively simple, and reference may be made to the partial description of the method embodiment for relevant points. In the description of the specification, reference to the description of the term "one embodiment," "some embodiments," "an example," "a specific example," or "some examples," etc., means that a particular feature, structure, material, or characteristic described in connection with the embodiment or example is included in at least one embodiment or example of the specification. In this specification, the schematic representations of the terms used above are not necessarily intended to refer to the same embodiment or example. Furthermore, the particular features, structures, materials, or characteristics described may be combined in any suitable manner in any one or more embodiments or examples. Furthermore, various embodiments or examples and features of different embodiments or examples described in this specification can be combined and combined by one skilled in the art without contradiction.

The above description is merely exemplary of one or more embodiments of the present disclosure and is not intended to limit the scope of one or more embodiments of the present disclosure. Various modifications and alterations to one or more embodiments described herein will be apparent to those skilled in the art. Any modification, equivalent replacement, improvement or the like made within the spirit and principle of the present specification should be included in the scope of the claims.

Claims

1. A method for realizing private information retrieval, a server encrypts a database to obtain a query base, and sends the query base to a client; the client and the server execute encryption/decryption on the same target by adopting encryption/decryption algorithms which can be exchanged in sequence;

in a retrieval process, the method comprises the following steps:

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;

2. The method of claim 1, wherein the client obtains the same sensitive field encrypted by the server through interaction with the server, comprising:

the server side encrypts the sensitive field encrypted by the client side again by adopting the self key and sends the encrypted sensitive field to the client side, and the client side decrypts the sensitive field encrypted twice by adopting the self key to obtain the sensitive field encrypted by the server side.

3. The method as claimed in claim 1, when the total number of records in the database is n, and the number of matching records retrieved by the client in the query base is 1, the server and the client transmit the value of the field of interest in the identifier-corresponding record/corresponding record of the predetermined size including the matching identifier in the database to the client by an inadvertent transmission mode, including:

and transmitting the values of the fields of interest in all the corresponding records/corresponding records of the identifiers including the matching identifiers in the database to the client in an n-to-1 careless transmission mode between the server and the client.

4. The method of claim 3, wherein the step of transmitting the values of the fields of interest in all the identifier mapping records/mapping records including the matching identifier in the database to the client terminal through an n-to-1 inadvertent transmission mode between the server terminal and the client terminal comprises:

the server side encrypts values of interest fields in n records/corresponding records in the data table respectively by using n different keys to obtain n encryption results, and sends the n encryption results to the client side;

and the client side decrypts 1 encryption result corresponding to the matching identifier in the n encryption results sent by the server side by adopting the key corresponding to the matching identifier.

5. The method as claimed in claim 1, when the total number of records in the database is n, and the number of matching records retrieved by the client in the query basis is k, 1-n-k-n, the server and the client transmit the value of the field of interest in the record/corresponding record corresponding to the predetermined size identifier set including the matching identifier in the database to the client in an inadvertent transmission manner, including:

for the server

Encrypting the result, and transmitting the result

And 1 encryption result corresponding to the matching identifier in the encryption results.

6. The method as claimed in claim 1, when the total number of records in the database is n, and the number of matching records retrieved by the client in the query base is 1, the server and the client transmit the value of the field of interest in the record/corresponding record corresponding to the predetermined size identifier set including the matching identifier in the database to the client through an oblivious transmission method, including:

the client constructs an confusion set containing m identifications and sends the confusion set to a server, wherein 1 & lt m & lt n & gt is provided, and the m confusion sets contain the identifications of the matched records;

and transmitting the values of the fields of interest in the m identification corresponding records/corresponding records indicated by the confusion set in the database to the client through an m-to-1 careless transmission mode between the server and the client.

7. The method of claim 6, wherein the transmitting, between the server and the client, the values in the database indicated by the confusion set that identify the fields of interest in the m corresponding records/corresponding records in an m-out-of-1 oblivious transmission manner to the client comprises:

the server side encrypts the values of the interested fields in the m records/corresponding records indicated by the confusion set in the data table respectively by using m different keys to obtain m encryption results, and sends the m encryption results to the client side;

and the client decrypts 1 encryption result corresponding to the matching identifier in the m encryption results sent by the server by using the key corresponding to the matching identifier.

8. The method as claimed in claim 1, when the total number of records in the database is n, and the number of matching records retrieved by the client in the query base is k, the server and the client transmit the value of the field of interest in the record/corresponding record corresponding to the predetermined size identifier set including the matching identifier in the database to the client through an oblivious transmission method, including:

the client constructs an m-sized confusion set and sends the confusion set to a server, wherein 1 & ltn & gt & ltm & gt & ltn & gt is constructed, and 1 subset of the m confusion sets comprises the matched marks of the k records;

the server side encrypts the identifiers corresponding to the m subsets in the confusion set respectively by using m different keys to obtain m encryption result subsets and sends the m encryption result subsets to the client side;

the server generates m keys, and the client obtains the key appointed by the client through an OT protocol of m-selected-1; the server side encrypts m subsets in the confusion set respectively by using m different keys to obtain m encryption result subsets and sends the m encryption result subsets to the client side;

and the client side decrypts the subset consisting of the k matched identifications by using the obtained key so as to obtain a correct decryption result.

9. A method for realizing private information retrieval is characterized in that a server encrypts a database to obtain a query base and sends the query base to a client; the client and the server execute encryption/decryption on the same target by adopting encryption/decryption algorithms which can be exchanged in sequence;

in a retrieval process, the method comprises the following steps:

s1: 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;

s2: the client side searches in a query base according to the sensitive field encrypted by the server side to obtain the identification of the matching record and generate a confusion set with the size of m including the expected ID;

s3: and the server side and the client side transmit the value of the field of interest in the record/corresponding record corresponding to the confusion set in the database to the client side in an accidental transmission mode.

10. The method as claimed in claim 9, when the total number of records in the database is n and the number of matching records retrieved by the client in the query base is 1,m-n, transmitting the value of the field of interest in the corresponding record/corresponding record containing the confusion set in the database to the client by an inadvertent transmission method between the server and the client, comprising:

and transmitting the values of the fields of interest in the m records/corresponding records indicated by the confusion set in the database to the client in an m-to-1 careless transmission mode between the server and the client.

11. The method of claim 10, wherein the transmitting the values of the fields of interest in the m identified corresponding records/corresponding records indicated by the confusion set in the database to the client by m-out-of-1 oblivious transmission between the server and the client comprises:

12. The method of claim 9, when the total number of records in the database is n, and the number of matching records retrieved by the client in the query basis is k, 1-m-n,

the client generates identifiers of 1 subset in m-size confusion sets containing the expected ID, wherein the 1 subset contains the matched k records;

the method for transmitting the value of the field of interest in the record/corresponding record corresponding to the confusion set to the client side by an inadvertent transmission mode comprises the following steps:

the server generates m keys, and the client obtains the key appointed by the client through an OT protocol of m-to-1 selection; the server side encrypts m subsets in the confusion set respectively by using m different keys to obtain m encryption result subsets and sends the m encryption result subsets to the client side;

and the client side decrypts the subset consisting of the k matching identifications by using the obtained key, so that a correct decryption result is obtained.

13. A system for realizing private information retrieval comprises a server and a client, wherein the client and the server execute encryption/decryption on the same target by adopting encryption/decryption algorithms capable of exchanging sequences, and the system comprises:

in a retrieval process:

14. A server for realizing private information retrieval, wherein encryption/decryption executed by the server and a client on the same target adopt encryption/decryption algorithms which can be exchanged in sequence, and the server and the client are characterized in that:

in a retrieval process:

the server receives the encrypted sensitive field sent by the client, encrypts the sensitive field again and returns the encrypted sensitive field to the client; and the server side and the client side transmit the values of the fields of interest in the records/corresponding records corresponding to the preset size identification set containing the matching identification in the database to the client side in an accidental transmission mode.

15. A client for realizing private information retrieval, wherein encryption/decryption executed by the client and a server on the same target adopt encryption/decryption algorithms which can exchange sequences, and the client and the server:

in a retrieval process: