Method for encrypting database supporting composable SQL query

Patent metadata

Field	Value
Publication number	US-11734448-B2
Application number	US-202217888521-A
Country	US
Kind code	B2
Filing date	Aug 16, 2022
Priority date	Aug 3, 2021
Publication date	Aug 22, 2023
Grant date	Aug 22, 2023

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.

First claim

What is claimed is:

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·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 N 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 th row is (r i , t i )∈Z N 2 ; the column key of a j th column is (m j , x j ), where m j ∈Z N 2 , x j ∈Z N ; the row key and the column key meets a requirement that an integer M (i,j) ∈Z N 2 for any i, j, renders m j g r i x j ·M (i,j) mod N 2 =1, the integer M (i,j) is defined as an inverse of N 2 relative to m j g r i x j , and is denoted as (m j g r i x j ) −1 ; an element yap in the i th row and the j th column of the database is encrypted as follows:
c (i,j) =( N+ 1) t i v (i,j) ·( m j g r i x j ) −1 mod N 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 α i (i=1, 2, . . . , n) for each query, and a corresponding column key is (m α , x α ), and an encryption scheme is E(α i )=(m α ·g r i x α ) −1 ·(N+1) t i α mod N 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 s , x s ), and an element 1 in the i th row is encrypted as E(1) i =(m s ·g r i x s ) −1 ·mod N 2 , where m s has an inverse m s −1 ∈Z N 2 for N 2 , namely m s ·m s −1 mod N 2 =1; x s has an inverse x s −1 ∈Z N for N, namely x s ·x s −1 mod N=1; a list of random numbers h i e i (i=1, 2, . . . , n), where h i is an N 2 order generator on Z N 1 , N 1 is a product of two or more random large prime numbers, and N 2 is any one of the large prime numbers, that is, N 2 is divisible by N 1 , e i is a random integer on Z N 2 ; a list of numbers h e i ·(t i ·α i mod N) mod N 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 γ , x γ ), and the element in the i th row is encrypted as E(γ) i =(m γ ·g r i x γ ) −1 ·(N+1) t i γ , where γ is a random number on Z N , and γ meets a requirement that an inverse γ −1 ∈Z N relative to N exists, that is, γ·γ −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 α i (i=1, 2, . . . , n) for each comparison operation, the corresponding column key is (m α , x α ), and an encryption scheme is E(α i )=(m α ·g r i x α ) −1 ·(N+1) t i α mod N 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 s , x s ), and the element 1 in the i th row is encrypted as E(1) i =(m s ·g r i x s ) −1 ·1 mod N 2 , where m s has an inverse of m s −1 ∈Z N 2 relative to N 2 , namely m s ·m s −1 mod N 2 =1; x s has an inverse of x s −1 ∈Z N relative to N, namely x s ·x s −1 mod N=1; a column β i ·t i −1 (i=1, 2, . . . , n), a column u i −β i ·α i , where t i −1 ∈Z N is an inverse of t i relative to N, namely t i −1 ·t i mod N=1, β i , u i is a random number on Z N and satisfies

0
≪

u
i

Assignees

• Univ Zhejiang

Inventors

• Liu Jian
• Cao Xinle
• Lu Hao
• Ren Kui

Classifications

• G06F21/6227 Primary

  where protection concerns the structure of data, e.g. records, types, queries · CPC title

• H04L9/0869

  involving random numbers or seeds · CPC title

• G06F2221/2107

  File encryption · CPC title

• H04L9/14

  using a plurality of keys or algorithms · CPC title

• H04L9/008

  involving homomorphic encryption · CPC title