Patent ID: 12238197

Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions and/or relative positioning of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of various embodiments of the present invention. Also, common but well-understood elements that are useful or necessary in a commercially feasible embodiment are often not depicted in order to facilitate a less obstructed view of these various embodiments it will further be appreciated that certain actions and/or steps may be described or depicted in a particular order of occurrence while those skilled in the art will understand that such specificity with respect to sequence is not actually required. It will also be understood that the terms and expressions used herein have the ordinary technical meaning as is accorded to such terms and expressions by persons skilled in the technical field as set forth above except where different specific meanings have otherwise been set forth herein.

DETAILED DESCRIPTION

Generally speaking, pursuant to these various embodiments, a method and apparatus for homomorphic image encryption and decryption is presented. Referring now to the drawings, and in particular toFIG.1, a computing system1that can be used to implement the presently described homographic image encryption and decryption schemes is shown. The example computing system1includes a computer processor (CPU)10, which interacts with a user interface20. Those skilled in the art will recognize and appreciate that the CPU10may include one or more processors that can comprise a fixed-purpose hard-wired platform or can comprise a partially or wholly programmable platform. All of these architectural options are well known and understood in the art and require no further description here.

The user interface20can include an input device20band an output device, e.g., a display20a. The display20acan be, or can include, one or more of a monitor, printer, touch screen, audio device, or other computer-related devices that present output from the computing system1. The input device20bcan be, or can include, one or more of a mouse, a touch screen, a keyboard, a microphone, a camera, a scanner, a touch pad, or other computer-related devices that allow a user to interact with a computer and provide feedback in essence, the user interface20allows a user to interact with the computing system1and provides relevant information to the user. In some embodiments, the input device20band the display20acan be the same, or at least intertwined. For example, the user interface20can include a touch screen that provides both the function of the display20aand the input device20b.

The CPU10also includes and/or accesses a memory70, which can be an electronic storage device. For example, the memory70can include a thumb drive, an SD card (or micro SD card), RAM memory, a hard drive, or other storage media, or a combination of such memory. The memory70can also be stored on the cloud80(data storage accessed through the internet), for example, and in some embodiments can include or be in communication with a network60or some other device that allows information stored on the memory70to communicate with the CPU10, and the user interface20. The CPU10may also be operably coupled to a transmitter30and/or a receiver32.

Referring now toFIG.2, an illustrative process that is compatible with many of these teachings will now be presented. Those skilled in the art will appreciate that the processes described are readily enabled using any of a wide variety of available and/or readily configured platforms, including partially or wholly programmable platforms as are known in the art or dedicated purpose platforms as may be desired for some applications. In general, a digital image is comprised of pixels distributed in a grid with rows and columns. A pixel will have a certain brightness, or “intensity”, and each pixel intensity may be written as a sum of its components, or “sub-values”. In one example, y is the intensity value of a pixel in an image g(i,j) for i=1, 2, 3, . . . M and j=1, 2, 3, . . . N, where the indices i and j represent individual pixels' coordinates and M and N are the number of rows and columns of pixels, respectively. The pixel intensity value), is found by, at step100, summing k pixels' intensity sub-values, such that y=y1+y2+y3+ . . . yk. Furthermore, the number of sub-values, k, for each pixel is an integer between 0 and L (i.e., 0<k<L), and L is the number of intensity levels of a pixel.

Each sub-value is separated and sent at step102to a homomorphic encryption function, E, which is a mathematical function. The homomorphic encryption function at step104operates on the sub-values of each pixel, such that E(y)=E(y1+y2+y3+ . . . yk), which may also be written in the form: E(y)=E(y1)×E(y2)×E(y3)× . . . E(yk). One can perform distributed and/or parallel encryption processing of each E(yk) simultaneously, or at different times using the same or different encryption keys. Each E(yk) can also be computed by the same or different processors at the same or different locations. This can greatly increase the security of the encrypted image because an opponent may not have access to all E(yk) functions that may be stored at different locations or transmitted at different time intervals. Also, if different encryption keys are used for each E(yk), opponents who have access to some of the decryption keys may not have access to other decryption keys, resulting in an inability to decipher all of the encrypted component images without all the decryption keys. Also, each ykcan be randomly generated; the only requirement in this context is that their sum should be equal to y, leading to an increase in diffusion of each plain-image's pixels. It is also noted that the larger the value of k, the more secure the encrypted image is, but also the higher the computational cost.

