Systems and methods for efficient fixed-base multi-precision exponentiation

• US 10,693,627 B2
• Filed: 01/19/2018
• Issued: 06/23/2020
• Est. Priority Date: 01/20/2017
• Status: Active Grant

• Current Assignee: Enveil, Inc.
• Original Assignee: Enveil, Inc.
• Inventors: Carr, Ryan
• Primary Examiner(s): Sandifer, Matthew D
• Application Number:
  US15/876,057
• Publication Number:
  US 20180224882A1
• Time in Patent Office: 886 Days
• Field of Search: 708235, 708277, 708606
• CPC Class Codes: G06F 1/0307 Logarithmic or exponential functions G06F1/0314, G06F1/035 take precedence
• CPC Class Codes: G06F 7/552 Powers or roots , e.g. Pythagorean sums
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: G06F 7/728 using Montgomery reduction
• CPC Class Codes: G06F 9/30014 with variable precision
• CPC Class Codes: H03M 7/24 Conversion to or from floating-point codes
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy

Abstract

Systems and methods for efficient fixed-base multi-precision exponentiation are disclosed herein. An example method includes applying a multi-precision exponentiation algorithm to a base number, the multi-precision exponentiation algorithm comprises a pre-generated lookup table used to perform calculations on the base number, the pre-generated lookup table comprising pre-calculated exponentiated values of the base number.

Claims

1. A method, comprising:

determining, via a processor, that a base number has a size that exceeds a size threshold, wherein the size threshold is greater than 64 bits; and

applying, via the processor, a multi-precision exponentiation algorithm to the base number, the multi-precision exponentiation algorithm comprising a pre-generated lookup table used to perform calculations on the base number, the pre-generated lookup table comprising pre-calculated exponentiated values of the base number, wherein the pre-generated lookup table is stored in a memory, the memory being coupled to the processor;

wherein an exponent size parameter of each of the pre-calculated exponentiated values in the pre-generated lookup table is selected by the processor based on a size limitation of a memory portion dedicated in the memory to the multi-precision exponentiation algorithm to prevent the pre-generated lookup table from growing to a size at which the memory portion dedicated in the memory to the multi-precision exponentiation algorithm is exhausted.

2. The method according to claim 1, further comprising:

identifying the base number as having a size that is more than 64 bits; and

determining if a time required for using the multi-precision exponentiation algorithm is less than a time required to perform the calculations of the base number directly using exponents,

wherein the multi-precision exponentiation algorithm is used only when the time required for using the multi-precision exponentiation algorithm is less than the time required to perform the calculations of the base number directly using exponents.

3. The method according to claim 2, wherein determining if a time required for using the multi-precision exponentiation algorithm is less than a time required to perform the calculations of the base number directly using exponents further comprises:

identifying the exponent size parameter;

estimating a number of multi-precision operations required using the exponent size parameter;

identifying which of the number of multi-precision operations are squarings or non-squarings; and

determining a one-time cost using calculations from the squarings and the non-squarings.

4. The method according to claim 1, further comprising selecting exponents that will be used to exponentiate the base number.

5. The method according to claim 4, further comprising identifying an index of a highest bit set in the exponents.

6. The method according to claim 1, further comprising converting the base number into a form suitable for use in an encryption algorithm.

7. The method according to claim 5, wherein an optimal value of the exponent size parameter is a function of a number of the exponents, the index of the highest bit set, and a highest possible value for the exponent size parameter.

8. A system, comprising:

a processor; and

a memory for storing executable instructions, the memory being coupled to the processor, the processor executing the instructions to;

determine if a time required for using a multi-precision exponentiation algorithm to exponentiate a base number is less than a time required to perform exponentiation of the base number directly using exponents;

apply a multi-precision exponentiation algorithm to the base number, wherein the multi-precision exponentiation algorithm comprises a pre-generated lookup table used to perform calculations on the base number, the pre-generated lookup table comprising pre-calculated exponentiated values of the base number, wherein the pre-generated lookup table is stored in the memory;

wherein an exponent size parameter of each of the pre-calculated exponentiated values in the pre-generated lookup table is selected by the processor based on a size limitation of a memory portion dedicated in the memory to the multi-precision exponentiation algorithm to prevent the pre-generated lookup table from growing to a size at which the memory portion dedicated in the memory to the multi-precision exponentiation algorithm is exhausted; and

return a calculated value for the base number.

9. The system according to claim 8, wherein the processor is further configured to identify a base number with a size that is more than 64 bits.

10. The system according to claim 9, wherein the pre-generated lookup table comprises raised values corresponding to exponentiation of the base number with the exponents.

11. The system according to claim 10, wherein the processor is further configured to select the exponents that will be used to exponentiate the base number when generating the pre-generated lookup table.

12. The system according to claim 8, wherein the processor is further configured to convert the base number into a form suitable for use in an encryption algorithm.