Searchable symmetric encryption

1 . A method of generating a modified permuterm index entry for use in a search for a keyword in a portion of an encrypted data collection, comprising:

at a client:

identifying a keyword in one or more portions of an encrypted data collection;

generating a permuterm index entry for the keyword, wherein the permuterm index entry comprises X values including a delimiting value inserted after the last value of the keyword, and wherein the delimiting value marks the end of the keyword;

generating a modified permuterm index entry for the keyword from the permuterm index entry, wherein the modified permuterm index entry comprises the first Y values of the permuterm index entry appended with a zero-or-more wildcard value, wherein Y is greater than zero and Y is less than or equal to X; and

storing the modified permuterm index entry in a modified permuterm index.

2 . The method of claim 1 , wherein the storing comprises:

determining if the modified permuterm index entry is a duplicate of another modified permuterm index entry already stored in the modified permuterm index; and

storing the modified permuterm index entry in the modified permuterm index if the modified permuterm index entry is not a duplicate of another modified permuterm index entry already stored in the modified permuterm index.

3 . The method of claim 1 , wherein the storing comprises:

determining if the permuterm index entry consists of a delimiting value and a wildcard value; and

storing the modified permuterm index entry in the modified permuterm index if the modified permuterm index entry does not consist of a delimiting value and a wildcard value.

4 . The method of claim 1 , wherein the storing comprises:

determining if the last value of the keyword is present in the modified permuterm index and storing the modified permuterm index if it does not comprise the last value of the keyword;

determining if the last value of the keyword is followed by the delimiting value in the modified permuterm index; and

storing the modified permuterm index entry in the modified permuterm index if the last value of the keyword in the modified permuterm index entry is followed by the delimiting value.

5 . The method of claim 1 , wherein the storing comprises:

determining if the last value of permuterm index entry is the delimiting value; and

storing the permuterm index entry in the modified permuterm index if the last value of permuterm index entry is the delimiting value.

6 . The method of claim 1 , further comprising:

encrypting the modified permuterm index;

encrypting the data collection; and

sending the encrypted modified permuterm index and the encrypted data collection to a server.

7 . The method of claim 6 , wherein a Hash-based Message Authentication Code (HMAC) is used to encrypt the modified permuterm index.

8 . The method of claim 1 , wherein a value is a binary value representing a alphanumeric character.

9 . The method of claim 1 , wherein the method further comprises storing an additional entry in the modified permuterm index, wherein the additional entry is configured in use to generate a false positive.

10 . The method of claim 1 , wherein the zero-or-more wildcard value indicates an unknown number of unknown values.

11 . A method for retrieving one or more portions of an encrypted data collection, comprising:

at a server:

receiving a search token, wherein the search token is an encrypted search query;

comparing the values of the search token to the values of an entry in a modified permuterm index, wherein the modified permuterm index comprises a plurality of encrypted entries for a keyword wherein at least one entry has less values than another entry; and

if the values of the search token match the values of the entry of the modified permuterm index, identifying one or more portions of an encrypted data collection associated with the keyword.

12 . A data processing device configured to perform the method according to claim 1 .

13 . A non-transitory computer-readable storage medium storing a computer program comprising instructions which, when executed by a computing device, cause the computing device to perform the method according to claim 1 .

14 . A computer system comprising at least one processor and memory storing a computer program configured to carry out the method of claim 1 .