METHOD FOR ENCRYPTING DATABASE SUPPORTING COMPOSABLE SQL QUERY

Abstract

Disclosed is a database encryption method supporting composable SQL query, which mainly comprises the following steps: (1) a user encrypting and preprocessing data based on the encryption scheme provided by the present disclosure and uploading an encryption result and preprocessed data to a service provider; (2) setting and uploading a SQL query instructions: the user uploads the query instruction to the service provider according to actual needs, and uploads auxiliary parameters for the query instruction at the same time; (3) data query: the service provider performs SQL query according to the query instruction and auxiliary parameters received from the user, saves a calculation result, updates the data and returns a query result to the user.

Claims

1. A database encryption method supporting composable SQL query, comprising the following steps: step (1) encrypting stored data, wherein a user encrypts and preprocesses his own stored data, and uploads an encryption result and preprocessed data to a service provider who provides software, apparatuses, electronic devices or storage media for running a database to store the data uploaded by the user; and wherein the step (1) comprises the following sub-steps: step (1.1) generating, by the user, random number sets as a row key and a column key of the data for his own data; encrypting, by the user, the data with the row key and the column key based on multiplication encryption, and outputting an encrypted database; step (1.2) uploading, by the user, the encrypted database to the service provider, and selecting any encryption scheme to encrypt and upload the row key generated in step (1.1) to the service provider to implement encrypted storage of the row key, and meanwhile selectively storing the column key locally without encryption as needed or encrypting and uploading the column key to the service provider; step (1.3) preprocessing, by the user, an instruction to generate auxiliary data needed to run the instruction; uploading, by the user, the auxiliary data to the service provider, wherein the service provider is not capable of obtaining any privacy information about the database from the auxiliary data, and the instruction comprises operations of updating, inserting, deleting, adding, searching for a certain specified keyword and querying a specified range; and step (1.4) selecting, by the service provider, a storage form according to an actual situation, wherein the storage form comprises database software, apparatuses, electronic devices or storage media; storing the encrypted data and the auxiliary data based on the storage form, and carrying out execution of subsequent instructions; step (2) setting a composable SQL query instruction, and uploading, by the user, the composable SQL query instruction to the service provider according to actual demands, and uploading auxiliary parameters used for the query instruction; and step (3) running the composable SQL query instruction set in step (2), wherein the service provider runs the query instruction according to the received composable SQL query instruction and the auxiliary parameters from the user, saves a calculation result after the instruction is run, and updates the data and returns a query result to the user.

2. The database encryption method supporting composable SQL query according to claim 1, wherein the step (1.1) is as follows: the user randomly generates two large prime numbers p and q to obtain a large integer N=p.Math.q; the user takes the large integer N as an order of an generator g and finds out the generator g on a finite field Z.sub.N.sub.2; the user takes the randomly generated numbers as the row key and the column key, and encrypts the database by using the row key and the column key, wherein the row key of an i.sup.th row is (r.sub.i, t.sub.i)∈Z.sub.N.sub.2; the column key of a j.sup.th column is (m.sub.j, x.sub.j), where m.sub.j∈Z.sub.N.sub.2, x.sub.j∈Z.sub.N; the row key and the column key meets a requirement that an integer M.sub.(i,j)∈Z.sub.N.sub.2 for any i, j, renders m.sub.jg.sup.r.sup.i.sup.x.sup.j.Math.M.sub.(i,j) mod N.sup.2=1, the integer M.sub.(i,j) is defined as an inverse of N.sup.2 relative to m.sub.jg.sup.r.sup.i.sup.x.sup.j, and is denoted as (m.sub.jg.sup.r.sup.i.sup.x.sup.j).sup.−1; an element yap in the i.sup.th row and the j.sup.th column of the database is encrypted as follows:
c.sub.(i,j)=(N+1).sup.t.sup.i.sup.v.sup.(i,j).Math.(m.sub.jg.sup.r.sup.i.sup.x.sup.j).sup.−1 mod N.sup.2.

3. The database encryption method supporting composable SQL query according to claim 1, wherein the step (1.3) is as follows: for the instructions of deleting and adding, it is not required for the user to generate auxiliary data D; for the instructions of updating and inserting, once a user updates or inserts a row of data, it is required to generate a row key in advance and encrypt and store the row key in the service provider; during updating and inserting, the user downloads the row key generated in advance from the service provider, and obtains the column key from the service provider or locally, so as to decrypt and update the updated data, re-encrypt and upload the data to the service provider or directly encrypt the inserted data and upload the data to the service provider; for the instruction of searching for a certain specified keyword, the user is allowed to select to query whether each row is a same keyword between two columns or to query whether all rows in a certain column are a certain specified keyword; when the user queries whether the same row of two columns is a same keyword, it is required for the user to generate a column of encrypted random numbers α.sub.i(i=1, 2, . . . , n) for each query, and a corresponding column key is (m.sub.α, x.sub.α), and an encryption scheme is E(α.sub.i)=(m.sub.α.Math.g.sup.r.sup.i.sup.x.sup.α).sup.−1.Math.(N+1).sup.t.sup.i.sup.α mod N.sup.2; an encrypted element in each row is 1, and this column is collectively defined as a column S; the column key corresponding to the column S is (m.sub.s, x.sub.s), and an element 1 in the i.sup.th row is encrypted as E(1).sub.i=(m.sub.s.Math.g.sup.r.sup.i.sup.x.sup.s).sup.−1.Math.mod N.sup.2, where m.sub.s has an inverse m.sub.s.sup.−1∈Z.sub.N.sub.2 for N.sup.2, namely m.sub.s.Math.m.sub.s.sup.−1 mod N.sup.2=1; x.sub.s has an inverse x.sub.s.sup.−1∈Z.sub.N for N, namely x.sub.s.Math.x.sub.s.sup.−1 mod N=1; a list of random numbers h.sub.i.sup.e.sup.i(i=1, 2, . . . , n), where h.sub.i is an N.sub.2 order generator on Z.sub.N.sub.1, N.sub.1 is a product of two or more random large prime numbers, and N.sub.2 is any one of the large prime numbers, that is, N.sub.2 is divisible by N.sub.1, e.sub.i is a random integer on Z.sub.N.sub.2; a list of numbers h.sup.e.sup.i.sup..Math.(t.sup.i.sup..Math.α.sup.i .sup.mod N) mod N.sup.2 (i=1, 2, . . . , N); when the user queries whether all rows of a certain column are a certain specified keyword, it is required for the user to generate an additional encrypted column of γ for every query in addition to auxiliary data required for compare the two columns to determine whether each row is a same keyword, that is, an encrypted element of each row is γ, and a corresponding column key is (m.sub.γ, x.sub.γ), and the element in the i.sup.th row is encrypted as E(γ).sub.i=(m.sub.γ.Math.g.sup.r.sup.i.sup.x.sup.γ).sup.−1.Math.(N+1).sup.t.sup.i.sup.γ, where γ is a random number on Z.sub.N, and γ meets a requirement that an inverse γ.sup.−1 ∈Z.sub.N relative to N exists, that is, γ.Math.γ.sup.−1 mod N=1; for the instruction of querying the specified range, the user is allowed to select to compare two columns with each other or to select to compare a column with a same constant to query the specified range; when the user compares two columns with each other, it is required to generate a column of encrypted random numbers α.sub.i(i=1, 2, . . . , n) for each comparison operation, the corresponding column key is (m.sub.α, x.sub.α), and an encryption scheme is E(α.sub.i)=(m.sub.α.Math.g.sup.r.sup.i.sup.x.sup.α).sup.−1.Math.(N+1).sup.t.sup.i.sup.α mod N.sup.2; an encrypted element in each row is 1, and the two columns are collectively defined as a column S; a column key corresponding to the column S is (m.sub.s, x.sub.s), and the element 1 in the i.sup.th row is encrypted as E(1).sub.i=(m.sub.s.Math.g.sup.r.sup.i.sup.x.sup.s).sup.−1.Math.1 mod N.sup.2, where m.sub.s has an inverse of m.sub.s.sup.−1 ∈Z.sub.N.sub.2 relative to N.sup.2, namely m.sub.s.Math.m.sub.s.sup.−1 mod N.sup.2=1; x.sub.s has an inverse of x.sub.s.sup.−1 ∈Z.sub.N relative to N, namely x.sub.s.Math.x.sub.s.sup.−1 mod N=1; a column β.sub.i.Math.t.sub.i.sup.−1 (i=1, 2, . . . , n), a column u.sub.i−β.sub.i.Math.α.sub.i, where t.sub.i.sup.−1 ∈Z.sub.N is an inverse of t.sub.i relative to N, namely t.sub.i.sup.−1.Math.t.sub.i mod N=1, β.sub.i, u.sub.i is a random number on Z.sub.N and satisfies $0 ≪ u_{i} ≪ β_{i} ≪ \frac{N}{2};$ when the user compares a column with the same constant, it is required for the user to generate an additional encrypted column of γ in addition to auxiliary data required for comparing the two columns, that is, the encrypted element in each row is γ, the corresponding column key is (m.sub.γ, x.sub.γ), and the element in the i.sup.th row is encrypted as E(γ).sub.i=(m.sub.γ.Math.g.sup.r.sup.i.sup.x.sup.γ).sup.−1.Math.(N+1).sup.t.sup.i.sup.γ, where γ is a random number on Z.sub.N, and γ meets a requirement that an inverse γ.sup.−1 ∈Z.sub.N relative to N exists, that is, γ.Math.γ.sup.−1 mod N=1.

