SYSTEMS AND METHODS FOR IMPLEMENTING AN EFFICIENT, SCALABLE HOMOMORPHIC TRANSFORMATION OF ENCRYPTED DATA WITH MINIMAL DATA EXPANSION AND IMPROVED PROCESSING EFFICIENCY
First Claim
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.
4 Assignments
0 Petitions
Accused Products
Abstract
Partially homomorphic encryption systems may be transformed into fully homomorphic encryption systems that are scalable, rapid in translation speed, difficult to invert or break, capable of enabling various types of public and/or private key generation protocols and semantically secure. 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. The final, output plaintext is equivalent to plaintext data that would have been generated by just applying the desired computations to the input plaintext data.
240 Citations
27 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. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
2. (canceled)
-
14. 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. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. 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. - View Dependent Claims (27)
-
-
26. (canceled)
Specification