In addition, each of the encrypted values E(yk) could be a very large integer, out of the range [0; (L−1)] of the associated image's pixels intensity values. Thus, to make these E(yk) meaningful from an image point of view, one can apply (mod p), where “mod” is the modulus p (with p being a prime number), to each of the encrypted values E(yk) to obtain pixels' intensity values within the range [0; (L−1)], that are meaningful from an image point of view (e.g., all pixels intensity values that are not out of the range [0,255] for an 8-bit image). For instance, this range is [0; 255] for the case of an 8-bit image, and p can be chosen to be p=257, the closest prime number to the range size. In this example, C1=E(y1), C2=E(y2), C3=E(y3), . . . Ck=E(yk), where each Ckis an encrypted value for the corresponding pixel intensity sub-value y. Applying (mod p), the encrypted values for each of the pixel's intensity sub-values y1, y2, y3, . . . ypkare given as the quantities Cp1=E(y1) mod p, Cp2=(y2) mod p, . . . Cpk=E(yk) mod p. The encrypted values Cp1, Cp2, . . . Cpkare stored106in a storage device and/or transmitted108to a receiver or database330. For instance, the encrypted values can be stored/saved in local or remote storage devices, and the encrypted values can be transmitted to a remote location through a transmitting antenna (e.g., transmitter30) or through the internet or other communication channels which may be unsecured (FIG.4).

With reference toFIG.3A, a method for homomorphic image decryption is shown. In a manner analogous to the above-mentioned encryption function application, a transmitter transmits200A the encrypted intensity sub-value E(yk) mod p. The decryption function, D, may be applied202A with the same encryption key to recover the pixel intensity value y. Specifically, the decryption function D operates202A to decrypt the encrypted pixel intensity value E(y), and the resultant decrypted pixel intensity sub-values needed to reconstruct the original image can be sent204A to secure storage devices such as memory devices70and/or transmitter30through a secure channel for future usage.320.

In an alternative example shown inFIG.3B, a transmitter transmits200B each E(yk) to a receiving device, similar to the device depicted inFIG.1, that is configured to have the decryption function D operate202B into the individual pixels intensity sub-values ykwith different encryption keys, which in turn, are transmitted204B to an adder device to be summed206B to obtain the pixel intensity y. Mathematically this may be written as D[E(y)]=D[E(y1)×E(y2)×E(y3)× . . . E(yk)]=y1+y2+y3+ . . . yk=y for the case ofFIG.3A. All the pixel intensity value y needed to reconstruct the original image are then sent208B to a secure storage device70and/or transmitter30through a secure channel if necessary for future usage.

One quantity used in the decryption is the greatest integer less than or equal to (E(yk)/p), also known as the floor of (E(yk)/p) or └E(yk)/p┘. This also represents the quotient (qtk) when E(yk) is divided by p. In other words, mathematically, qtk=└E(yk)/p┘. This quantity is not secret but can also be encrypted by other means to increase security because without it, reconstruction of E(yk) for decryption purposes at the receiver may be impossible. To reconstruct or compute the individual encrypted pixel intensity sub-values, the following equation is used for each value k: E(yk)=qtk×p+Cpkwhere qtk×p+Cpkis different for each k value. Once each E(yk) is found, the decryption function for the homomorphic encryption function E is applied to obtain the individual pixel sub-values y. In addition, if the encryption/decryption keys for each individual pixel intensity sub-value ykare different, one can first decrypt each E(yk), then add the sum of the pixel sub-values y1+y2+y3+ . . . +ykto obtain the pixel intensity value y. For implementation efficiency, the image's pixel intensity values can be processed together as a matrix instead of single pixels.

