Systems and methods for implementing an efficient, scalable homomorphic transformation of encrypted data with minimal data expansion and improved processing efficiency

• US 10,333,696 B2
• Filed: 11/07/2017
• Issued: 06/25/2019
• Est. Priority Date: 01/12/2015
• Status: Active Grant

• Current Assignee: X-Prime, Inc.
• Original Assignee: X-Prime, Inc.
• Inventors: Ahmed, Sherjil
• Primary Examiner(s): Kim, Jung W
• Assistant Examiner(s): Stoica, Adrian
• Application Number:
  US15/805,916
• Publication Number:
  US 20190036678A1
• Time in Patent Office: 595 Days
• CPC Class Codes: H04L 2209/46 Secure multiparty computation, e.g. millionaire problem
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/88 Medical equipments
• CPC Class Codes: H04L 9/006 involving public key infrastructure [PKI] trust models network architecture or network communication protocol for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3033 details relating to pseudo-prime or prime number generation, e.g. primality test
• CPC Class Codes: H04L 9/3268 using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL]
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Partially homomorphic encryption systems may be transformed into fully homomorphic encryption systems. Input plaintext data are transformed into modified plaintext data using a prime number operation and the modified plaintext data is then encrypted using any number of conventional encryption schemes. Desired computations on the encrypted data are transformed into homomorphic operations, based on the nature of the encryption format, and the homomorphic operations are applied to yield manipulated encrypted data. The manipulated encrypted data may be decrypted and the decrypted plaintext data may be modified into final, output plaintext data using a similar prime number operation as applied during encryption.

Claims

1. An encryption system comprising:

a computing device, wherein said computing device comprises at least one processor coupled to a memory and wherein said memory comprises instructions executable by the at least one processor to;

receive a first plaintext data;

modify the first plaintext data to yield second plaintext data;

encrypt the second plaintext data in a first encryption format to generate a first encrypted data;

receive a request to perform an operation on the first encrypted data;

transform the operation into a homomorphic operation based on the first encryption format, wherein said homomorphic operation is different from the operation;

apply the homomorphic operation to the first encrypted data to generate a second encrypted data, wherein the homomorphic operation, as transformed from the operation, is configured such that, when applied to the first encrypted data to yield the second encrypted data, the second encrypted data does not occupy more than 4 times n log(n) of said memory and wherein n is equal to a number of bits defining the first encrypted data;

decrypt the second encrypted data using a first decryption format corresponding to the first encryption format to yield a third plaintext data; and

modify the third plaintext data to generate fourth plaintext data, wherein said fourth plaintext data is equivalent to plaintext data generated by applying said operation to the first plaintext data.

2. The encryption system of claim 1, wherein said first encryption format is at least one of RSA, Goldwasser-Micali, El-Gamal, Benaloh, and Paillier.

3. The encryption system of claim 1, wherein said operation is at least one of a multiplication operation, subtraction operation, division operation and addition operation.

4. The encryption system of claim 3, wherein transforming said operation to yield a homomorphic operation comprises redefining an addition operation as at least one multiplication operation.

5. The encryption system of claim 3, wherein said homomorphic operation is configured such that execution of the homomorphic operation by the processor requires no more than 10 times more processing cycles than an execution of the operation, by the processor, applied to the first plaintext data.

6. The encryption system of claim 3, wherein transforming said operation to yield a homomorphic operation comprises redefining a multiplication operation as at least one exponentiation operation.

7. The encryption system of claim 3, wherein transforming said operation to yield a homomorphic operation comprises redefining a subtraction operation as at least one division operation.

8. The encryption system of claim 3, wherein transforming said operation to yield a homomorphic operation comprises redefining a division operation as at least one root operation.

9. The encryption system of claim 1, wherein the first plaintext data is modified by applying a prime number generation process to yield a plurality of prime numbers, wherein the prime number generation process comprises identifying a prime number that is less than an integer representative of the first plaintext data and that is on a predefined list of prime numbers, subtracting the prime number from the integer to yield a remainder, and repeating the prime number generation process using the remainder in place of the integer in subsequent cycles to yield the plurality of prime numbers.

10. The encryption system of claim 9, wherein the second plaintext data is generated by multiplying said plurality of prime numbers together.

11. The encryption system of claim 1, wherein the third plaintext data is modified applying a prime number generation process to yield a plurality of prime numbers, wherein the prime number generation process comprises by identifying a prime number that is less than an integer representative of the third plaintext data and that is on a predefined list of prime numbers, dividing the integer using the prime number to yield a remainder, and repeating the prime number generation process using the remainder in place of the integer in subsequent cycles to yield the plurality of prime numbers.

12. The encryption system of claim 11, wherein the fourth plaintext data is generated by adding said plurality of prime numbers together.

13. A method of homomorphically manipulating encrypted data in a computer having at least one processor coupled to a memory, wherein said memory comprises instructions executable by the at least one processor, said method comprising:

in said computer, receiving a first encrypted data, wherein said first encrypted data is generated by applying a first encryption format to a first plaintext data;

in said computer, receiving a request for an operation to be performed on the first encrypted data;

