Method and system for search pattern oblivious dynamic symmetric searchable encryption

Patent metadata

Field	Value
Publication number	US-11144663-B2
Application number	US-201716474712-A
Country	US
Kind code	B2
Filing date	Dec 28, 2017
Priority date	Dec 30, 2016
Publication date	Oct 12, 2021
Grant date	Oct 12, 2021

Abstract

An oblivious encrypted search and update method includes transmitting encrypted search queries and encrypted file update requests from a trusted client to at least two different untrusted servers, receiving encrypted search entries and encrypted file entries from the untrusted servers, and decrypting the encrypted search entries and encrypted file entries with the trusted client. The trusted client re-encrypts the decrypted entries and transmits re-encrypted entries that were received from a first untrusted server to a second untrusted server and vice versa to provide obliviousness for encrypted keyword searches and encrypted file updates from the trusted client.

First claim

What is claimed:

1. A method for searching and updating encrypted data comprising:
generating, with a trusted client, a first encrypted search query for a first keyword and a first encrypted file update request for a first encrypted file;
generating, with the trusted client, a second encrypted search query for a second keyword that is different than the first keyword and a second encrypted file update request for a second encrypted file that is different than the first encrypted file;
transmitting, with the trusted client, the first encrypted search query and the first encrypted file update request to a first untrusted server;
transmitting, with the trusted client, the second encrypted search query and the second encrypted file update request to a second untrusted server, the second untrusted server being different than the first untrusted server;
receiving, with the trusted client, a first encrypted search entry corresponding to the first encrypted search query and a first encrypted file entry corresponding to the first encrypted file update request from the first untrusted server;
receiving, with the trusted client, a second encrypted search entry corresponding to the second encrypted search query and a second encrypted file entry corresponding to the second encrypted file update request from the second untrusted server;
decrypting, with the trusted client, the first encrypted search entry and the first encrypted file entry using a plurality of cryptographic keys associated with the first untrusted server to generate a first decrypted search entry and a first decrypted file entry;
decrypting, with the trusted client, the second encrypted search entry and the second encrypted file entry using a plurality of cryptographic keys associated with the second untrusted server to generate a second decrypted search entry and a second decrypted file entry;
generating, with the trusted client, a first re-encrypted search entry corresponding to the first keyword based on the first decrypted search entry and a first re-encrypted file entry corresponding to a first file identifier based on the first decrypted file entry using the plurality of cryptographic keys associated with the second untrusted server;
generating, with the trusted client, a second re-encrypted search entry corresponding to the second keyword based on the second decrypted search entry and a second re-encrypted file entry corresponding to a second file identifier based on the second decrypted file entry using the plurality of cryptographic keys associated with the first untrusted server;
transmitting, with the trusted client, the second re-encrypted search entry and the second re-encrypted file entry to the first untrusted server to update a first encrypted search index stored in the first untrusted server; and
transmitting, with the trusted client, the first re-encrypted search entry and the first re-encrypted file entry to the second untrusted server to update a second encrypted search index stored in the second untrusted server.

2. The method of claim 1 further comprising:
generating, with the trusted client, a third encrypted search query for a third keyword that is different than the first keyword and the second keyword and a third encrypted file update request for a third encrypted file that is different than the first encrypted file and the second encrypted file;
generating, with the trusted client, a fourth encrypted search query for a fourth keyword that is different than the first keyword, the second keyword, and the third keyword and a fourth encrypted file update request for a fourth encrypted file that is different than the first encrypted file, the second encrypted file, and the third encrypted file;
transmitting, with the trusted client, the third encrypted search query and the third encrypted file update request to the first untrusted server with the first encrypted search query and the first encrypted file update request;
transmitting, with the trusted client, the fourth encrypted search query and the fourth encrypted file update request to the second untrusted server with the second encrypted search query and the second encrypted file update request;
receiving, with the trusted client, a third encrypted search entry corresponding to the third encrypted search query and a third encrypted file entry corresponding to the third encrypted file update request from the first untrusted server;
receiving, with the trusted client, a fourth encrypted search entry corresponding to the fourth encrypted search query and a fourth encrypted file entry corresponding to the fourth encrypted file update request from the second untrusted server;
decrypting, with the trusted client, the third encrypted search entry and the third encrypted file entry using the plurality of cryptographic keys associated with the first untrusted server to generate a third decrypted search entry and a third decrypted file entry;
decrypting, with the trusted client, the fourth encrypted search entry and the fourth encrypted file entry using the plurality of cryptographic keys associated with the second untrusted server to generate a fourth decrypted search entry and a fourth decrypted file entry;
generating, with the trusted client, a third re-encrypted search entry corresponding to the third keyword based on the third decrypted search entry and a third re-encrypted file entry corresponding to a third file identifier based on the third decrypted file entry using the plurality of cryptographic keys associated with the second untrusted server;
generating, with the trusted client, a fourth re-encrypted search entry corresponding to the fourth keyword based on the fourth decrypted search entry and a fourth re-encrypted file entry corresponding to a fourth file identifier based on the fourth decrypted file entry using the plurality of cryptographic keys associated with the first untrusted server;
transmitting, with the trusted client, the third re-encrypted search entry and the third re-encrypted file entry to the second untrusted server with the first re-encrypted search entry and the first re-encrypted file entry to update the second encrypted search index stored in the second untrusted server; and
transmitting, with the trusted client, the fourth re-encrypted search entry and the fourth re-encrypted file entry to the first untrusted server with the second re-encrypted search entry and the second re-encrypted file entry to update the first encrypted search index stored in the first untrusted server.

3. The method of claim 1 further comprising:
updating, with the trusted client, a counter stored in an index in a memory of the trusted client;
generating, with the trusted client, a first updated encryption key corresponding to the first keyword based on a symmetric key associated with the second untrusted server, a hash of the first keyword, and the counter;
generating, with the trusted client, a second updated encryption key corresponding to the second keyword based on a symmetric key associated with the first untrusted server, a hash of the second keyword, and an updated second keyword counter;
generating, with the trusted client, the first re-encrypted search entry corresponding to the first keyword based on the first decrypted search entry using the first updated encryption key; and
generating, with the trusted client, the second re-encrypted search entry corresponding to the second keyword based on the second decrypted search entry using the second updated encryption key.

4. The method of claim 3 further comprising:
generating, with the trusted client, the first re-encrypted file entry corresponding to the first keyword based on the first decrypted file entry and a first updated file counter using the plurality of cryptographic keys associated with the second untrusted server, th

Assignees

• Bosch Gmbh Robert

Inventors

• Yavuz Attila
• Merchan Jorge Guajardo
• Hoang Thang

Classifications

• G06F21/6227 Primary

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

• G06F21/602 Primary

  Providing cryptographic facilities or services · CPC title

• H04L9/00 Primary

  {Cryptographic mechanisms or cryptographic} arrangements for secret or secure communications; Network security protocols · CPC title

• G06F21/606

  by securing the transmission between two devices or processes · CPC title

• H04L9/14

  using a plurality of keys or algorithms · CPC title