Securing SQL based databases with cryptographic protocols

Patent metadata

Field	Value
Publication number	US-10664604-B2
Application number	US-201615780363-A
Country	US
Kind code	B2
Filing date	Nov 30, 2016
Priority date	Dec 3, 2015
Publication date	May 26, 2020
Grant date	May 26, 2020

Abstract

The subject matter discloses a method operated on a computerizing system comprising generating two secret shares of at least some of the data fields in a database, loading data fields of the database into two database copies, wherein one secret share of the two secret shares is loaded into one database copy and another secret share of the two secret shares is loaded into another database copy, receiving a request to perform a query in the database, processing said query on the database copies, wherein the database fields employed by the query process and the query results remain secret during processing, and revealing the secret query results.

First claim

The invention claimed is:

1. A method operated on a computerizing system having a first server having a first database, a second server having a second database, the method comprising:
generating two secret shares of at least some of the data fields in a database;
encrypting at least some of the data fields in a database using a method based on probabilistic searchable encryption;
loading the two secret shares generated from the data fields of the database and the encrypted data fields into the first database and the second database, wherein one secret share of the two secret shares is loaded into the first database and another secret share of the two secret shares is loaded into the second database and the encrypted data fields are loaded into the first database and the second database;
receiving a request to perform a query in the database, wherein the query comprises an EQUALS clause;
processing the query first via the EQUALS clause by filtering shares of the first database and the second database using the searchable encryption process independently;
processing the rest of said query using a Multi-Party Computation (MPC) process performed on the secret shares held by the servers, wherein the database fields employed by the query process and the query results remain secret during the entire processing; and
revealing the secret query results.

2. The method of claim 1 , further comprises sending secret query results to another secured party, said secured party decrypts the query results.

3. The method of claim 1 , comprising performing an encrypted mix protocol by generating a copy of the database under a different sharing of the database in a random order.

4. The method of claim 1 , wherein the two secret shares become secret using a XOR based method; or using a method based on additive secret sharing; or a method based on probabilistic searchable encryption.

5. The method of claim 1 , further comprising:
preparing a tokenized query tree, wherein said tokenized query tree is a query tree where at least some of the tables' names or arrays' names in the query tree are replaced with tokens;
splitting the part of the values of the search conditions in the tokenized query tree into random shares; and
sending two tokenized query trees for the first server and the second server, wherein the values in the search conditions are shared between the two tokenized query trees.

6. The method of claim 1 , wherein the processing of the query utilizes a secret query tree; or comprises a garbled circuit based MPC process.

7. The method of claim 6 , wherein an auxiliary server processes the query using garbled circuits.

8. The method of claim 6 , wherein the processing of the query uses a secure MPC process.

9. The method of claim 1 , wherein processing of the query comprises creating a copy of the database rearranged in a random order.

10. A computerizing system comprising,
a first server having a first database, a second server having a second database, wherein the first database stores one secret share of data fields of a database and the second database stores a second secret share of the same data fields of the database, wherein at least some of the data fields in the database are encrypted using a method based on probabilistic searchable encryption;
a Multi-Party Computation (MPC) server processing query operations on the database, wherein the data fields remain encrypted during the entire query process, wherein said processing comprises
receiving a request to perform a query in the database, wherein the query comprises an EQUALS clause,
processing the query first via the EQUALS clause by filtering shares of the first database and the second database using the searchable encryption process independently, and
processing the rest of said query using an MPC process performed on the secret shares held by the servers.

11. The computerized system of claim 10 , wherein the first database and the second database comprise encrypted data fields.

12. The computerized system of claim 10 , wherein the MPC server is configured to decrypt the data fields of the query results.

13. The computerized system of claim 10 , wherein the MPC server conducting multiparty computation protocols with the servers comprising the first database and the second database for revealing the data fields.

Assignees

• Unbound Tech Ltd
• Univ Bar Ilan

Inventors

• Lindell Yehuda
• Pe'Er Guy
• Kraitsberg Michael
• Osheter Valery
• Presman Alex

Classifications

• H04L9/085

  Secret sharing or secret splitting, e.g. threshold schemes · CPC title

• G06F16/2455

  Query execution · CPC title

• G06F21/602 Primary

  Providing cryptographic facilities or services · CPC title

• G06F21/6227 Primary

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

• G06F21/60 Primary

  Protecting data · CPC title