Generating integers for cryptographic protocols

• US 9,780,948 B1
• Filed: 06/15/2016
• Issued: 10/03/2017
• Est. Priority Date: 06/15/2016
• Status: Active Grant

• Current Assignee: ISARA Corporation
• Original Assignee: ISARA Corporation
• Inventors: Gutoski, Gustav Michael, Kelly, Shane Daniel, Struik, Marinus, Yamada, Atsushi
• Primary Examiner(s): Davis, Zachary A
• Assistant Examiner(s): Pan, Peiliang
• Application Number:
  US15/182,820
• Time in Patent Office: 475 Days
• Field of Search: 380 46, 380267, 380268
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/586 using an integer algorithm, e.g. using linear congruential method
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/0844 with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

In a general aspect, pseudorandom integers are generated for use in a cryptographic protocol. In some aspects, a first plurality of digits are obtained and converted to a second plurality of digits. The first plurality of digits (e.g., bits) represent an integer in a first number system (e.g., binary), and the second plurality of digits (e.g., trits) represent the integer in a second number system (e.g., trinary). A plurality of integers in the first number system are generated based on the second plurality of digits, and an array of integers is produced. Each integer in the array is less than a modulus, and the array includes the plurality of integers. The array of integers can be used in a lattice-based cryptographic protocol.

Claims

1. A lattice-based cryptography method comprising:

obtaining a first plurality of digits based on pseudorandom data from a pseudorandom number generator, the first plurality of digits representing an integer in a first number system;

determining whether to reject the pseudorandom data based on comparing the integer with a second threshold that is based on a second number system, wherein comparing the integer with the second threshold reduces a probability of rejecting the pseudorandom data relative to comparing the integer with a first threshold that is based on the first number system;

in response to determining not to reject the pseudorandom data, converting the first plurality of digits to a second plurality of digits, the second plurality of digits representing the integer in the second number system;

by operation of a processor, generating a plurality of integers in the first number system based on the second plurality of digits;

producing an array of integers each less than a modulus, the array of integers comprising the plurality of integers; and

using the array of integers in a lattice-based cryptography protocol executed by computer nodes configured to exchange information over a communication channel.

2. The lattice-based cryptography method of claim 1, wherein the plurality of integers comprises a second plurality of integers, and the method comprises:

after seeding the pseudorandom number generator, obtaining the first plurality of digits and a first plurality of integers based on the pseudorandom data from the pseudorandom number generator; and

generating the second plurality of integers based on the second plurality of digits and the first plurality of integers.

3. The lattice-based cryptography method of claim 1, comprising producing an array of integers by an iterative process that includes multiple iterations, wherein each iteration includes:

obtaining a first plurality of digits for the iteration, the first plurality of digits for the iteration representing an integer in the first number system;

converting the first plurality of digits for the iteration to a second plurality of digits for the iteration, the second plurality of digits for the iteration representing the integer in the second number system; and

generating a plurality of integers in the first number system for the iteration based on the second plurality of digits for the iteration;

wherein the array of integers includes the plurality of integers for multiple iterations of the iterative process.

4. The lattice-based cryptography method of claim 3, wherein the plurality of integers in the first number system comprises a second plurality of integers, and each iteration includes:

obtaining a first plurality of integers for the iteration; and

generating the second plurality of integers for the iteration based on the second plurality of digits for the iteration and the first plurality of integers for the iteration.

5. The lattice-based cryptography method of claim 4, wherein obtaining the first plurality of integers for the iteration comprises:

retrieving, from the pseudorandom number generator, pseudorandom digits for the iteration;

obtaining the first plurality of integers for the iteration from a first subset of the pseudorandom digits; and

caching a second subset of the pseudorandom digits for a subsequent iteration of the iterative process.

6. The lattice-based cryptography method of claim 4, wherein obtaining the first plurality of integers for the iteration comprises:

obtaining pseudorandom digits for the iteration, a first subset of the pseudorandom digits being retrieved from the pseudorandom number generator, a second subset of the pseudorandom digits being retrieved from a cache; and

obtaining the first plurality of integers for the iteration from at least a subset of the pseudorandom digits for the iteration.

7. The lattice-based cryptography method of claim 1, wherein obtaining the first plurality of digits comprises obtaining the pseudorandom data from the pseudorandom number generator.

8. The lattice-based cryptography method of claim 1, wherein converting the first plurality of digits to the second plurality of digits comprises accessing pre-computed values of the second plurality of digits from a storage medium.

9. The lattice-based cryptography method of claim 1, wherein the plurality of integers in the first number system comprises a second plurality of integers, and the method comprises:

obtaining a first plurality of integers in the first number system; and

generating the second plurality of integers based on the second plurality of digits and the first plurality of integers.

10. The lattice-based cryptography method of claim 9, wherein each integer in the second plurality of integers is generated based on a respective one of the second plurality of digits and a respective one of the first plurality of integers.

11. The lattice-based cryptography method of claim 10, wherein each integer in the second plurality of integers is generated based on adding the respective integer in the first plurality of integers to a product of the respective digit in the second plurality of digits multiplied by a common value.

12. The lattice-based cryptography method of claim 9, wherein obtaining the first plurality of digits comprises obtaining bits that represent the integer in a base-two number system, and the second plurality of digits represent the integer in a base-three number system.

13. The lattice-based cryptography method of claim 12, wherein:

obtaining the first plurality of digits comprises obtaining eight pseudorandom bits that represent the integer in a base-two number system; and

obtaining the first plurality of integers comprises obtaining a first set of five integers by;

obtaining sixty pseudorandom bits; and

obtaining the first set of five integers from the sixty pseudorandom bits, each of the five integers in the first set comprising a respective set of twelve bits from the sixty pseudorandom bits.

