System and method for multiple-character wildcard search over encrypted data

Patent metadata

Field	Value
Publication number	US-2020159779-A1
Application number	US-201816195733-A
Country	US
Kind code	A1
Filing date	Nov 19, 2018
Priority date	Nov 19, 2018
Publication date	May 21, 2020
Grant date	—

Abstract

A method and system for searching encrypted data using wildcard keywords. The method includes: obtaining, by a first computing device, a keyword for data to be encrypted, where the keyword has a fixed length; generating a sequence of primes; determining corresponding one prime from the sequence of primes for each character of the keyword; and defining a product of the corresponding primes of the characters of the keyword as index of the encrypted data, where the index can be searched using a wildcard search keyword.

First claim

What is claimed is:

1 . A method for providing wildcard keyword search upon encrypted data, comprising:
providing, by a first computing device, a data encryption key (DEK); providing, by the first computing device, data for being encrypted, wherein the data comprises a keyword having M number of characters, each of the characters is selected from N number of predetermined characters, and M and N are positive integers; encrypting, by the first computing device, the data into encrypted data using the DEK; calculating, by the first computing device, an index encryption key (IEK) from the DEK using a key derivation function (KDF); providing M×N number of primes; shuffling the M×N number of primes based on the IEK to form a sequence of primes; calculating, for each character in the keyword, a sequential value according to a position of the character in the keyword and a value of the character in the keyword; selecting a prime from the sequence of primes for each character in the keyword according to the sequential value; calculating an index of the keyword, the index being a product of the primes selected for the characters of the keyword; and uploading the encrypted data and the index on the second computing device, such that the encrypted data and the index are accessible by a third computing device, wherein the third computing device has the DEK and KDF, and is configured to:
generate the IEK according to the DEK and the KDF;
provide a wildcard search keyword, wherein the wildcard search keyword has M number of characters, the M number of characters comprises at least one query character and at least one wildcard character, and the at least one query character is selected from the N number of predetermined characters;
provide the M×N number of primes;
shuffle the M×N number of primes based on the IEK to form the sequence of primes;
calculate a query sequential value for the at least one query character according to a position and a value of the at least one query character in the wildcard search query;
select a prime from the sequence of primes for the at least one query character in the wildcard search keyword according to the query sequential value;
calculate a query index of the wildcard search keyword, the query index being a product of the primes selected for the at least one query character of the wildcard search keyword; and
query the index stored in the second computing device using the query index, so as to obtain the encrypted data corresponding to the index that matches the query index.

2 . The method of claim 1 , wherein the sequential value for a character in a pth position in the keyword is calculated by: p×(M−1)+C % N, wherein p is an integer selected from 0 to N and representing a position of the character in the keyword, C is the character value in the pth position, and C % N is a remainder of dividing C by N.

3 . The method of claim 1 ,
wherein the first computing device is a data provider, the second computing device is a storage server, and the third computing device is a data consumer; and wherein the first computing device is configured to perform storage operations to the second computing device, and the third computing device is configured to send the query index to the second computer and receive a search response from the second computing device.

4 . The method of claim 1 , further comprising: updating the DEK on the first computing device and the second computing device at a predetermined time interval.

5 . The method of claim 1 , wherein the DEK is an advanced encryption standard (AES) key, and the KDF is a SHA-256 hash value function.

6 . The method of claim 1 , wherein the N number of predetermined characters comprises at least one of numbers 0 to 9, lowercase characters a to z, and uppercase characters A to Z.

7 . The method of claim 1 , wherein the step of shuffling the M×N number of primes is performed by Fisher-Yates shuffle using the IEK as seeds.

8 . The method of claim 1 , wherein the step of query the index comprises:
performing a modulus operation on the query index to the indexes stored in the second computing device; and when the modulus of the query index and one of the indexes stored in the second computing device is 0, delivering the encrypted data corresponding to the one of the indexes from the second computing device to the third computing device.

9 . A method for providing wildcard keyword search upon encrypted data, comprising:
obtaining, by a first computing device, a keyword for data to be encrypted, wherein the keyword has a fixed length; generating a sequence of primes; determining corresponding one prime from the sequence of primes for each character of the keyword; and defining a product of the corresponding primes of the characters of the keyword as index of the encrypted data, wherein the index is searchable using a wildcard search keyword.

10 . The method of claim 9 , wherein the keyword has M number of characters, each of the characters is selected from N number of predetermined characters, M and N are positive integers, and the sequence of primes comprises M×N number of primes.

11 . The method of claim 10 , further comprising:
encrypting the data using a data encryption key (DEK) to obtain the encrypted data; processing the DEK using a key derivation function (KDF) to obtain an index encryption key (IEK); obtaining sequentially increasing M×N number of primes from 1; and shuffling the sequentially increasing M×N number of primes, using random shuffling with the IEK as seeds, to obtain the sequence of primes.

12 . The method of claim 11 , wherein the step of determining corresponding one prime from the sequence of primes for each character of the keyword comprises:
calculating, for each character in the keyword, a sequential value using p×(M−1)+C % N, wherein p is an integer selected from 0 to N and representing a position of the character in the keyword, C is the character value in the pth position, and C % N is a remainder of dividing C by N; and selecting, for each character in the keyword, a prime at a position of the sequential value in the sequence of primes.

13 . The method of claim 12 , wherein the wildcard search keyword has M number of characters, the M number of characters comprises at least one query character and at least one wildcard character, and the at least one query character is selected from the N number of predetermined characters.

14 . The method of claim 13 , further comprising:
uploading the index and the encrypted data onto a storage serer; calculating a query sequential value for at least one query character of the wildcard search keyword according to a position and a value of the at least one query character in the wildcard search keyword; calculating a query index of the wildcard keyword, the query index being a product of the primes selected for the at least one query character of the wildcard search keyword; and querying the index on the storage server using the query index.

15 . The method of claim 14 , further comprising, when the query index matches the index on the storage server: downloading encrypted data corresponding to the index.

16 . A non-transitory computer readable medium storing computer executable code, wherein the computer executable code, when executed at a processor of a computing device, is configured to perform the method of claim 9 .

17 . A system for providing wildcard keyword search upon encrypted data, the system comprising a first computing device, the first computing device comprisi

Assignees

• Beijing Jingdong Shangke Information Technology Co Ltd
• Jd Com American Tech Corp

Inventors

• Dong Qiuxiang
• Lin Yueh-Hsun
• Gao Wei
• Su Jimmy

Classifications

• G06F16/313

  Selection or weighting of terms for indexing · CPC title

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title

• G06F16/90335 Primary

  Query processing · CPC title

• H04L9/0631 Primary

  Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms · CPC title

• G06F16/90344

  by using string matching techniques · CPC title