System and method for initializing tokens in a dictionary encryption scheme

• US 9,195,835 B2
• Filed: 02/14/2013
• Issued: 11/24/2015
• Est. Priority Date: 03/01/2012
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Movshovitz, David
• Primary Examiner(s): Gee, Jason K
• Application Number:
  US13/767,546
• Publication Number:
  US 20130232341A1
• Time in Patent Office: 1,013 Days
• Field of Search: 713/189
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G09C 1/00 Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system cryptographic typewriters G09C3/00

Abstract

Computer systems and applications are provided for encrypting data in a manner which preserves the ability to process the encrypted data. The method includes arranging a plurality of plaintext symbols in lexicographical order; defining respective first and second subsets of the lexicographically arranged symbols; defining a first and a second set of random tokens for use with the first and second subsets of symbols, respectively; adding a first random constant value to each token in the first set of random tokens; adding a second random constant value to each token in the second set of random tokens; defining the first set of random tokens comprises establishing a first average distance between tokens; and defining the second set of random tokens comprises establishing a second average distance between tokens; wherein the second average distance is different than the first average distance, and the second random constant value is greater than the first random constant value.

Claims

1. A computer implemented method, comprising:

receiving data in unencrypted form, the data including a plurality of plaintext symbols;

encrypting the data in accordance with an encryption dictionary generated by

arranging the plurality of plaintext symbols in lexicographical order;

defining a first subset comprising a first plurality of the lexicographically arranged symbols;

defining a second subset comprising a second plurality of the lexicographically arranged symbols;

defining a first set comprising a first plurality of unique random tokens within a first token space for use with the first plurality of symbols, respectively;

defining a second set comprising a second plurality of unique random tokens within a second token space for use with the second plurality of symbols, respectively;

adding a first random constant value to each token in the first set of random tokens; and

adding a second random constant value to each token in the second set of random tokens;

wherein the second random constant value is greater than the first random constant value; and

storing the encrypted data in a database.

2. The method of claim 1, wherein:

defining the first set of random tokens comprises establishing a first average distance between tokens; and

defining the second set of random tokens comprises establishing a second average distance between tokens;

wherein the second average distance is different than the first average distance.

3. The method of claim 2, wherein the plaintext symbols comprise a plaintext dictionary of words in one of the following languages:

English;

French;

German;

Italian;

Polish;

Swedish;

Dutch;

Turkish; and

Esperanto.

4. The method of claim 2, further comprising:

sorting the first set of random tokens in chronological order;

sorting the second set of random tokens in chronological order;

mapping a respective one of the first set of random tokens to a respective one of the first subset of symbols; and

mapping a respective one of the second set of random tokens to a respective one of the second subset of symbols.

5. The method of claim 2, wherein the first average distance is in the range of (2)⁰ to (2)¹⁰²⁴ bits, and the second average distance is in the range of (2)⁰ to (2)¹⁰²⁴ bits.

6. The method of claim 2, wherein the difference between the second average distance and the first average distance is in the range of (2)⁰ to (2)¹⁰²⁴ bits.

7. The method of claim 2, wherein the plaintext symbols comprises words, numbers, and alphanumeric combinations in one of the following languages:

English;

French;

German;

Italian;

Polish;

Swedish;

Dutch;

Turkish; and

Esperanto.

8. The method of claim 2, wherein defining respective first and second subsets of the lexicographically arranged symbols comprises segregating the plurality of plaintext symbols based on a random coin flip event.

9. The method of claim 2, wherein:

the symbols correspond to a language having a non-linear letter frequency such that a first letter has a relatively greater frequency of occurrence than a second letter;

the first token space corresponds to the first letter;

the second token space corresponds to the second letter; and

the first token space is greater than the second token space, such that the letter frequency corresponds to the average distance for each token space.

10. The method of claim 2, further comprising:

defining a third subset of the lexicographically arranged symbols;

defining a third set of random tokens within a third token space for use with the third subset of symbols; and

adding a third random constant value to each token in the third set of random tokens;

wherein the third random constant value is different than the second random constant value.

11. The method of claim 10, wherein defining the third set of random tokens comprises establishing a third average distance between tokens, and wherein the third average distance is greater than the second average distance.

12. In a cloud based computing environment of the type including a multitenant database maintained by a service provider, a method comprising:

receiving data in unencrypted form, the data including a plurality of plaintext symbols;

encrypting the data in accordance with an encryption dictionary generated by

alphabetically sorting the plurality of plaintext symbols;

defining a first subset comprising a first plurality of the symbols;

defining a second subset comprising a second plurality of the symbols;

defining a first set comprising a first plurality of random tokens within a first token space for use with the first subset of symbols, respectively; and

defining a second set comprising a second plurality of random tokens within a second token space for use with the second subset of symbols, respectively;

wherein;

defining the first set of random tokens comprises establishing a first average distance between tokens; and

defining the second set of random tokens comprises establishing a second average distance between tokens; and

the second average distance is different than the first average distance; and

storing the encrypted data in the multitenant database.

13. The method of claim 12, further comprising:

adding a first random constant value to each token in the first set of random tokens; and

adding a second random constant value to each token in the second set of random tokens;

wherein the second random constant value is greater than the first random constant value.

14. The method of claim 13, wherein the plaintext symbols comprise a plaintext dictionary of words in one of the following languages:

English;

French;

German;

Italian;

Polish;

Swedish;

Dutch;

Turkish; and

Esperanto.

15. The method of claim 13, further comprising:

sorting the first set of random tokens in chronological order;

sorting the second set of random tokens in chronological order;

mapping a respective one of the first set of random tokens to a respective one of the first subset of symbols; and

mapping a respective one of the second set of random tokens to a respective one of the second subset of symbols.

16. The method of claim 13, wherein the first average distance is in the range of (2)⁰ to (2)¹⁰²⁴ bits, and the second average distance is in the range of (2)⁰ to (2)¹⁰²⁴ bits.

17. The method of claim 13, wherein the difference between the second average distance and the first average distance is in the range (2)⁰ to (2)¹⁰²⁴ bits.

18. The method of claim 17, further comprising:

defining a third subset of the alphabetically sorted symbols;

defining a third set of random tokens within a third token space for use with the third subset of symbols; and

adding a third random constant value to each token in the third set of random tokens;

wherein the third random constant value is different than the second random constant value.

19. The method of claim 18, wherein defining the third set of random tokens comprises establishing a third average distance between tokens, and wherein the third average distance is different than the second average distance.

20. A computer application embodied in a non-transitory medium for operation by a computer processor for performing the steps of:

receiving data in unencrypted form, the data including a plurality of plaintext symbols;

encrypting the data in accordance with an encryption dictionary generated by

arranging the plurality of plaintext symbols in lexicographical order;

defining a first subset comprising a first plurality of the lexicographically arranged symbols;

defining a second subset comprising a second plurality of the lexicographically arranged symbols;

defining a first set comprising a first plurality of random tokens within a first token space for use with the first subset of symbols, respectively;

defining a second set comprising a second plurality of random tokens within a second token space for use with the second subset of symbols, respectively;

adding a first random constant value to each token in the first set of random tokens;

adding a second random constant value to each token in the second set of random tokens;

defining the first set of random tokens comprises establishing a first average distance between tokens; and

defining the second set of random tokens comprises establishing a second average distance between tokens;

wherein the second average distance is different than the first average distance; and

wherein the second random constant value is different than the first random constant value; and

storing the encrypted data in a database.