14. The lattice-based cryptography method of claim 13, wherein:

converting the first plurality of digits to a second plurality of digits comprises converting the eight pseudorandom bits to five trits {t_i}; and

generating the second plurality of integers comprises generating a second set of five integers {x_i} based on computing x_i=t_i×

2¹²+b_i, where {b_i} represents the first set of five integers.

15. The lattice-based cryptography method of claim 14, wherein the second set of five integers comprises a set of non-negative values {x_i+1} less than a modulus 12289.

16. A cryptography method comprising:

obtaining pseudorandom data from a pseudorandom number generator, the pseudorandom data comprising bits that represent an integer in a binary number system;

determining whether to reject the pseudorandom data based on comparing the integer with a second threshold that is based on a trinary number system, wherein comparing the integer with the second threshold reduces a probability of rejecting the pseudorandom data relative to comparing the integer with a first threshold that is based on the binary number system;

in response to determining not to reject the pseudorandom data, converting the bits to trits that represent the integer in the trinary number system;

by operation of a processor, using the trits to generate a plurality of integers in the binary number system, wherein each of the plurality of integers is based on a respective one of the trits;

producing an array of integers each less than a modulus, the array of integers comprising the plurality of integers; and

using the array of integers in a cryptographic protocol executed by computer nodes configured to exchange information over a communication channel.

17. The cryptography method of claim 16, wherein the plurality of integers comprises a second plurality of integers, and the method comprises:

after seeding the pseudorandom number generator, obtaining the bits and a first plurality of integers based on the pseudorandom data from the pseudorandom number generator; and

generating the second plurality of integers based on the trits and the first plurality of integers.

18. The cryptography method of claim 16, comprising using the array of integers in a lattice-based key agreement protocol.

19. The cryptography method of claim 16, comprising using the array of integers in a lattice-based signature protocol.

20. The cryptography method of claim 16, comprising producing an array of integers by an iterative process that includes multiple iterations, wherein each iteration includes:

obtaining bits for the iteration, the bits representing an integer in the binary number system;

converting the bits to trits for the iteration, the trits representing the integer in a second number system; and

using the trits for the iteration to generate a plurality of integers in the binary number system for the iteration;

wherein the array of integers includes the plurality of integers for multiple iterations of the iterative process.

21. The cryptography method of claim 20, wherein the plurality of integers in the binary number system comprises a second plurality of integers, and each iteration includes:

obtaining a first plurality of integers for the iteration; and

generating the second plurality of integers based on the trits and the first plurality of integers.

22. The cryptography method of claim 21, wherein obtaining the first plurality of integers for the iteration comprises:

obtaining, from the pseudorandom number generator, pseudorandom bits for the iteration;

designating the first plurality of integers for the iteration from a first subset of the pseudorandom bits; and

caching a second subset of the pseudorandom bits for a subsequent iteration of the iterative process.

23. The cryptography method of claim 21, wherein obtaining the first plurality of integers for the iteration comprises:

obtaining pseudorandom bits for the iteration, a first subset of the pseudorandom bits being retrieved from the pseudorandom number generator, a second subset of the pseudorandom bits being retrieved from a cache; and

designating the first plurality of integers for the iteration from at least a subset of the pseudorandom bits for the iteration.

24. The cryptography method of claim 16, wherein converting the bits to trits comprises accessing pre-computed values of the trits from a storage medium.

25. The cryptography method of claim 16, wherein the plurality of integers in the binary number system comprises a second plurality of integers, and the method comprises:

obtaining a first plurality of integers in the binary number system; and

generating the second plurality of integers based on the trits and the first plurality of integers.

26. The cryptography method of claim 25, wherein:

obtaining the bits comprises obtaining eight pseudorandom bits;

converting the bits to trits comprises converting the eight pseudorandom bits to five trits {t_i};

obtaining the first plurality of integers comprises obtaining a first set of five integers by;

obtaining the first set of five integers from sixty pseudorandom bits, each of the five integers in the first set comprising a respective set of twelve bits from the sixty pseudorandom bits; and

generating the second plurality of integers comprises generating a second set of five integers {x_i} based on computing x_i=t_i×

2¹²+b_i, where {b_i} represents the first set of five integers.

27. A computing system comprising:

a data processing apparatus;

a computer-readable medium storing instructions that are operable when executed by the data processing apparatus to perform operations comprising;

obtaining a first plurality of digits based on pseudorandom data from a pseudorandom number generator, the first plurality of digits representing an integer in a first number system;

determining whether to reject the pseudorandom data based on comparing the integer with a second threshold that is based on a second number system, wherein comparing the integer with the second threshold reduces a probability of rejecting the pseudorandom data relative to comparing the integer with a first threshold that is based on the first number system;

in response to determining not to reject the pseudorandom data, converting the first plurality of digits to a second plurality of digits, the second plurality of digits representing the integer in a second number system;

generating a plurality of integers in the first number system based on the second plurality of digits;

producing an array of integers each less than a modulus, the array of integers comprising the plurality of integers; and

using the array of integers in a lattice-based cryptography protocol executed by computer nodes configured to exchange information over a communication channel.

28. The computing system of claim 27, wherein the plurality of integers comprises a second plurality of integers, and the operations comprise:

obtaining a first plurality of integers in the first number system based on a third plurality of digits from the pseudorandom number generator; and

generating the second plurality of integers based on the first plurality of integers and the second plurality of digits.

29. The computing system of claim 28, wherein the third plurality of digits includes one or more surplus digits not used in the first plurality of integers, and the computing system further comprises a cache configured to store the one or more surplus digits.

30. The computing system of claim 27, further comprising an array storage that stores pre-computed values for the second number system, and converting the first plurality of digits to the second plurality of digits comprises accessing pre-computed values of the second plurality of digits from the array storage.