4. The database encryption method supporting composable SQL query according to claim 1, wherein the step (2) specifically comprises following sub-steps: step (2.1) uploading, by the users, operation instructions to the service provider according to actual business requirements, wherein the operation instructions comprise updating, adding, searching for a certain specified keyword and querying a specified range; step (2.2) calculating, by the users, the auxiliary parameters according to the uploaded instructions, and uploading the auxiliary parameters to the service provider along with the instructions or after receiving a request of the service provider: wherein the step (2.2) is as follows: the user does not need to calculate any auxiliary parameters for the operations of updating, inserting and deleting; for the operation of adding, when a column A and a column B are added, and corresponding column keys are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the column key of a newly generated column C=A+B is calculated and stored by the user; the corresponding calculation mode is (m.sub.C=m.sub.A.Math.m.sub.B mod N.sup.2, x.sub.C=x.sub.A+x.sub.B mod N); the user selects to store the key locally without encryption or encrypt and upload the key to the service provider for storage; for the instruction of searching for a certain specified keyword, the user selects to query whether each row is a same keyword between two columns or to query whether all rows of a certain column are a certain specified keyword; when the user queries whether each row is the same keyword between two columns such as the column A and the column B, and the corresponding column keys are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the user needs to calculate: (I) a column key (m.sub.A′=m.sub.A.Math.m.sub.B.sup.−1.Math.m.sub.α mod N.sup.2, x.sub.A′=x.sub.A−x.sub.B+x.sub.α mod N) of a column A′=A−B+α; (II) calculating the auxiliary parameter ζ=−x.sub.s.sup.−1x.sub.A′ mod N, η=m.sub.A′m.sub.s.sup.ζ mod N.sup.2 to obtain the auxiliary parameter (ζ,η) uploaded by the user at last; when the user queries whether all rows in a certain column such as the column A, are a certain specified keyword such as v, the user needs to calculate: (I) v.Math.γ.sup.−1, where γ is the auxiliary data in step (1.3); (II) the column key (m.sub.γ′=m.sub.γ.sup.v.Math.γ.sup.−1 mod N.sup.2, x.sub.γ′=v.Math.γ.sup.−1.Math.x.sub.γ mod N) of the column γ′=E(γ).sup.v.Math.γ.sup.−1, where the column γ′ is a new column calculated by the service provider from γ, and the i.sup.th element E(γ′).sub.i of the column γ′ is calculated from the i.sup.th element E(γ).sub.i of the column γ: E(γ′).sub.i=E(γ).sub.i.sup.v.Math.γ.sup.−1 mod N.sup.2; (III) the column key (m.sub.A′=m.sub.A.Math.(m.sub.γ′).sup.−1.Math.m.sub.α mod N.sup.2, x.sub.A′=x.sub.A−x.sub.γ′+x.sub.α mod N) of a column A′=A−γ′+α; (IV) calculating the auxiliary parameter P: ζ=−x.sub.s.sup.−1x.sub.A′ mod N, η=m.sub.A′m.sub.s.sup.ζ mod N.sup.2; obtaining the auxiliary parameter (v.Math.γ.sup.−1, ζ, η) uploaded by the user at last; for the instruction of querying a specified range, the user selects to compare the values of two columns with each other or compare the value of a column with the same constant to query the specified range; when the user compares the values between the same rows of the two columns, such as the column A and the column B, and the column keys corresponding to the two columns are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the user needs to calculate: (I) the column key (m.sub.A′=m.sub.A.Math.m.sub.B.sup.−1.Math.m.sub.α mod N.sup.2, x.sub.A′=x.sub.A−X.sub.B+x.sub.α mod N) of the column A′=A−B+α; (2) ζ=−x.sub.s.sup.−1x.sub.A′ mod N, η=m.sub.A′m.sub.s.sup.ζ mod N.sup.2; and obtaining the auxiliary parameter (ζ,η) uploaded by the user at last; wherein when the user compares the values of all rows in a certain column such as the column A, with a same constant such as v, the user needs to calculate: (I) v.Math.γ.sup.−1, where γ is the auxiliary data in step (1.3); (II) calculating the column key (m.sub.γ′=m.sub.γ.sup.v.Math.γ.sup.−1 mod N.sup.2, x.sub.γ′=v.Math.γ.sup.−1.Math.x.sub.γ mod N) of the column γ′, wherein the column γ′ is a new column calculated by the service provider from the column γ, and an i.sup.th row element E(γ′).sub.i of the column γ′ is calculated from the i.sup.th row element E(γ).sub.i of the column γ: E(γ′).sub.i=E(γ).sub.i.sup.v.Math.γ.sup.−1 mod N.sup.2; (III) calculating the column key (m.sub.A′=m.sub.A.Math.(m.sub.γ′).sup.−1.Math.m.sub.α mod N.sup.2, x.sub.A′=x.sub.A−x.sub.γ′+x.sub.α mod N) of the column A′=A−γ′+α; (IV) calculating the auxiliary parameter ζ=−x.sub.s.sup.−1x.sub.A′ mod N, η=m.sub.A′m.sub.s.sup.ζ mod N.sup.2; and obtaining the auxiliary parameter (v.Math.γ.sup.−1, ζ, η) uploaded by the user at last.

5. The database encryption method supporting composable SQL query according to claim 1, wherein the step (3) specifically comprises the following sub-steps: step (3.1) the service provider performing corresponding calculation and operation after receiving the composable SQL query instruction of the user, and putting forward a request for the auxiliary parameters to the user according to the requirements in the calculation or selecting required parameters from the auxiliary parameters uploaded by the user along with the instruction; step (3.2) the service provider carrying out calculation according to the instruction after receiving the auxiliary parameters, saves the calculation result after the instruction is run, updates the data and return the query result to the user.

