Method and computer program product for order preserving symbol based encryption

• US 10,223,546 B2
• Filed: 08/14/2017
• Issued: 03/05/2019
• Est. Priority Date: 02/23/2010
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Movshovitz, David
• Primary Examiner(s): Hoffman, Brandon S
• Application Number:
  US15/676,876
• Publication Number:
  US 20180004971A1
• Time in Patent Office: 568 Days
• Field of Search: None
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: H04L 9/00 Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/3213 using tickets or tokens, e.g. Kerberos network architectures or network communication protocols for entities authentication using tickets in a packet data network H04L63/0807

Abstract

Techniques for sorting encrypted data within a software as a service (SaaS) environment. Data is encrypted on a per symbol basis with a symbol based encryption module. Sort and search functionality preserving encryption that allows other modules to sort tokens and to search for tokens is provided. Encrypted tokens that have been encrypted by the symbol based encryption module are stored in a database. Access to the encrypted tokens is provided through the SaaS environment.

Claims

1. A method for generating an encryption dictionary, the method comprises:

generating a random value for each plaintext symbol of multiple plaintext symbols; and

calculating a random token for each plaintext symbol based on a random value of the plaintext symbol and on random values of other plaintext symbols that have a lower lexicographic value than the plaintext symbol;

wherein the calculating comprises applying a monotonic function;

wherein the encryption dictionary comprises a mapping between the multiple plaintext symbols and random token of the multiple plaintext symbols.

2. The method according to claim 1, comprising calculating the random token of plaintext symbol by summing the random values of other plaintext symbols that have a lower lexicographic value than the plaintext symbol.

3. The method according to claim 1, comprising calculating the random token of the plaintext symbol by applying a weighted sum of the random values of other plaintext symbols that have a lower lexicographic value than the plaintext symbol.

4. The method according to claim 1, comprising calculating multiple random tokens for a single plaintext symbol.

5. The method according to claim 4, comprising calculating multiple random tokens for a single plaintext symbol that has a popularity level that exceeds a predefined popularity level.

6. The method according to claim 4, calculating multiple random tokens for the single plaintext symbol so that values of random tokens of other plaintext symbols are outside a range that is span by values of the multiple random tokens of the single plaintext symbol.

7. The method according to claim 1, comprising:

receiving a new plaintext symbol that is not included in the encryption dictionary;

finding a first plaintext symbol that belongs to the encryption dictionary and has a nearest smaller lexicographic value to a lexicographic value of the new plaintext symbol;

finding a second plaintext symbol that belongs to the encryption dictionary and has a nearest larger lexicographic value to the lexicographic value of the new plaintext symbol; and

assigning to the new plaintext symbol a new random token that has a new value that is between values of the random tokens of the first and second plaintext symbols.

8. The method according to claim 7, comprising randomly selecting the new value of the random token within a range of numbers that is limited by values of the random tokens of the first and second plaintext symbols.

9. The method according to claim 7, comprising assigning the new random token by adding a suffix to the random token of first plaintext symbol.

10. The method according to claim 1 further comprising selecting the multiple plaintext symbols.

11. The method according to claim 1, comprising encoding a numerical value of each random token to an alphabetic value.

12. The method according to claim 11, comprising encoding the numerical value of each random token to a sequence of small case letters.

13. The method according to claim 11, comprising encoding the numerical value of each random token to a sequence of Armenian letters.

14. The method according to claim 1, further comprising:

receiving a group of plaintext symbols to be encrypted;

encrypting by a second computerized entity plaintext symbols of the group of plaintext symbols by using the encryption dictionary to provide a group of random tokens; and

providing the group of random tokens to a first computerized entity that differs from the second computerized entity.

15. The method according to claim 14, comprising:

receiving text;

selecting out of the text the group of plaintext symbols to be encrypted; and

selecting at least one plaintext symbols to be provided to the first computerized entity without being encrypted.

16. The method according to claim 14, comprising performing sorting and search operations by the first computerized entity on the group of random tokens.

17. The method according to claim 14, comprising detecting an email address that comprises two plaintext strings that are separated by an at sign;

and generating an encrypted email address that comprises two random tokens that are separated by an at sign.

18. The method according to claim 14 comprising detecting an email address that comprises two plaintext strings that are separated by an at sign;

and generating an encrypted email address that comprises two random tokens that are followed by an at sign, wherein the at sign is followed by a predefined domain name that identifies a computerized entity that is arranged to assist in decrypting the encrypted email address.

19. The method according to claim 18, further comprising decrypting the encrypted email address and sending an email message that comprises the email address to a destination defined by the email address.

20. The method according to claim 14, comprising generating letter case information relating to the group of plaintext symbols to be encrypted.