×

Wildcard search in encrypted text using order preserving encryption

  • US 9,760,637 B2
  • Filed: 09/11/2015
  • Issued: 09/12/2017
  • Est. Priority Date: 09/11/2015
  • Status: Active Grant
First Claim
Patent Images

1. A method for performing wildcard search of encrypted cloud stored data comprising:

  • receiving, at a network intermediary, a document destined for a cloud service provider;

    encrypting, at a network intermediary, the document using a document encryption algorithm;

    generating a set of permuted keyword strings for each of some or all of the keywords in the document, the set of permuted keyword strings for each keyword being generated by adding a first character delimiter before the first character of the keyword and applying cyclic rotation of the characters of the keyword, including the first character delimiter;

    encrypting the permuted keyword strings using an order preserving encryption algorithm;

    storing the encrypted permuted keyword strings in a database;

    transmitting the encrypted document to the cloud service provider;

    receiving, at a network intermediary, a search request with a search term directed to encrypted documents stored in a cloud service provider, the search term comprising a wildcard search term;

    transforming the wildcard search term to a permuted search term having a prefix search format;

    generating a minimum possible plaintext string using the permuted search term as prefix and padding the permuted search term to a first character length using one or more trailing characters indicative of a minimum possible value related to the search term;

    generating a maximum possible plaintext string using the permuted search term as prefix and padding the permuted search term to the first character length using one or more trailing characters indicative of a maximum possible value related to the search term;

    encrypting the minimum possible plaintext string and the maximum possible plaintext string using the order-preserving encryption algorithm used to encrypt the permuted keyword strings;

    generating a minimum ciphertext from the minimum possible plaintext string and a maximum ciphertext from the maximum possible plaintext string;

    determining a set of common leading digits from the minimum ciphertext and the maximum ciphertext;

    generating a range query including the set of common leading digits;

    sending the range query to the database of encrypted permuted keyword strings; and

    receiving a search result from the database including encrypted permuted keyword strings having ciphertext values that fall within the range query.

View all claims
  • 10 Assignments
Timeline View
Assignment View
    ×
    ×