6. The database encryption method supporting composable SQL query according to claim 5, wherein the step (3.1) is as follows: for the instruction of deleting, the service provider only needs to perform a normal deletion operation and update the database; for operations of insertion and update, when the user encrypts and stores the row key and column key at the service provider, the service provider only needs to return the row key and column key requested by the user and receive the new data uploaded by the user for normal insertion and update; for the operation of addition, when the column A and the column B are added to get a column C, the service provider calculates the i.sup.th row element C.sub.i of the column C as follows: C.sub.i=A.sub.i×B.sub.i(i=1,2,3, . . . n), where A.sub.i and B.sub.i represent the i.sup.th row elements of the column A and the column B, respectively; in the operation of the above instructions, the service provider does not need the user to provide any auxiliary parameters; for the operation of searching for a certain specified keyword, the user selects to query whether each row is the same keyword between two columns or whether all rows in a certain column are a certain specified keyword; when the user queries whether each row is the same keyword between two columns such as the column A and the column B, and the corresponding column keys are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the service provider performs following calculations: (I) calculating a column B′ as follows: an i.sup.th row element B′.sub.i=B.sub.i.sup.N-1 mod N.sup.2 of the column B′, where B.sub.i is the i.sup.th row element of the column B; (II) calculating a column A′ as follows: the i.sup.th row element A′.sub.i=A.sub.i×B′.sub.i×E(α).sub.i mod N.sup.2 of the column A′, where A.sub.i is the i.sup.th row element of the column A and E(α).sub.i is the i.sup.th row element of the column α of the auxiliary data in step (1.3); (III) the service provider requesting the auxiliary parameter P to the user or selects the required parameter from the auxiliary parameters uploaded by the user along with the instruction; when the user queries whether all the rows in a certain column such as the column A, are an external keyword such as v, the service provider directly asks the user for auxiliary parameters or selects the required parameters from the auxiliary parameters uploaded by the user along with the instruction; for the instruction of querying a specified range, the user is allowed to select to compare the values of two columns with each other or the value of a certain column with the same constant to query the specified range; when the user compares the values of two columns such as the column A and the column B, and the corresponding column keys are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the service provider carries out the following calculations: (I) calculating the column B′ as follows: the i.sup.th row element B′.sub.i=B.sub.i.sup.N-1 mod N.sup.2 of the column B′, where B.sub.i is the i.sup.th row element of the column B; (II) calculating the column A′ as follows: the i.sup.th row element A′.sub.i=A.sub.i×B′.sub.i×E(α).sub.i mod N.sup.2 of the column A′, where A.sub.i is the i.sup.th row element of the column A and E(α).sub.i is the i.sup.th row element of the column α of the auxiliary data in step (1.3); (III) the service provider puts forward a request for the auxiliary parameters to the user or selects the required parameters from the auxiliary parameters uploaded by the user along with the instruction; when the user compares the values of all the rows in a certain column such as the column A, with the same constant such as v, the service provider directly puts forward a request for the auxiliary parameters to the user or selects the required parameters from the auxiliary parameters uploaded by the user along with the instruction.

7. The database encryption method supporting composable SQL query according to claim 5, wherein the step (3.2) is as follows: for the operation of searching for a specified keyword, the user selects to query whether each row is the same keyword between two columns or to query whether all rows in a certain column are a certain specified keyword; when the user queries whether each row is the same keyword between two columns such as the column A and the column B, and the corresponding column keys are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the service provider receives the auxiliary parameter (ζ,η) calculated and uploaded by the user in step (2), and carries out the following calculations: (I) calculation of a column a, wherein the i.sup.th row element a.sub.i of the column a is calculated as follows: a.sub.i=A′.sub.i×η×E(1).sub.i.sup.ζ mod N.sup.2, where A′.sub.i is the i.sup.th row element of the column A′ in step (3.1) and E(1).sub.i is the i.sup.th row element of the column S of the auxiliary data in step (1.3); (II) calculation of a column H, wherein the i.sup.th row element H.sub.i of the column H is calculated as follows: H.sub.i=(h.sub.i.sup.e.sup.i).sup.a.sup.i mod N.sub.1, where, h.sub.i.sup.e.sup.i is the i.sup.th row element of the column h of the auxiliary data in step (1.3), N.sub.1 is the N.sub.1 described in step (1.3); (III) comparison of (h.sup.e.sup.i.sup..Math.(t.sup.i.sup..Math.α.sup.i .sup.mod N) mod N.sup.2, H.sub.i), where h.sup.e.sup.i.sup..Math.(t.sup.i.sup..Math.α.sup.i .sup.mod N) mod N.sup.2 is the i.sup.th row element of the column h′ of the auxiliary data in the step (1.3), and when (h.sup.e.sup.i.sup..Math.(t.sup.i.sup..Math.α.sup.i .sup.mod N) mod N.sup.2, H.sub.i) and H.sub.i are equal, elements in the i.sup.th rows of the column A and the column B are equal; when (h.sup.e.sup.i.sup..Math.(t.sup.i.sup..Math.α.sup.i .sup.mod N) mod N.sup.2, H.sub.i) and H.sub.i are not equal, the elements in the i.sup.th rows of the column A and the column B are not equal; when the user queries whether all the rows in a certain column such as the column A, are an external keyword such as v, the service provider receives the auxiliary parameter (v.Math.γ.sup.−1, ζ, η) uploaded by the user and carries out following calculations: (I) calculating the column γ′, where γ′ is a new column calculated by the service provider according to the column γ in the auxiliary data in step (1.3) and the calculated auxiliary parameter P uploaded by the user, and the i.sup.th row element E(γ′).sub.i of the column γ′ is calculated from the i.sup.th row element E(γ).sub.i of the column γ: E(γ′).sub.i=E(γ).sub.i.sup.v.Math.γ.sup.−1 mod N.sup.2; (II) calculating the column A′ as follows: the i.sup.th row element A′.sub.i=A.sub.i×E(γ′).sub.i.sup.N-1×E(α).sub.i mod N.sup.2 of the column A′, where A.sub.i is the i.sup.th row element of the column A and E(α).sub.i is the i.sup.th row element of the column α in the auxiliary data in step (1.3); (III) calculating the column a, wherein the i.sup.th row element of the column a is calculated as follows: a.sub.i=A′.sub.i×η×E(1).sub.i.sup.ζ mod N.sup.2, where A′.sub.i is the i.sup.th row element of the column A′ in step (3.1) and E(1).sub.i is the i.sup.th row element of the column S in the auxiliary data in step (1.3); (IV) calculating the column H, wherein the i.sup.th row element H.sub.i of the column H is calculated as follows: H.sub.i=(h.sub.i.sup.e.sup.i).sup.a.sup.i mod N.sub.1, wherein, h.sub.i.sup.e.sup.i is the i.sup.th row element of the column h in the auxiliary data in step (1.3), and N.sub.1 is the N.sub.1 described in step (1.3); (V) comparing (h.sup.e.sup.i.sup..Math.(t.sup.i.sup.α.sup.i .sup.mod N) mod N.sup.2, H.sub.i), where h.sup.e.sup.i.sup..Math.(t.sup.i.sup.α.sup.i .sup.mod N) mod N.sup.2 is the i.sup.th row element of the column h′ in the auxiliary data in step (1.3); when (h.sup.e.sup.i.sup..Math.(t.sup.i.sup.α.sup.i .sup.mod N) mod N.sup.2, H.sub.i) and H.sub.i are equal, the element in the i.sup.th row of the column A is equal to v; when (h.sup.e.sup.i.sup..Math.(t.sup.i.sup.α.sup.i .sup.mod N) mod N.sup.2, H.sub.i) and H.sub.i are not equal, the element in the i.sup.th row of the column A is not equal to v; for the instruction of querying a specified range, the user selects to compare the values of two columns with each other or the value of a certain column with the same constant to query the specified range; when the user compares the values of the same rows between two columns such as the column A and the column B, and the corresponding column keys of the two columns are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), then the service provider receives the auxiliary parameter P: (ζ,η) uploaded by the user, and carries out the following calculations: (I) calculating the column a, wherein the i.sup.th row element a.sub.i of the column a is calculated as follows: a.sub.i=A′.sub.i×η×E(1).sub.i.sup.ζ mod N.sup.2, where A′.sub.i is the i.sup.th row element of the column A′ in step (3.1) and E(1).sub.i is the i.sup.th row element of the column S in the auxiliary data in step (1.3); (II) calculating the column a′, wherein the i.sup.th row element a′.sub.i of the column a′ is calculated as follows: a′.sub.i=a.sub.i×(β.sub.i.Math.t.sub.i.sup.−1)+u.sub.i−β.sub.iα.sub.i mod N, where β.sub.it.sub.i.sup.−1 is the i.sup.th row element of the column β in the auxiliary data in step (1.3), and u.sub.i−β.sub.iα.sub.i is the i.sup.th row element of the column u in step (1.3); (III) comparing a′.sub.i with $\frac{N}{2},$ wherein when $a_{i}^{'} > \frac{N}{2},$ the element in the i.sup.th row of the column A is smaller; otherwise, the element in the i.sup.th row of the column B is not greater than the element in the i.sup.th row of the column A; when the user compares the values of all rows in a certain column such as the column A, with the same constant such as v, the service provider receives the auxiliary parameter (v.Math.γ.sup.−1, ζ, η) uploaded by the user and carries out the following calculations: (I) calculating the column γ′, wherein γ′ is a new column calculated by the service provider according to the column γ in the auxiliary data in step (1.3) and the calculated auxiliary parameter P uploaded by the user, and the i.sup.th row element E(γ′).sub.i of the column γ′ is calculated from the i.sup.th row element E(γ).sub.i of the column γ: E(γ′).sub.i=E(γ).sub.i.sup.v.Math.γ.sup.−1 mod N.sup.2; (II) calculating the column A′ as follows: the i.sup.th row element A′.sub.i=A.sub.i×E(γ′).sub.i.sup.N-1×E(α).sub.i mod N.sup.2(i=1, 2, . . . , n) of the column A′, where A.sub.i is the i.sup.th row element of the column A and E(α).sub.i is the i.sup.th row element of the column α in the auxiliary data in step (1.3); (III) calculating the column a, wherein the i.sup.th row element a.sub.i of the column a is calculated as follows: a.sub.i=A′.sub.i×η×E(1).sub.i.sup.ζ mod N.sup.2, where A′.sub.i is the i.sup.th row element of the column A′ in step (3.1) and E (1).sub.i is the i.sup.th row element of the column S in the auxiliary data in step (1.3); (IV) calculating the column a′, wherein the i.sup.th row element a′.sub.i of the column a′ is calculated as follows: a′.sub.i=a.sub.i×(β.sub.i.Math.t.sub.i.sup.−1)+u.sub.i−β.sub.iα.sub.i mod N, where β.sub.it.sub.i.sup.−1 is the i.sup.th row element of the column β in the auxiliary data in step (1.3) and u.sub.i−β.sub.iα.sub.i is the i.sup.th row element of the column u in step (1.3); (V) comparing a′.sub.i with $\frac{N}{2},$ wherein if $a_{i}^{'} < \frac{N}{2},$ the element in the i.sup.th row of the column A is not less than v; and if not, the element in the i.sup.th row of the column A is less than v.

