Method and computer program product for order preserving symbol based encryption

• US 9,059,851 B2
• Filed: 02/22/2011
• Issued: 06/16/2015
• 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:
  US13/579,934
• Publication Number:
  US 20130046995A1
• Time in Patent Office: 1,575 Days
• Field of Search: None
• US Class Current: 1/1
• 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

A method for generating an encryption dictionary, the method includes 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.

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 increasing function;

wherein the encryption dictionary comprises a mapping between the multiple plaintext symbols and random token of the multiple plaintext symbols based on a sensitivity level of one or more of the symbols, wherein the random token for each plaintext symbol is 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.

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 1 further comprising selecting the multiple plaintext symbols.

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

10. 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.

11. The method according to claim 1, comprising generating at least one additional dictionary for at least one other set of plaintext symbols.

12. A non-transitory computer readable medium that stores instructions for:

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

calculating, using a monotonic increasing function, 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 encryption dictionary comprises a mapping between the multiple plaintext symbols and random values of the multiple plaintext symbols based on a sensitivity level of one or more of the symbols, wherein the random token for each plaintext symbol is 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.

13. The non-transitory computer readable medium according to claim 12 that stores instructions for 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.

14. The non-transitory computer readable medium according to claim 12 that stores instructions for 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.

15. The non-transitory computer readable medium according to claim 12 that stores instructions for calculating multiple random tokens for a single plaintext symbol.

16. The non-transitory computer readable medium according to claim 15 that stores instructions for calculating multiple random tokens for a single plaintext symbol that has a popularity level that exceeds a predefined popularity level.

17. The non-transitory computer readable medium according to claim 15 that stores instructions for 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.

18. The non-transitory computer readable medium according to claim 12 that stores

instructions for:

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.

19. The non-transitory computer readable medium according to claim 12 that stores instructions for selecting the multiple plaintext symbols.

20. The non-transitory computer readable medium according to claim 12 that stores instructions for encoding a numerical value of each random token to an alphabetic value.

21. The non-transitory computer readable medium according to claim 12 that stores instructions for:

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.

22. The non-transitory computer readable medium according to claim 12 that stores instructions for generating at least one additional dictionary for at least one other set of plaintext symbols.