In one example of the above described approach, a distributed homomorphic image encryption method for an instance where there are only two pixel intensity sub-values (k=2) is shown inFIG.4. In this example, each pixel's intensity value y is written as a sum of only two pixel intensity sub-values y1and y2, or y=y1+y2. The transmitter side of the flow diagram inFIG.4implements the concepts shown inFIG.2, for the case of k=2, while the receiver side implements the decryption method ofFIG.3A, where the decryption keys are the same. InFIG.4, the information source is an original image, which is an RGB image. The original image input is separated at step300into R, G, and B-channel images to produce three separate gray-scale images denoted by Original Image R, Original image G, and Original Image B. Then, the pixel intensity values y for each of these R, G, and B-Channel images are extracted and split302into two pixels components y1and y2so that y=y1+y2. Then y1and y2are each encrypted304separately using a homomorphic encryption function E and the same public key to produce two encrypted pixel sub-values Cp1and Cp2that can each optionally be compressed306using known compression methods before being transmitted308and/or stored.

In one more specific example, the encryption function for this can be represented as E(y)=E(y1)+E(y2). The encryption function E has an homomorphic property in that the encryption of a sum of two pixel intensity sub-values y1and y2equals the product of the individual encrypted sub-values E(y1) and E(y2). One such function is the known Pailliers Cryptographic System where a value y can be encrypted as follows: E(y)=gyxNmod N2, where N=s×q, and s and q are prime numbers, while x is a random number such that x∈ZN*={1, 2, . . . , (N−1)}, and g is an integer whose order l is a multiple of N such that gl≡1(mod N) and a value of g=1+N satisfies this condition when s and q have the same length. When using the Paillier encryption scheme, N should be a large with, for example, more than 300 digits. In this example, C1=E(y1)=gy1x1Nmod N2and C2=E(y2)=gy2x2Nmod N2. Applying mod p as described above gives Cp1=E(y1) mod p=[gy1x1Nmod N2] mod p and Cp2=E(y2) mod p=[gy2x2Nmod N2] mod p where Cp1and Cp2represent the cipher values corresponding to each of the pixel intensity sub-values y1and y2and are the values that are transmitter over or stored on insecure media.

For decryption in this example according to the decryption method described above, the encrypted pixel intensity sub-values E(y1) and E(y2) can be expressed as E(y1)=qt1×p+Cp1and E(y2)=qt2×p+Cp2. The decryption proceeds as D[E(y1)×E(y2)]=D[y1+y2]=D[E(y)]=y. When applying the Paillier Decryption function, C=E(y1)×E(y2) and

y=L⁡(Cλ⁢mod⁢N2)L⁡(gλ⁢mod⁢N2)
mod N where A is given by the least common multiple of s−1 and q−1 while the function

L⁡(U)⁢is⁢L⁡(U)=(0-1)N.

On the receiver side, the database330where the encrypted, compressed or uncompressed images are stored relays312the data to a receiver. The data (encrypted images) may also come through the receiver32. The decompression is implemented314if necessary, and then the homomorphic property of the encryption function is also used to decrypt316previously encrypted pixels intensity sub-values and reconstruct each channel image before combining318them to recover the original RGB image. It is noted that after encrypting each channel Original Image R, G, or B, two cipher-images are produced instead of one. For instance, Original Image R will produce two encrypted images R1and R2, Original image G will produce two encrypted images G1and G2, while encrypted images B1and B2are obtained from encrypting Original Image B. Note that for implementation efficiency, matrices of corresponding pixels' intensity sub-values of the image of interest are processed simultaneously instead of individual pixel intensity sub-values.

Simulation results demonstrate that encryption using such an approach can resist security attaches under a variety of analyses including correlation analysis, information entropy, cipher cycle, histogram analysis, chosen-plaintext attacks, and brute force attacks. The described homomorphic image encryption scheme can be used in non real-time applications, such as archiving satellite images, some medical images, fingerprint images, or any confidential images in the visible electromagnetic spectrum range. Real-time applications may be possible with application of faster encryption and decryption algorithms.

Those skilled in the art will recognize that a wide variety of modifications, alterations, and combinations can be made with respect to the above described embodiments without departing from the scope of the invention, and that such modifications, alterations, and combinations are to be viewed as being within the ambit of the inventive concept.