Description

DESCRIPTION OF EMBODIMENTS

[0080] In order to make the purpose, technical solution and advantages of this application clearer, the technical solution of this application will be clearly and completely described below with reference to the specific embodiments of this application and the corresponding drawings. Obviously, the described embodiments are only part of, not all of the embodiments of this application. Based on the embodiments in this application, all other embodiments obtained by those skilled in the art without creative labor belong to the scope of protection in this application.

Embodiment 1

[0081] Supposing that a user A of a sales company stores his own data set M in a service provider B, and asks the service provider B not to get any information about M. In addition, the user A requires that the data set M can be operated without revealing privacy (operations include but are not limited to updating, inserting, deleting, adding, searching for specified keywords and querying a specified range, for example returning orders with a transaction volume greater than 5000). To solve this situation, the database encryption method supporting composable SQL query of the present disclosure is used to meet the requirements of the user A, which specifically includes the following steps:

[0082] (1) Encrypting stored data: the user A encrypts and preprocesses data M, and uploads the encryption result and preprocessed data to the service provider B, which provides software, apparatuses, electronic devices or storage media for running a database for storing the data uploaded by the user.

[0083] Specifically, in step (1.1), the user A generates random number sets R and C as a row key and a column key of the database M, respectively; based on multiplication encryption, the user A encrypts data with the keys R and C, and outputs the encrypted database.

[0084] Specifically, the user A randomly generates two large prime numbers p and q to obtain a large integer N=p q; the user takes the large integer N as an order of an generator g and finds out the generator g on a finite field Z.sub.N.sub.2; the user takes the randomly generated numbers as the row key and the column key, and encrypts the database M by using the row key and the column key, wherein the row key of an i.sup.th row is (r.sub.i, t.sub.i) ∈Z.sub.N.sup.2; the column key of a j.sup.th column is (m.sub.j, x.sub.j), where m.sub.j∈Z.sub.N.sub.2, x.sub.j∈Z.sub.N; the row key and column key should ensure that there is an integer M.sub.(i,j) ∈Z.sub.N.sub.2 for any i, j, so that m.sub.ig.sup.r.sup.i.sup.x.sup.i.Math.M.sub.(i,j) mod N.sup.2=1, the integer M.sub.(i,j) is called an inverse of N.sup.2 relative to m.sub.ig.sup.r.sup.i.sup.x.sup.i, and is marked as (m.sub.jg.sup.r.sup.i.sup.x.sup.i).sup.−1; an element v.sub.(i,j) in the i.sup.th row and the j.sup.th column of the database M is encrypted as follows:

c.sub.(i,j)=(N+1).sup.t.sup.i.sup.v.sup.(i,j).Math.(m.sub.jg.sup.r.sup.i.sup.x.sup.i).sup.−1 mod N.sup.2;

[0085] In step (1.2), the user A uploads the encrypted database M to the service provider B; in addition, the user A chooses any safe encryption scheme to encrypt a random number set R and uploads the encrypted random number set R to the service provider B; the user A can also choose to store a random number set C locally without encryption or uploads it with encryption to the service provider B as needed;

[0086] Specifically, in the whole process, assuming that the database has elements of n rows and m columns; in addition to the encrypted database ciphertext, the user A will upload n encrypted row keys to the service provider B at the same time, and store m column keys locally without encryption or upload the m column keys with encryption to the service provider B; any safe encryption scheme, for example AES encryption, may be adopted for the encryption schemes of row keys and column keys; the encrypted database and the encrypted row keys are collectively referred to as the encryption result, and the encryption result is uploaded by the user A to the service provider B for storage; the service provider B cannot obtain any sensitive information about the database M of the user A from the encryption result; if the user A needs to restore the plaintext of the database elements, it needs to download the encryption elements and the corresponding row keys from service provider B at the same time; if the column keys are encrypt and uploaded to the service provider B, the user A needs to download the column keys corresponding to the encryption elements; if that column keys are stored without encryption locally by the user A, then the user A only needs to find the corresponding column keys of the encrypt elements locally; if the user A needs to query a column in the database, the user A needs the column key of this column; if the column key is encrypted and uploaded to the service provider B, the user A needs to download the column key of this column from the service provider B; if the column key is stored without encryption locally by the user A, then the user A only needs to find the column key of this column locally.

