Back to results
US 2010/0246813 A1Published application
Method and system for accelerating the deterministic enciphering of data in a small domain
AssigneeThe Regents of the University of California
InventorsBenjamin J. Morris, Phillip Rogaway, Till Stegers
Life of this patent
Estimating the term…
Abstract
Conventional block ciphers that traffic in 128-bit block sizes are ill-suited for operating in small domains like credit card numbers. Some embodiments relate to techniques for constructing and speeding up practical and provably secure schemes for deterministically enciphering data from a small domain like credit card numbers using a conventional block cipher or other pseudorandom function.
Claims37
A method for enciphering an input string to produce an output string, comprising:
- receiving the input string;
- storing the input string into a register;
- modifying the register in a sequence of phases, 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.
4 more elements
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;
- storing the input into an n-character first register [0 . . . n-1];
- modifying the first register in a numbered sequence of phases, wherein each phase involves:
- applying a pseudorandom function to a phase number and the value in character positions [m . . . n-1] of the first register, for some m≦n, wherein the pseudorandom function outputs a pseudorandom character string and wherein each character is a base-k digit;
- selecting at least m·km-1 base-k characters from the pseudorandom character string and storing them in a second register;
- iteratively performing the following operations, wherein each iteration constitutes a round and wherein each round involves:
- applying a choice function to the first register, the second register, and the round number, wherein the choice function outputs a pseudorandom base-k character;
- combining the value in character position [0] of the first register and the pseudorandom base-k character to produce a new base-k character output;
- concatenating the value in character positions [1 . . . n-1] of the first register with the value of the new base-k character;
- and
- storing the concatenation result into the n-character first register;
- and
- providing the contents of the first register as an output, after the sequence of phases completes.
10 more elements
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;
- storing the input into an n-character first register [0 . . . n-1];
- modifying the first register in a numbered sequence of phases, wherein each phase involves:
- applying a pseudorandom function to a phase number and the value in character positions [m . . . n-1] of the first register for some m≦n, wherein the pseudorandom function outputs a pseudorandom character string and wherein each character is a base-k digit;
- selecting at least m·km-1 base-k characters from the pseudorandom character string and storing them in a second register;
- iteratively performing the following operations, wherein each iteration constitutes a round and wherein each round involves:
- applying a choice function to the first register, the second register, and the round number, wherein the choice function outputs a pseudorandom base-k character;
- combining the value in character position [0] of the first register and the pseudorandom base-k character output to produce a new base-k character output;
- concatenating the value in character positions [1 . . . n-1] of the first register with the value of the new base-k character output;
- and
- storing the concatenation result into the n-character first register;
- and
- providing the contents of the first register as an output, after the sequence of phases completes.
10 more elements
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;
- a storing mechanism configured to store the input into an n-character first register [0 . . . n-1];
- a computation mechanism configured to modify the first register in a numbered sequence of phases, wherein each phase involves:
- applying a pseudorandom function to a phase number and the value in character positions [m . . . n-1] of the first register, for some m≦n, wherein the pseudorandom function outputs a pseudorandom character string and wherein each character is a base-k digit;
- selecting at least m·km-1 base-k characters from the pseudorandom character string and storing them in a second register;
- iteratively performing the following operations, wherein each iteration constitutes a round and wherein each round involves:
- applying a choice function to the first register, the second register, and the round number, wherein the choice function outputs a pseudorandom base-k character;
- combining the value in character position [0] of the first register and the pseudorandom base-k character to produce a new base-k character output;
- concatenating the value in character positions [1 . . . n-1] of the first register with the value of the new base-k character;
- and
- storing the concatenation result into the n-character first register;
- and
- an outputting mechanism configured to provide the contents of the first register as an output, after the sequence of phases completes.
10 more elements
Dependencies are inferred from the claim text.