Method and system for accelerating the deterministic enciphering of data in a small domain

1. A key-dependent method for reversibly enciphering an input string to an output string having the same length as the input string, comprising:

receiving the input string;

storing the input string into a register;

modifying the register in a sequence of reversible and key-dependent phases, wherein each phase is functionally equivalent to two or more rounds of Thorp-shuffle encryption, and wherein each phase involves:

invoking a pseudorandom function that outputs a pseudorandom string;

iteratively modifying the register in a sequence of two or more rounds, wherein each round entails using a different portion of the pseudorandom string to direct the modification of the register; and

providing the contents of the register as an output, after the sequence of phases completes.

2. The method of claim 1 ,

wherein receiving the input string also involves receiving a key and a tweak; and

wherein applying the pseudorandom function involves using the key and the tweak to determine the pseudorandom function.

3. The method of claim 1 , wherein the pseudorandom function is implemented by the CBC-MAC of the Advanced Encryption Standard (AES).

4. A method for enciphering an input to produce an output, comprising:

receiving the input, wherein the input is n characters in length and wherein each character is a base-k digit, for some n≧2 and k≧2;

storing the input into an n-character first register;

modifying the first register in a sequence of two or more numbered phases, wherein each phase involves:

partitioning the first register into a first and second portion, the first portion comprising m≧2 characters and the second portion comprising the remaining n−m characters;

applying a pseudorandom function to the phase number and the second portion, wherein the pseudorandom function outputs a pseudorandom character string t;

obtaining from the pseudorandom string m·k m−1 base-k characters and storing them in a speed-up register;

using the first portion of the first register to select characters from the speed-up register and combining the selected characters with the first portion of the first register to obtain a new right-hand side consisting m base-k characters;

replacing the first register by the concatenation of the second portion of the first register and the new right-hand side; and

providing the contents of the first register as an output, after the sequence of phases completes.

5. The method of claim 4 , wherein concatenating two character strings involves:

joining a first character string of x characters in length to a second character string of y characters in length to produce a new character string of x+y characters and wherein the new character string contains the characters of the first character string followed by the characters of the second character string.

6. The method of claim 4 ,

wherein receiving the input involves receiving a key and a tweak; and

wherein applying the pseudorandom function involves using the key and the tweak to determine the pseudorandom function.

7. The method of claim 4 , wherein the pseudorandom function is constructed from the CBC-MAC of the Advanced Encryption Standard (AES).

8. The method of claim 7 , wherein at least one AES call is performed per pseudorandom function invocation.

9. The method of claim 4 ,

wherein said input is a Social Security number or a credit-card number or a Private Account Number; and

enciphering the input into a string of the same length and drawn from the same character set simplifies adding encryption to a system with legacy data, because field types for the legacy data need not be changed when the data is enciphered.

10. A non-transitory computer-readable storage medium for storing instructions that when executed by a computer cause the computer to perform a method for enciphering an input to produce an output, comprising:

receiving the input, wherein the input is n characters in length and wherein each character is a base-k digit, for some n≧2 and k≧2;

storing the input into an n-character first register;

modifying the first register in a sequence of two or more numbered phases, wherein each phase involves:

partitioning the first register into a first and second portion, the first portion comprising m≧2 characters and the second portion comprising the remaining n−m characters;

applying a pseudorandom function to the phase number and the second portion, wherein the pseudorandom function outputs a pseudorandom character string;

obtaining from the pseudorandom string m·k m−1 base-k characters and storing them in a speed-up register;

using the first portion of the first register to select characters from the speed-up register and combining the selected characters with the first portion of the first register to obtain a new right-hand side consisting m base-k characters;

replacing the first register by the concatenation of the second portion of the first register and the new right-hand side; and

providing the contents of the first register as an output, after the sequence of phases completes.

11. The non-transitory computer-readable storage medium of claim 10 , wherein concatenating two character strings involves:

joining a first character string of x characters in length to a second character string of y characters in length to produce a new character string of length x+y number of characters and wherein the new character string contains the characters of the first character string followed by the characters of the second character string.

12. The non-transitory computer-readable storage medium of claim 10 ,

wherein receiving the input involves receiving a key and a tweak; and

wherein applying the pseudorandom function involves using the key and the tweak to determine the pseudorandom function.

13. The non-transitory computer-readable storage medium of claim 10 wherein the pseudorandom function is constructed from the CBC-MAC of the Advanced Encryption Standard (AES).

14. The non-transitory computer-readable storage medium of claim 13 , wherein at least one AES call is performed per pseudorandom function invocation.

15. The non-transitory computer-readable storage medium of claim 10 ,

wherein said input is a Social Security number or a credit-card number or a Private Account Number; and

enciphering the input into a string of the same length and drawn from the same character set simplifies adding encryption to a system with legacy data, because field types for the legacy data need not be changed when the data is enciphered.

16. A system for enciphering an input to produce an output, comprising:

a receiving mechanism configured to receive the input, wherein the input is n characters in length and wherein each character is a base-k digit, for some n≧2 and k≧2;

a storing mechanism configured to store the input into an n-character first register;

a computation mechanism configured to modify the first register in a sequence of two or more numbered phases, wherein each phase involves:

partitioning the first register into a first and second portion, the first portion comprising m≧2 characters and the second portion comprising the remaining n−m characters;

applying a pseudorandom function to the phase number and the second portion, wherein the pseudorandom function outputs a pseudorandom character string;

obtaining from the pseudorandom string m·k m−1 base-k characters and storing them in a speed-up register;

using the first portion of the first register to select characters from the speed-up register and combining the selected characters with the first portion of the first register to obtain a new right-hand side consisting m base-k characters;

replacing the first register by the concatenation of the second portion of the first register and the new right-hand side; and

an outputting mechanism configured to provide the contents of the first register as an output, after the sequence of phases completes.

17. The system of claim 16 , wherein concatenating two character strings involves:

joining a first character string of x characters in length to a second character string of y characters in length to produce a new character string of length x+y number of characters and wherein the new character string contains the characters of the first character string followed by the characters of the second character string.

18. The system of claim 16 ,

wherein receiving the input involves receiving a key and a tweak; and

wherein applying the pseudorandom function involves using the key and the tweak to determine the pseudorandom function.

19. The system of claim 16 wherein the pseudorandom function is constructed from the CBC-MAC of the Advanced Encryption Standard (AES).

20. The system of claim 19 , wherein at least one AES call is performed per pseudorandom function invocation.

21. The system of claim 16 ,

wherein said input is a Social Security number or a credit-card number or a Private Account Number; and

enciphering the input into a string of the same length and drawn from the same character set simplifies adding encryption to a system with legacy data, because field types for the legacy data need not be changed when the data is enciphered.

22. A key-dependent method for reversibly enciphering an input string into an output string having the same length as the input string, the method comprising:

storing the input string in a register;

modifying contents of the register in a sequence of reversible and key-dependent phases, wherein each phase is functionally equivalent to two or more rounds of Thorp-shuffle encryption, and wherein said modification in each phase is directed by a multi-character output of a pseudorandom function; and

upon completion of said modification, providing the modified contents of the register as an output string.