in said computer, transforming said operation into a homomorphic operation based on the first encryption format, wherein said homomorphic operation is different from the operation; and

in said computer, applying the homomorphic operation to the first encrypted data to yield second encrypted data, wherein the homomorphic operation, as transformed from the operation, is configured such that, when applied to the first encrypted data to yield the second encrypted data, the second encrypted data does not occupy more than 4 times n log(n) of said memory and wherein n is equal to a number of bits defining the first encrypted data.

14. The method of claim 13, wherein said first encryption format is at least one of RSA, Goldwasser-Micali, El-Gamal, Benaloh, Paillier, and an encryption format which is not homomorphic for both multiplication and addition operations.

15. The method of claim 13, wherein transforming said operation to yield a homomorphic operation comprises redefining an addition operation as at least one multiplication operation.

16. The method of claim 13, wherein said homomorphic operation is configured such that an execution of the homomorphic operation by the processor requires no more than 10 times more processing cycles than an execution of the operation, by the processor, applied to the first plaintext data.

17. The method of claim 13, wherein transforming said operation to yield a homomorphic operation comprises redefining a multiplication operation as at least one exponentiation operation.

18. The method of claim 13, wherein transforming said operation to yield a homomorphic operation comprises redefining a subtraction operation as at least one division operation.

19. The method of claim 13, wherein transforming said operation to yield a homomorphic operation comprises redefining a division operation as at least one root operation.

20. The method of claim 13, further comprising receiving a plaintext data and generating first plaintext data from the plaintext data by applying a prime number generation process to yield a plurality of prime numbers, wherein the prime number generation process comprises identifying a prime number that is less than an integer representative of the plaintext data and that is on a predefined list of prime numbers, subtracting the prime number from the integer to yield a remainder, repeating the prime number generation process using the remainder in place of the integer in subsequent cycles to yield a plurality of prime numbers, and multiplying said plurality of prime numbers together.

21. The method of claim 20, further comprising decrypting the second encrypted data using a first decryption format corresponding to the first encryption format to yield a third plaintext data.

22. The method of claim 21, further comprising modifying the third plaintext data to generate fourth plaintext data, wherein said fourth plaintext data is equivalent to output plaintext data that would have been generated by directly applying said operation to the plaintext data.

23. The method of claim 22, further comprising modifying the third plaintext data to generate fourth plaintext data by applying a prime number generation process to yield a plurality of prime numbers, wherein the prime number generation process comprises identifying a prime number that is less than an integer representative of the third plaintext data and that is on a predefined list of prime numbers, dividing the integer using the prime number to yield a remainder, repeating the prime number generation process using the remainder in place of the integer in subsequent cycles to yield a plurality of prime numbers, and adding said plurality of prime numbers together.

24. An encryption method executed in a computing device, wherein said computing device comprises at least one processor coupled to a memory and wherein said memory comprises instructions executable by the at least one processor, said encryption method comprising:

receiving a first plaintext data;

modifying the first plaintext data to yield second plaintext data, wherein the first plaintext data is modified by applying a prime number generation process to yield a plurality of prime numbers, wherein the prime number generation process comprises identifying a prime number that is less than an integer representative of the first plaintext data and that is on a predefined list of prime numbers, subtracting the prime number from the integer to yield a remainder, repeating the prime number generation process using the remainder in place of the integer in subsequent cycles to yield a plurality of prime numbers, identifying an additional unused prime number not included within the plurality of prime numbers, and multiplying said plurality of prime numbers together;

encrypting the second plaintext data in a first encryption format to generate a first encrypted data;

receiving a request to perform an operation, wherein said operation is at least one of a multiplication operation, subtraction operation, division operation and addition operation;

transforming the operation into a homomorphic operation based on the first encryption format, wherein transforming said operation to yield a homomorphic operation comprises at least one of redefining an addition operation as at least one multiplication operation, redefining a multiplication operation as at least one exponentiation operation, redefining a subtraction operation as at least one division operation, or redefining a division operation as at least one root operation;

applying the homomorphic operation to the first encrypted data to generate a second encrypted data, wherein the homomorphic operation, as transformed from the operation, is configured such that, when applied to the first encrypted data to yield the second encrypted data, the second encrypted data does not occupy more than 4 times n log(n) of said memory and wherein n is equal to a number of bits defining the first encrypted data;

decrypting the second encrypted data using a first decryption format corresponding to the first encryption format to yield a third plaintext data; and

modifying the third plaintext data to generate fourth plaintext data, wherein said fourth plaintext data is equivalent to plaintext data generated by applying said operation to the first plaintext data, wherein the third plaintext data is modified by applying a prime number generation process to yield a plurality of prime numbers, wherein the prime number generation process comprises identifying a prime number that is less than an integer representative of the third plaintext data and that is on a predefined list of prime numbers, dividing the integer using the prime number to yield a remainder, repeating the prime number generation process using the remainder in place of the integer in subsequent cycles to yield a plurality of prime numbers, and generating the fourth plaintext data by adding said plurality of prime numbers together.

25. The encryption method of claim 24, wherein the additional unused prime number not included within the plurality of prime numbers is used to decrypt second encrypted data, wherein said second encrypted data has been subject to an exponentiation operation.