[0087] In step (1.3), the user A preprocesses the instruction to generate auxiliary data D required for executing the instruction; the user A uploads the auxiliary data D to the service provider B, and the service provider B cannot obtain any privacy information about the database M from the auxiliary data D; the service provider B must obtain the auxiliary parameter P calculated by the user A before performing the specified operation; the instructions include, but are not limited to, updating, inserting, deleting, adding, searching for specified keywords, querying the specified range, and the like;

[0088] Specifically, for the instructions of deleting and adding, the user A does not need to generate auxiliary data D; for the instructions of updating and inserting, once the user A updates or inserts a row of data, it is necessary to generate a row key in advance and encrypt and store the row key in the service provider B; during updating and inserting, the user A downloads the row key generated in advance from the service provider B, and obtains the column key from the service provider B or locally, so as to decrypt and update the updated data, re-encrypt and upload the data to the service provider B or directly encrypt the inserted data and upload the data to the service provider B; for the instruction of searching for a certain specified keyword, the user A can select whether each row is the same keyword between two columns or whether all rows in a certain column are a certain specified keyword; if the user A queries whether the same row is the same keyword between two columns, the user A needs to generate a column of encrypted random numbers α.sub.i(i=1, 2, . . . , n) (collectively referred to as a column α) for each query, and the corresponding column key is (m.sub.α, x.sub.α), and the encryption scheme is E(α.sub.i)=(m.sub.α.Math.g.sup.r.sup.i.sup.x.sup.α).sup.−1.Math.(N+1).sup.t.sup.i.sup.α mod N.sup.2; the encrypted element in each row is 1, and this column is collectively called a column S; the column key corresponding to the column S is (m.sub.s, x.sub.s), and the element 1 in the i.sup.th row is encrypted as E(1).sub.i=(m.sub.s.Math.g.sup.r.sup.i.sup.x.sup.s).sup.−1.Math.1 mod N.sup.2, where m.sub.s has an inverse m.sub.s.sup.−1 ∈Z.sub.N.sub.2 for N.sup.2, that is m.sub.s.Math.m.sub.s.sup.−1 mod N.sup.2=1; x.sub.s has an inverse x.sub.s.sup.−1 ∈Z.sub.N for N, that is, x.sub.s.Math.x.sub.s.sup.−1 mod N=1; a list of random numbers h.sub.i.sup.e.sup.i(i, =1, 2, . . . , n) ( ) where h.sub.i is a N.sub.2 order generator on Z.sub.N.sub.1, N.sub.1 is product of two or more random large prime numbers, and N.sub.2 is any one of the large prime numbers, that is, N.sub.2 is divisible by N.sub.1, e.sub.i is a random integer on Z.sub.N.sub.2; a list of numbers h.sup.e.sup.i.sup..Math.(t.sup.i.sup..Math.α.sup.i .sup.mod N) mod N.sup.2(i=1, 2, . . . , N) (collectively referred to as a column h′); if 2 (i=the user A queries whether all rows of a certain column are a certain specified keyword, the user A needs to generate an additional encrypted column of γ for every query (i.e., the encrypted elements in each row are γ, and this column is collectively referred to as a column γ) in addition to the auxiliary data needed to compare whether each row is the same keyword between the above two columns, that is, the encrypted element of each row is γ, and the corresponding column key is (m.sub.γ, x.sub.γ), and the element in the i.sup.th row is encrypted as E(γ).sub.i=(m.sub.γ.Math.g.sup.r.sup.i.sup.x.sup.γ).sup.−1.Math.(N+1).sup.t.sup.i.sup.γ, where γ is a random number on Z.sub.N, and γ should guarantee the existence of an inverse γ.sup.−1 ∈Z.sub.N relative to N, that is, γ.Math.γ.sup.−1 mod N=1; for the instruction of querying the specified range, the user A selects two columns to compare with each other or one column to compare with the same constant to query the specified range; if the user compares the two columns, it needs to generate a column of encrypted random numbers α.sub.i(i=1, 2, . . . , n) (collectively referred to as a column α) for each comparison operation, the corresponding column key is (m.sub.α, x.sub.α), and the encryption scheme is E(α.sub.i)=(m.sub.α.Math.g.sup.r.sup.i.sup.x.sup.α).sup.−1.Math.(N+1).sup.t.sup.i.sup.α mod N.sup.2; the encrypted element in each row is 1, and this column is collectively called a column S; the column key corresponding to the column S is (m.sub.s, x.sub.s), and the element 1 in the i.sup.th row is encrypted as E(1).sub.i=(m.sub.s.Math.g.sup.r.sup.i.sup.x.sup.s).sup.−1.Math.1 mod N.sup.2, where m.sub.s has an inverse of m.sub.s.sup.−1 ∈Z.sub.N.sub.2 relative to N.sup.2, that is, m.sub.s.Math.m.sub.s.sup.−1 mod N.sup.2=1; x.sub.s has an inverse of x.sub.s.sup.−1 ∈Z.sub.N relative to N, that is x.sub.s.Math.x.sub.s.sup.−1 mod N=1; a column β.sub.i.Math.t.sub.i.sup.−1 (i=1, 2, . . . , n) (collectively referred to as a column β), a column u.sub.i−β.sub.i.Math.α.sub.i (collectively referred to as a column u), where t.sub.i.sup.−1 ∈Z.sub.N is an inverse of t.sub.i relative to, that is t.sub.i.sup.−1.Math.t.sub.i mod N=1, β.sub.i, u.sub.i is a random number on Z.sub.N and satisfies 0<<u.sub.i<<β.sub.i<<N/2; if the user A compares a column with the same constant, the user needs to generate an additional encrypted column of γ (i.e., the encrypted elements in each row are γ, and this column is collectively referred to as a column γ) in addition to the auxiliary data needed for the comparison between the two columns, that is, the encrypted element in each row is γ, the corresponding column key is (m.sub.γ, x.sub.γ), and the element in the i.sup.th row is encrypted as E(γ).sub.i=(m.sub.γ.Math.g.sup.r.sup.i.sup.x.sup.γ).sup.−1.Math.(N+1).sup.t.sup.i.sup.γ, where γ is a random number on Z.sub.N, and γ should guarantee the existence of an inverse γ.sup.−1 ∈Z.sub.N relative to N, that is, γ.Math.γ.sup.−1 mod N=1.

[0089] The above column α, column S, and column γ of the auxiliary data can be used for instructions of searching for a specified keyword or querying a specified range. All the above auxiliary data should be uploaded to the service provider B before the query instruction is uploaded, and the service provider B can complete the query instruction with the help of the auxiliary data, thus greatly improving the execution efficiency of the query instruction.

[0090] In step (1.4), the service Provider B selects database software, apparatuses, electronic devices or storage media according to the actual situation to store the encrypted M, the random number set R and the auxiliary data D, and performs subsequent instruction execution based on this mode.

[0091] In step (2), a composable SQL query instruction is set, and the user A uploads the instruction to the service provider B according to the actual demand, and calculates and uploads the auxiliary parameter P for executing the instruction.

[0092] Specifically, in step (2.1), the users A uploads operation instructions to the service provider B according to actual business needs; wherein the operation instructions include updating, adding, searching for a certain specified keyword and querying a specified range;

[0093] in step (2.2), the user A calculates the auxiliary parameter P according to the uploaded instruction Q, and uploading the auxiliary parameter P to the service provider B along with the instruction or after receiving a request of the service provider B.

[0094] Specifically, the user A does not need to calculate any auxiliary parameter P for the operations of updating, inserting and deleting; for the operation of adding, if a column A and a column B are added, and the corresponding column keys are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the column key of a newly generated column C=A+B is calculated and stored by the user A; the corresponding calculation mode is (m.sub.C=m.sub.A.Math.m.sub.B mod N.sup.2, x.sub.C=x.sub.A+x.sub.B mod N); the user A chooses to store the key locally without encryption or encrypt and upload the key to the service provider b for storage; for the instruction of searching for a certain specified keyword, the user selects to query whether each row is the same keyword between two columns or whether all rows of a certain column are a certain specified keyword.

[0095] If the user queries whether each row is the same keyword between two columns, for example the column A and the column B, and the corresponding column keys are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the user needs to calculate:

[0096] (I) The column key (m.sub.A′=m.sub.A.Math.m.sub.B.sup.−1.Math.m.sub.α mod N.sup.2, x.sub.A, =X.sub.A−X.sub.B+x.sub.α mod N) of a column A′=A−B+α.

[0097] (II) Calculating the auxiliary parameter P: ζ=−x.sub.s.sup.−1x.sub.A′ mod N, η=M.sub.A′m.sub.s.sup.ζ mod N.sup.2 to obtain the auxiliary parameter P uploaded by the user A at last as (ζ, η).

[0098] If the user A queries whether all rows in a certain column, for example the column A, are a certain specified keyword, for example v, the user A needs to calculate:

[0099] (I) v.Math.γ.sup.−1, where γ is the auxiliary data in step (1.3);

[0100] (II) The column key (m.sub.γ′=m.sub.γ.sup.v.Math.γ.sup.−1 mod N.sup.2, x.sub.γ′=v.Math.γ.sup.−1.Math.x.sub.γ mod N) of the column γ′=E(γ).sup.v.Math.γ.sup.−1, where the column γ′ is a new column calculated by the service provider from γ, and the i.sup.th element E(γ′).sub.i of the column γ′ is calculated from the i.sup.th element E(γ).sub.i of the column γ: E(γ′).sub.i=E(γ).sub.i.sup.v.Math.γ.sup.−1 mod N.sup.2.

[0101] (III) The column key (m.sub.A′=m.sub.A.Math.(m.sub.γ′).sup.−1.Math.m.sub.α mod N.sup.2, x.sub.A′=x.sub.A−x.sub.γ′+x.sub.α mod N) of a column A′=A−γ′+α.

[0102] (IV) Calculating the auxiliary parameter P: ζ=−x.sub.s.sup.−1x.sub.A′ mod N, η=m.sub.A, m.sub.s.sup.ζ mod N.sup.2; obtaining the auxiliary parameter (v.Math.γ.sup.−1, ζ, η) uploaded by the user at last;

[0103] for the instruction of querying a specified range, the user A may select to compare the values of two columns with each other or compare the value of a column with the same constant to query the specified range; if the user A compares the values between the same rows of the two columns, for example the column A and the column B, and the column keys corresponding to the two columns are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the user A needs to calculate:

[0104] (I) The column key (m.sub.A′=m.sub.A.Math.m.sub.B.sup.−1.Math.m.sub.α mod N.sup.2, x.sub.A′=x.sub.A−X.sub.B+x.sub.α mod N) of the column A′=A−B+α; (2) ζ=−x.sub.s.sup.−1x.sub.A′ mod N, η=M.sub.A′m.sub.s.sup.ζ mod N.sup.2; obtaining the auxiliary parameter (ζ,η) uploaded by the user at last.

[0105] If the user A compares the values of all rows in a certain column, for example the column A, with the same constant, for example v, the user A needs to calculate:

[0106] (I) v.Math.γ.sup.−1, where γ is the auxiliary data in step (1.3);

[0107] (II) Calculating the column key (m.sub.γ′=m.sub.γ.sup.v.Math.γ.sup.−1 mod N.sup.2, x.sub.γ′=v.Math.γ.sup.−1.Math.x.sub.γ mod N) of the column γ′, wherein the column γ′ is a new column calculated by the service provider from the column γ, and the i.sup.th row element E(γ′).sub.i of the column γ′ is calculated from the i.sup.th row element E(γ).sub.i of the column γ: E(γ′).sub.i=E(γ).sub.i.sup.v.Math.γ.sup.−1 mod N.sup.2.

[0108] (III) Calculating the column key (m.sub.A′=m.sub.A.Math.(m.sub.γ′).sup.−1.Math.m.sub.α mod N.sup.2, x.sub.A′=x.sub.A−x.sub.γ′+x.sub.α mod N) of the column A′=A−γ′+α.

[0109] (IV) Calculating the auxiliary parameter P: ζ=−x.sub.s.sup.−1x.sub.A′ mod N, η=m.sub.A′m.sub.s.sup.ζ mod N.sup.2; obtaining the auxiliary parameter (v.Math.γ.sup.−1, ζ, η) uploaded by the user at last.

[0110] In step (3), the composable SQL query instruction set in step (2) is run: the service provider B runs the query instruction according to the received composable SQL query instruction and the auxiliary parameter P from the user, saves a calculation result after the instruction is run, updates the data and returns a query result U to the user A, which includes the following sub-steps:

[0111] (3.1) The service provider B performing corresponding calculation and operation after receiving the composable SQL query instruction of the user, and putting forward a request for the auxiliary parameter P to the user A according to the requirements in the calculation or selecting required parameters from the auxiliary parameter P uploaded by the user A along with the instruction.

[0112] Specifically, for the instruction of deleting, the service provider B only needs to perform a normal deletion operation and update the database; for operations of insertion and update, if the user A encrypts and stores the row key and column key at the service provider B, the service provider B only needs to return the row key and column key requested by the user A and receive the new data uploaded by the user A for normal insertion and update; for the operation of addition, if the column A and the column B are added to get a column C, the service provider B calculates the i.sup.th row element C.sub.i of the column C as follows: C.sub.i=A.sub.i×B.sub.i(i=1,2,3, . . . n), where A.sub.i and B.sub.i represent the i.sup.th row elements of the column A and the column B respectively; in the operation of the above instructions, the service provider B does not need the user A to provide any auxiliary parameters.

[0113] For the operation of searching for a certain specified keyword, the user A may select to query whether each row is the same keyword between two columns or whether all rows in a certain column are a certain specified keyword; if the user A queries whether each row is the same keyword between two columns, for example the column A and the column B, and the corresponding column keys are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the service provider B performs the following calculations:

[0114] (I) Calculating a column B′ as follows: the i.sup.th row element B′.sub.i=B.sub.i.sup.N-1 mod N.sup.2 of the column B′, where B.sub.i is the i.sup.th row element of the column B.

[0115] (II) Calculating a column A′ as follows: the i.sup.th row element A′.sub.i=A.sub.i×B′.sub.i×E(α).sub.i mod N.sup.2 of the column A′, where A.sub.i is the i.sup.th row element of the column A and E(α).sub.i is the i.sup.th row element of the column α of the auxiliary data in step (1.3).

[0116] (III) The service provider B requesting the auxiliary parameter P to the user or selects the required parameter from the auxiliary parameter P uploaded by the user A along with the instruction.

[0117] If the user A queries whether all the rows in a certain column, for example the column A, are an external keyword, for example v, the service provider B directly asks the user for auxiliary parameter P or selects the required parameter from the auxiliary parameters P uploaded by the user A along with the instruction.

[0118] For the instruction of querying a specified range, the user A can select to compare the values of two columns with each other or the value of a certain column with the same constant to query the specified range; if the user A compares the values of two columns, for example the column A and the column B, and the corresponding column keys are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the service provider B carries out the following calculations:

[0119] (I) Calculating the column B′ as follows: the i.sup.th row element B′.sub.i=B.sub.i.sup.N-1 mod N.sup.2 of the column B′, where B.sub.i is the i.sup.th row element of the column B.

[0120] (II) Calculating the column A′ as follows: the i.sup.th row element A′.sub.i=A.sub.i×B′.sub.i×E(α).sub.i mod N.sup.2 of the column A′, where A.sub.i is the i.sup.th row element of the column A and E(α).sub.i is the i.sup.th row element of the column α of the auxiliary data in step (1.3).

[0121] (III) The service provider B puts forward a request for the auxiliary parameters P to the user or selects the required parameter from the auxiliary parameter P uploaded by the user A along with the instruction.

[0122] If the user A compares the values of all the rows in a certain column, for example the column A, with the same constant, for example v, the service provider B directly puts forward a request for the auxiliary parameter P to the user or selects the required parameters from the auxiliary parameter P uploaded by the user A along with the instruction.

[0123] In step (3.2) the service provider B carries out calculation according to the instruction after receiving the auxiliary parameter P, saves the calculation result after the instruction is run, updates the data and return the query result U to the user A.

[0124] Specifically, for the operation of searching for a specified keyword, the user A selects to query whether each row is the same keyword between two columns or whether all rows in a certain column are a certain specified keyword; if the user queries whether each row is the same keyword between two columns, for example the column A and the column B, and the corresponding column keys are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), the service provider B receives the auxiliary parameter P: (ζ, η) calculated and uploaded by the user A in step (2), and carries out the following calculations:

[0125] (I) Calculation of a column a, wherein the i.sup.th row element a.sub.i of the column a is calculated as follows: a.sub.i=A′.sub.i×η×E (1).sub.i.sup.ζ mod N.sup.2, where A′.sub.i is the i.sup.th row element of the column A′ in step (3.1) and E(1).sub.i is the i.sup.th row element of the column S of the auxiliary data in step (1.3).

[0126] (II) Calculation of a column H, wherein the i.sup.th row element H.sub.i of the column H is calculated as follows: H.sub.i=(h.sub.i.sup.e.sup.i).sup.a.sup.i mod N.sub.1, where, h.sub.i.sup.e.sup.i is the i.sup.th row element of the column h of the auxiliary data in step (1.3), N.sub.1 is the N.sub.1 described in step (1.3); (III) comparison of (h.sup.e.sup.i.sup..Math.(t.sup.i.sup..Math.α.sup.i .sup.mod N) mod N.sup.2, H.sub.i), where h.sup.e.sup.i.sup..Math.(t.sup.i.sup..Math.α.sup.i .sup.mod N) mod N.sup.2 is the i.sup.th row element of the column h′ of the auxiliary data in the step (1.3), and if they are equal, the elements in the i.sup.th rows of the column A and the column B are equal; if not, the elements in the i.sup.th rows of the column A and the column B are not equal.

[0127] If the user A queries whether all the rows in a certain column, for example the column A, are an external keyword, for example v, the service provider receives the auxiliary parameter P: (v.Math.γ.sup.−1, ζ, η) uploaded by the user and carries out the following calculations:

[0128] (I) Calculation of the column γ′, where γ′ is a new column calculated by the service provider according to the column γ in the auxiliary data in step (1.3) and the calculated auxiliary parameter P uploaded by the user, and the i.sup.th row element E(γ′).sub.i of the column γ′ is calculated from the i.sup.th row element E(γ).sub.i of the column γ: E(γ′).sub.i=E(γ).sub.i.sup.v.Math.γ.sup.−1 mod N.sup.2.

[0129] (II) Calculation of the column A′ as follows: the i.sup.th row element A′.sub.i=A.sub.i×E(γ′).sub.i.sup.N-1×E(α).sub.i mod N.sup.2 of the column A′, where A.sub.i is the i.sup.th row element of the column A and E(α).sub.i is the i.sup.th row element of the column α in the auxiliary data in step (1.3).

[0130] (III) Calculation of the column a, wherein the i.sup.th row element of the column a is calculated as follows: a.sub.i=A′.sub.i×η×E(1).sub.i.sup.ζ mod N.sup.2, where A′.sub.i is the i.sup.th row element of the column A′ in step (3.1) and E(1).sub.i is the i.sup.th row element of the column S in the auxiliary data in step (1.3).

[0131] (IV) Calculation of the column H, wherein the i.sup.th row element H.sub.i of the column H is calculated as follows: H.sub.i=(h.sub.i.sup.e.sup.i).sup.a.sup.i mod N.sub.1, wherein, h.sub.i.sup.e.sup.i is the i.sup.th row element of the column h in the auxiliary data in step (1.3), and N.sub.1 is the N.sub.1 described in step (1.3).

[0132] (V) Comparison of (h.sup.e.sup.i.sup..Math.(t.sup.i.sup..Math.α.sup.i .sup.mod N) mod N.sup.2, H.sub.i), where h.sup.e.sup.i.sup..Math.(t.sup.i.sup..Math.α.sup.i .sup.mod N) mod N.sup.2 is the i.sup.th row element of the column h′ in the auxiliary data in step (1.3); if they are equal, the element in the i.sup.th row of the column A is equal to v; if they are not equal, the element in the i.sup.th row of the column A is not equal to v.

[0133] For the instruction of querying a specified range, the user A may select to compare the values of two columns with each other or the value of a certain column with the same constant to query the specified range; if the user compares the values of the same rows between two columns, for example the column A and the column B, and the corresponding column keys of the two columns are (m.sub.A, x.sub.A) and (m.sub.B, x.sub.B), then the service provider B receives the auxiliary parameter P: (ζ, η) uploaded by the user, and carries out the following calculations:

[0134] (I) Calculation of the column a, wherein the i.sup.th row element a.sub.i of the column a is calculated as follows: a.sub.i=A′.sub.i×η×E (1).sub.i.sup.ζ mod N.sup.2, where A′.sub.i is the i.sup.th row element of the column A′ in step (3.1) and E(1).sub.i is the i.sup.th row element of the column S in the auxiliary data in step (1.3).

[0135] (II) Calculation of the column a′, wherein the i.sup.th row element a; of the column a′ is calculated as follows: a′.sub.i=a.sub.i×(β.sub.i.Math.t.sub.i.sup.−1)+u.sub.i−β.sub.iα.sub.i mod N, where β.sub.it.sub.i.sup.−1 is the i.sup.th row element of the column β in the auxiliary data in step (1.3), and u.sub.i−β.sub.iα.sub.i is the i.sup.th row element of the column u in step (1.3).

[0136] (III) Comparison of a′.sub.i with

[00006] $\frac{N}{2},$

wherein if

[00007] $a_{i}^{'} > \frac{N}{2},$

the element in the i.sup.th row of the column A is smaller; otherwise, the element in the i.sup.th row of the column B is not greater than the element in the i.sup.th row of the column A.

[0137] If the user A compares the values of all rows in a certain column, for example, the column A, with the same constant, for example v, the service provider B receives the auxiliary parameter P: (v.Math.γ.sup.−1, ζ, η) uploaded by the user and carries out the following calculations:

[0138] (I) Calculation of the column γ′, wherein γ′ is a new column calculated by the service provider according to the column γ in the auxiliary data in step (1.3) and the calculated auxiliary parameter P uploaded by the user, and the i.sup.th row element E(γ′).sub.i of the column γ′ is calculated from the i.sup.th row element E(γ).sub.i of the column γ: E(γ′).sub.i=E(γ).sub.i.sup.v.Math.γ.sup.−1 mod N.sup.2.

[0139] (II) Calculation of the column A′ as follows: the i.sup.th row element A′.sub.i=A.sub.i×E(γ′).sub.i.sup.N-1×E(α).sub.i mod N.sup.2(i=1, 2, . . . , n) of the column A′, where A.sub.i is the i.sup.th row element of the column A and E(α).sub.i is the i.sup.th row element of the column α in the auxiliary data in step (1.3).

[0140] (III) Calculation of the column a, wherein the i.sup.th row element a.sub.i of the column a is calculated as follows: a.sub.i=A′.sub.i×η×E(1).sub.i.sup.ζ mod N.sup.2, where A′.sub.i is the i.sup.th row element of the column A′ in step (3.1) and E(1).sub.i is the i.sup.th row element of the column S in the auxiliary data in step (1.3).

[0141] (IV) Calculation of the column a′, wherein the i.sup.th row element a; of the column a′ is calculated as follows: a′.sub.i=a.sub.i×(β.sub.i.Math.t.sub.i.sup.−1)+u.sub.i−β.sub.iα.sub.i mod N, where β.sub.it.sub.i.sup.−1 is the i.sup.1 row element of the column β in the auxiliary data in step (1.3) and u.sub.i−β.sub.iα.sub.i is the i.sup.th row element of the column u in step (1.3).

[0142] (V) Comparison of a′.sub.i with

[00008] $\frac{N}{2},$

wherein if

[00009] $a_{i}^{'} < \frac{N}{2},$

the element in the i.sup.th row of the column A is not less than v; otherwise, the element in the i.sup.th row of the column A is less than v.

Embodiment 2

[0143] The present disclosure discloses a system for encrypting a database supporting composable SQL query, which can perform the functions of safely storing user data and supporting updating, inserting, deleting, adding, searching for a specified keyword and querying a specified range for user data provided by any embodiment of the present disclosure. The system for encrypting a database supporting composable SQL query includes a user device module and a service provider module; the user device module encrypts and preprocesses user data, and uploads the encryption result and preprocessed data to the service provider module; the user module executes data operation instructions, and uploads operation instructions to the service provider module according to actual requirements, wherein the operation instructions include updating, inserting, deleting, adding, searching for a specified keyword and querying a specified ranges, and uploads auxiliary parameter operation instructions to the service provider module, wherein the auxiliary parameter operation instructions include updating, inserting, deleting, adding, searching for a specified keyword and querying a specified range; the service provider module runs the instruction according to the received operation instruction and the auxiliary parameter, stores the calculation result after the instruction is run, updates the data and returns the query result to the user module.

Embodiment 3

[0144] In the field of database, an enterprise runs the database test international standard TPC-C for trading, that is, a certain warehouse accepts orders from multiple users at the same time, and the warehouse has multiple transactions with these users at the same time. In order to save memory and improve performance, the warehouse encrypts transaction data and stores it in the cloud. According to the demand of real-time transactions, the warehouse continuously submits SQL instructions to the encrypted data in the cloud (instructions include updating, inserting, deleting, adding, searching for a specified keyword and querying a specified range).

[0145] According to the meaning of the instructions for actual transactions, the instructions are divided into five sets:

[0146] 1. New-Order: the customer enters a new order transaction.

[0147] 2. Payment: update the customer's account balance and reflect its payment status.

[0148] 3. Delivery: delivery (simulated batch transaction).

[0149] 4. Order-Status query: query the status of customers' recent transactions.

[0150] 5. Stock-Level query: query the stock level of the warehouse so as to replenish the goods in time.

[0151] In this embodiment, a server with two 2.5 GHz Intel Xeon Gold 6248 processors and 256 GB memory is used to simulate the cloud service provider, and the method of the present disclosure is used to execute the five sets of instructions respectively, and the time spent is shown in Table 1.

TABLE-US-00001 TABLE 1 Time consumed Time consumed Time consumed for one for two for three Transaction operation/ms operations/ms opeartions/ms New-Order 192023 411606 614116 Payment 136020 275803 417246 Delivery 422247 843313 1286638 Order-Status 346161 690062 1051611 Stock-Level 101926 204299 293828

[0152] As shown in Table 1 above, the present disclosure supports the execution of five TPC-C transactions. When the five TPC-C transactions are completed once, the shortest time used by the present disclosure is 101 seconds, and the longest time is only 422 seconds (Delivery transactions). As each TPC-C transaction consists of dozens of SQL query instructions, it can be seen that in actual commercial activities, even if the transmission delay is considered, the present disclosure can still be completed in about 10 seconds. In addition, with the increase of the number of executions, the time of the present disclosure is always stable, so it can maintain stable performance in actual commercial activities. Therefore, by using the method of the present disclosure, the database runs faster, consumes less time and runs stably. To sum up, based on the discrete logarithm problem, the present disclosure realizes the encryption protection of user data and reduces the leakage of user privacy information, thus providing a safe and complete protection solution for cloud storage of user data in actual commercial activities; according to the present disclosure, the composable SQL query instructions can be safely and efficiently executed on encrypted data, and the instructions include updating, inserting, deleting, adding, searching for a specified keyword and querying a specified range, so that the requirements of users for remote operation and query of cloud storage data in actual commercial activities are met; the present disclosure has the advantages of strong universality, safety and high efficiency, privacy protection, simple and convenient use, high efficiency, less memory and time consumption and the like.

[0153] The steps of the method or algorithm described combined with the embodiments of the present disclosure may be implemented in a hardware manner, or may be implemented in a manner in which a processor executes software instructions. The software instructions may consist of corresponding software modules, and the software modules can be stored in Random Access Memory (RAM), flash memory, Read Only Memory (ROM), Erasable Programmable ROM (EPROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), registers, hard disks, removable hard disks, CD-ROMs or any other forms of storage media well-known in the art. An exemplary storage medium is coupled to the processor, such that the processor can read information from, and write information to, the storage medium. The storage medium can also be an integral part of the processor. The processor and storage medium may reside in an Application Specific Integrated Circuit (ASIC). Alternatively, the ASIC may be located in a node device, such as the processing node described above. In addition, the processor and storage medium may also exist in the node device as discrete components.

[0154] It should be noted that when the data compression apparatus provided in the foregoing embodiment performs data compression, division into the foregoing functional modules is used only as an example for description. In an actual application, the foregoing functions can be allocated to and implemented by different functional modules based on a requirement, that is, an inner structure of the apparatus is divided into different functional modules, to implement all or some of the functions described above. For details about a specific implementation process, refer to the method embodiment. Details are not described herein again.

[0155] All or some of the foregoing embodiments may be implemented by using software, hardware, firmware, or any combination thereof. When the software is used for implementation, all or some of the embodiments may be implemented in a form of a computer program product. The computer program product includes one or more computer instructions. When the computer program instructions are loaded and executed on a server or a terminal, all or some of the procedures or functions according to the embodiments of this application are generated. The computer instructions may be stored in a computer-readable storage medium or may be transmitted from a computer-readable storage medium to another computer-readable storage medium. For example, the computer instructions may be transmitted from a web site, computer, server, or data center to another web site, computer, server, or data center in a wired (for example, a coaxial optical cable, an optical fiber, or a digital subscriber line) or wireless (for example, infrared, radio, or microwave) manner. The computer-readable storage medium may be any usable medium accessible by a server or a terminal, or a data storage device, such as a server or a data center, integrating one or more usable media. The usable medium may be a magnetic medium (for example, a floppy disk, a hard disk, or a magnetic tape), an optical medium (for example, a digital video disk (DVD)), or a semiconductor medium (for example, a solid-state drive).

[0156] What is described above is only preferred embodiments of the present disclosure, and it is not intended to limit the present disclosure. Any modifications, equivalents, improvements and the like made within the spirit and principle of the present disclosure shall be included in the scope of protection of the present disclosure.

METHOD FOR ENCRYPTING DATABASE SUPPORTING COMPOSABLE SQL QUERY

Inventors

Cpc classification

Classification Explorer

G06F2221/2107

PHYSICS

Classification Explorer

G06F21/6227

PHYSICS

Classification Explorer

H04L9/14

ELECTRICITY

Classification Explorer

H04L9/0869

ELECTRICITY

Classification Explorer

H04L9/008

ELECTRICITY

International classification

Classification Explorer

G06F21/62

PHYSICS

Classification Explorer

H04L9/08

ELECTRICITY

Abstract

Claims

Description