# An Efficient Secret Key Homomorphic Encryption Used in Image Processing Service

Authors: Pan Yang; Xiaolin Gui; Jian An; Feng Tian
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Homomorphic encryption can protect user’s privacy when operating on user’s data in cloud computing. But it is not practical for wide using as the data and services types in cloud computing are diverse. Among these data types, digital image is an important personal data for users. There are also many image processing services in cloud computing. To protect user’s privacy in these services, this paper proposed a scheme using homomorphic encryption in image processing. Firstly, a secret key homomorphic encryption (IGHE) was constructed for encrypting image. IGHE can operate on encrypted floating numbers efficiently to adapt to the image processing service. Then, by translating the traditional image processing methods into the operations on encrypted pixels, the encrypted image can be processed homomorphically. That is, service can process the encrypted image directly, and the result after decryption is the same as processing the plain image. To illustrate our scheme, three common image processing instances were given in this paper. The experiments show that our scheme is secure, correct, and efficient enough to be used in practical image processing applications.


---

## Body

## 1. Introduction

Along with the arrival of the cloud computing fever, there emerge a lot of service outsourcing applications based on cloud computing platform (such as SaaS). Users who request the service just need to upload their data to the service and wait for the result. This brings users great benefits, but also the risk of privacy disclosure, because the service provider (SP) can access users’ plain sensitive information arbitrarily. To balance the privacy with usability of data in cloud computing, many computable encryption technologies are proposed, such as homomorphic encryptions [1–5]. The idea of these encryptions can be represented as follows.“Enc” represents the encryption process, and “Dec” represents the decryption process. For a functionf(π0,π1,…,πt) taking the plaintexts as input, there exists a function f′(ψ0,ψ1,…,ψt) (where ψk=Enc(πk)) taking the ciphertexts as input, such that(1)Decf′ψ0,ψ1,…,ψt=fπ0,π1,…,πt.According to (1), user uploads the encrypted data to service, and instead of using f to operate on user’s plain data, the service can operate on the encrypted data by using f′ and return to user the encrypted result. After decryption, user will get the expected result which is the same as f. Thus, the service can run correctly without knowing user’s plain data. And then, the privacy is safe from disclosure.Homomorphic encryption seems a good way to protect privacy in service outsourcing applications, especially when handling the integer data type. But as the data types in cloud computing are diverse, how to use homomorphic encryption in other types is still a challenging problem. For example, with the popularization of photograph equipment, a large amount of digital images are generated every day. It has become one of the most popular forms of personal data for users. Consequently, the online image processing services are widely used for users to edit their images. But the image may also contain privacy that the user does not want SP to see. To protect the privacy in this data type, we proposed a scheme using homomorphic encryption in image processing services.In broad terms, image processing includes all kinds of operations on the image. But it is hard to handle the privacy issues in all kinds of image processing using one scheme. So in this paper, the image processing mainly refers to the processes based on pixels. That is, the new color of pixel is computed according to the old ones. The operations on plain pixels can be seen as a functionf. Taking the old pixels and some other parameters (if necessary) as inputs, f outputs the new pixel. When using the traditional image encryptions [6–8], operating on the encrypted pixels is meaningless. Thus no one can process the encrypted image without decryption. However, by encrypting each pixel separately using homomorphic encryption, the service can operate on the encrypted pixels using f′. Then the service can process the encrypted image without decryption.Unfortunately, there are no appropriate homomorphic encryptions which can be used in image encryption yet. Unpadded-RSA [1] and ElGamal [2] cryptosystems satisfy (1) when f consists of only multiplication operations. But it needs both addition and multiplication operations in image processing. Neither do Goldwasser and Micali [3] or Paillier [4] cryptosystems fit image encryption, as f consists of only addition operations. Gentry’s fully homomorphic encryption [5] is too complex to apply in image processing, because it encrypts one bit each time, with the runtime more than 30 seconds even in “toy” security level [9]. The homomorphic cryptosystems proposed in [10, 11] are oriented to integers, but as the floating numbers are involved in operations in image processing, these cryptosystems cannot be used either. Besides, these are all public key encryptions which need a large key size to ensure the security. Thus, the sizes of ciphertexts are too large to store or transmit online.Through the above analysis, we need an efficient homomorphic encryption which can support both addition and multiplication operations on floating numbers. Then we can use it to encrypt the image and process the encrypted image directly. It seems that no existing work has ever proposed any solution for this problem. Our contributions are as follows:(i)
We propose an encrypted image processing model based on homomorphic encryption.(ii)
We improve Gentry’s homomorphic encryption to propose an efficient secret key homomorphic encryption which can support addition and multiplication operations on floating numbers (IGHE).(iii)
We use IGHE in image encryption and give the instances of processing encrypted image.The rest of this paper is organized as follows. Section2 outlines our encrypted image processing model and defines the notions that we need. In Section 3, we describe the improvement of Gentry’s homomorphic encryption (IGHE). Section 4 gives the method of image encryption using IGHE, followed by the instances of processing encrypted image. The experimental results are presented in Section 5. Finally, Section 6 concludes the paper.


## 2. Encrypted Image Processing Model

First of all, we construct an encrypted image processing model based on homomorphic encryption; see Figure1.Figure 1
The encrypted image processing model.
(a)
Image processing service model
(b)
Encrypted image processing service modelFigure1(a) is a common online image processing service model. The service has a set of image processing functions as f1,f2,…,fs. When image data owner (DO) uploads the image for a specific kind of process request, service provider (SP) will choose the corresponding function fk to process the image. As SP can access the original image, the privacy may be leaked. In Figure 1(b), DO encrypts the image using a homomorphic encryption before uploading. Thanks to this encryption, SP can operate on the encrypted image with the function f′k corresponding to fk and return to DO the encrypted result image. After decryption, DO can get the correct processed image. The result is the same as Figure 1(a). But as the image in server is always in encrypted form, the privacy is preserved.To realize the model, constructing an efficient homomorphic cryptosystem which supports both addition and multiplication operations on floating numbers is the key problem. We will discuss this in the next section. For clear description, the important notations used in this paper are summarized in Notations.


## 3. Improvement of Gentry’s Homomorphic Encryption

### 3.1. The Initial Construction of Gentry’s Scheme

Gentry denoted his initial scheme asε [5]. It started by fixing a ring R and an ideal lattice I⊂R, with BI as the basis. Then he used an algorithm IdealGen(R, BI) to output the public and secret keys BJpk and BJsk which are the bases of some ideal J, such that I+J=R. The plaintext space Πε was [R]BI, and “AddBI”, “MultBI” were the addition and multiplication in Πε. For π∈Πε, ε set the ciphertext ψ←Rπ+I+J. In decryption, π←(ψmodBJsk)modBI. For any function f(π0,π1,…,πt) consisting of “AddBI” and “MultBI”, f′(ψ0,ψ1,…,ψt) was generated by replacing “AddBI” and “MultBI” with “AddBJpk” and “MultBJpk”, respectively.Gentry proved that schemeε satisfies (1), that is,(2)DecεBJsk,f′ψ0,ψ1,…,ψt=fπ0,π1,…,πt.Butε is too complex to encrypt image. For one thing, to prevent the attacker from working out the secret key, the dimension n of public key needs to be large enough (n≥512 [9]). For another, ε encrypts one bit each time ({0,1} need to be translated into Πε as {0,1}). Thus, supposing that each of the elements of vector has l bits, the ciphertext will be n·l times larger than plaintext. Therefore, the byte of the encrypted image file will be enlarged at least 512l times. This is unrealistic, not to mention the extra cost for operating on each encrypted bit in the image processing. So we need to simplify ε to make it more efficient.


### 3.2. Simplifying Gentry’s Scheme

Our simplified scheme is denoted asεs. To reduce the size of key, we discard the public key encryption part. That is, the part of π+I is reserved, but the public key encryption part (the ideal J) will no longer be used. The ciphertext of π is set as ψ←Rπ+I. In decryption, π←[ψ]BI. Then, the key problem is how to construct the ideal lattice I.For anyb∈R, the ideal generated by b is (b)={b∗r∣r∈R}={Rot(b)·r∣r∈R}. According to Notations, (b) is an ideal lattice with Rot(b) as the basis. Thus, we set BI←Rot(b), and I is (b). In εs, b can be seen as the secret key. The encryption and decryption algorithms are described as follows.E
n
c
ε
s
(
b
,
π
). It takes as input the key b and a plaintext π. It sets r←RR and outputs ψ←π+b∗r.D
e
s
ε
s
(
b
,
ψ
). It takes as input the key b and a ciphertext ψ. It outputs π←[ψ]BI, where BI=Rot(b).Besides, there is an algorithm denoted as Eval which operates on ciphertext.E
v
a
l
ε
s
(
f
,
Ψ
). It takes as input a set of ciphertexts Ψ=ψ0,ψ1,…,ψt, where Decεs(b,ψk)=πk, and a function f(π0,π1,…,πt) consisting of “AddBI” and “MultBI”. It outputs f′(ψ0,ψ1,…,ψt) by replacing “πk”, “AddBI”, and “MultBI” with “ψk”, “+”, and “∗”, respectively.Now let us consider the correctness ofEvalεs; that is, εs satisfies (1).Proof.
ForΨ=ψ0,ψ1,…,ψt, ψk=πk+ik, where πk∈Π, and ik∈I, we have(3)Evalεsf,Ψ=f′ψ0,ψ1,…,ψt=f′π0+i0,π1+i1,…,πt+it,Decεsb,Evalεsf,Ψ=f′π0+i0,π1+i1,…,πt+itmodBI=f′π0,π1,…,πtmodBI.
Inf(π0,π1,…,πt), instead of computing “AddBI” and “MultBI”, we can compute “+” and “∗” to get a result π∈R and then output πmodBI. Thus,(4)f′π0,π1,…,πtmodBI=fπ0,π1,…,πt.
That is,εs satisfy (1).The security ofεs is the same as ε, that is, semantic security, as they are all based on ICP.Definition 1 (ideal coset problem (ICP) in [5]).
FixR, B, and an algorithm Samp1 that efficiently samples R. The challenger sets b←R{0,1}. If b=0, it sets r←RSamp1(R), t←rmodB. If b=1, it samples t uniformly from RmodB. The problem is guessing b by given (t,B).Theorem 2.
Suppose that there is an algorithmA1 that breaks the semantic security of εs with advantage ϵ. Then there is an algorithmA2 that solves the ICP with advantage ϵ/2.Proof.
The challenger sendsA2 an ICP instance (t,B). A2 sets β←R{0,1}, t0←t and samples t1 uniformly from RmodB. Then, A2 gives ψβ←Encεs(B,tβ) to A1; A1 sends back a guess of β as β′. Finally, A2 guesses b as b′=β⊙β′.
Ifb=0, ψ0 is a well-formed ciphertext. As t1 is uniformly random element of [R]B, and r is uniformly random element of R, then ψ1 is uniformly random element of R. In this case, A1 should have advantage ϵ to get β′=β, which translates into an advantage of ϵ for A2 to get b′=β⊙β′=1.
Ifb=1, both t0 and t1 are uniformly random elements of RmodB. In this case, whatever β is, the ciphertexts ψβ are uniformly random element of R. A1’s advantage is 0, which translates into an advantage of 0 for A2 to get b′=β⊙β′=1.
Overall,A2’s advantage is ϵ/2.The ICP asks one to decide whethert is uniform moduloB(b=1) or whether it was chosen according to a known “clumpier” distribution induced by Samp1 (b=0). According to [5], there is no such algorithm that can solve the ICP with an unnegligible probability. Thus, according to Theorem 2, the advantage of algorithm A1 breaking the semantic security of εs can be ignored; that is, εs is semantic security.WhenBI=Rot(b), the modular operation [v]BI can be calculated as v-b∗⌊b-1∗v⌉ or denoted as [v]b. As “∗” and b-1 can be operated with O(n·log⁡n) operations using the Fast Fourier Transform (FFT) [12], the time complexity of εs is O(n·log⁡n). Furthermore, as a secret key encryption, a small value of n will make εs security enough. Thus, εs is efficient and secure for being used in image encryption. But the plaintext space of εs is [R]b, while, in image processing, the data types include integer and float. So we need a mapping between the floats and R.


### 3.3. Expanding Plaintext Space into Floats

#### 3.3.1. A Mapping between Integers andR

For∀v∈R, v can be written as the polynomial ∑i=0n-1vi·ximodg(x). If we set x a fixed value (e.g., x=2 or 10), each v is corresponding to a number; this numeralization of v is denoted as ηx(v). Meanwhile, any integer v with v<ηxg(x) is equal to the polynomial ∑i=0n-1vi·ximodg(x), where vi=±v/ximodx; the sign of vi is the same as v. Thus, each number v is corresponding to an element in R, denoted as ρx(v). Thus, for an integer plaintext p<ηxg(x), in encryption (denoted as Encε1), after getting π←ρx(p), it outputs ψ←Encεs(b,π). In decryption (denoted as Decε1), when getting π←Decεs(b,ψ), it outputs p←ηx(π).This scheme is denoted asε1. We discuss the conditions to make ε1 satisfy (1), that is, Decε1b,h′ψ0,…,ψt=hp0,…,pt, where ψk=Encε1b,pk. The operations in h are “+” and “×” in real number field.Lemma 3.
For an integerN, if hp0,…,pt<min⁡N,ηxg(x) and 1/2·b-1≥N, then ε1 satisfies (1).Proof.
Obviouslyηxπk=pk, where πk=ρxpk. If hp0,…,pt<ηxgx, then ηxh′′π0,…,πt=hp0,…,pt, where h′′ consists of “+” and “∗” in R. Besides, we have proved that Decεsb,f′ψ0,…,ψt=fπ0,…,πt, where f′ is equivalent to h′.
Asf consists of “AddBI” and “MultBI”, [h′′]BI=f. Denoting the output of h′′ as h, then h=∑ihi2≤∑ihi·xi=ηx(h)<N≤1/2·b-1. According to Lemma 1 in [5], if h<1/2·b-1, then h∈[R]BI, that is, h′′=[h′′]BI.
Above all, we haveDecε1b,h′=ηxDecεs(b,f′)=h, that is, ε1 satisfies (1).


#### 3.3.2. A Mapping between Floats andR

Now we need to expand the plaintext space into floats. To encrypt a floating numberp which is accurate to x-m (i.e., p·xm-⌊p·xm⌉=0), we can change it into integer p·xm and encrypt p·xm to output the ciphertext ψ←Encε1(b,p·xm). In this case, Decε1(b,ψ)=p·xm, and Decε1(b,ψ1+ψ2)=(p1+p2)·xm. So, the correct output of decryption should be Decε1·x-m. But as Decε1(b,ψ1∗ψ2)=(p1·p2)·x2m, to keep the multiplication homomorphic, we redefine it (“∗(m)”) as u∗(m)v=u(m)∗v, where u(m)=u·x-mmodg(x), that is, ui(m)=ui+mmodn.Lemma 4.
If(u·v)·x2m≤ηxg(x) and (u·v)·xm-⌊(u·v)·xm⌉=0, then Decε1(b,ψu∗(m)ψv)=(u·v)·xm, where ψu=Encε1(b,u), ψv=Encε1(b,v).See the proof in AppendixB.Finally, our homomorphic encryption (IGHE) is described as follows.KeyGen
(
n
,
N
). It takes as input the security parameters n and N. It chooses a random vector b from Zn repeatedly until 1/2·b-1>N, and then it outputs (b,b-1).Enc
(
b
,
m
,
p
). It takes as input the key b and a plaintext p∈(-N,N). It sets π←ρx(⌊p·xm⌉); then, after choosing a random vector r from Zn, it outputs ψ←π+b∗r.Dec
(
b
,
m
,
ψ
). It takes as input the key b and a ciphertext ψ. It sets π←[ψ]b and outputs p←ηxπ·x-m.Eval
(
f
,
m
,
Ψ
). It takes as input a function f(p0,p1,…,pt) and a set of ciphertexts Ψ=ψ0,ψ1,…,ψt, where Dec(b, m, ψk)=pk. It outputs f′=ψ0,ψ1,…,ψt by replacing “pk”, “+”, and “×” in f with “ψk”, “+”, and “∗(m)” in R, respectively.According to Lemmas3 and 4, if f includest multiplications, as long as f≤ηxg(x)·x-t·m and f·xt·m-⌊f·xt·m⌉=0, IGHE satisfies (1). To gain a high accuracy with a small value of m, we set x=10. Next, we will use IGHE to realize the encrypted image processing model in Figure 1(b).We have proved thatεs is semantic security. If algorithm A3 can break the semantic security of IGHE, then, for εs, one can first map the ciphertext ψβ into float and use A2 to break the security of εs. Thus, IGHE is also semantic security.So far, we have introduced our homomorphic encryption IGHE which is simplified and improved from Gentry’s homomorphic encryption. The differences between IGHE and Gentry’s scheme are as follows:(i)
IGHE is a symmetric encryption, while Gentry is a public key encryption. The purpose of public key is for service to use the public key to operate on the encrypted data. We omitted the public key encryption part, because we have another way to let service operate on the encrypted data without using key (see Section4.2). The main benefit of symmetric encryption is that a smaller size of secret key can reach to the security level as high as public key. Then, in the same security level, as the size of key is smaller, our scheme is more efficient than Gentry’s scheme.(ii)
Gentry’s scheme is universal and fully homomorphic; it takes each bit as the plaintext. As the image processing can also be presented as a batch of operations of bit, theoretically the scheme can be used for encrypted image processing. But considering the complexity, it is hard to implement. While our scheme takes the byte as plaintext, and, after inducing the homomorphic addition and multiplication operations on floats, we can easily realize the encryption image processing.


## 3.1. The Initial Construction of Gentry’s Scheme

Gentry denoted his initial scheme asε [5]. It started by fixing a ring R and an ideal lattice I⊂R, with BI as the basis. Then he used an algorithm IdealGen(R, BI) to output the public and secret keys BJpk and BJsk which are the bases of some ideal J, such that I+J=R. The plaintext space Πε was [R]BI, and “AddBI”, “MultBI” were the addition and multiplication in Πε. For π∈Πε, ε set the ciphertext ψ←Rπ+I+J. In decryption, π←(ψmodBJsk)modBI. For any function f(π0,π1,…,πt) consisting of “AddBI” and “MultBI”, f′(ψ0,ψ1,…,ψt) was generated by replacing “AddBI” and “MultBI” with “AddBJpk” and “MultBJpk”, respectively.Gentry proved that schemeε satisfies (1), that is,(2)DecεBJsk,f′ψ0,ψ1,…,ψt=fπ0,π1,…,πt.Butε is too complex to encrypt image. For one thing, to prevent the attacker from working out the secret key, the dimension n of public key needs to be large enough (n≥512 [9]). For another, ε encrypts one bit each time ({0,1} need to be translated into Πε as {0,1}). Thus, supposing that each of the elements of vector has l bits, the ciphertext will be n·l times larger than plaintext. Therefore, the byte of the encrypted image file will be enlarged at least 512l times. This is unrealistic, not to mention the extra cost for operating on each encrypted bit in the image processing. So we need to simplify ε to make it more efficient.


## 3.2. Simplifying Gentry’s Scheme

Our simplified scheme is denoted asεs. To reduce the size of key, we discard the public key encryption part. That is, the part of π+I is reserved, but the public key encryption part (the ideal J) will no longer be used. The ciphertext of π is set as ψ←Rπ+I. In decryption, π←[ψ]BI. Then, the key problem is how to construct the ideal lattice I.For anyb∈R, the ideal generated by b is (b)={b∗r∣r∈R}={Rot(b)·r∣r∈R}. According to Notations, (b) is an ideal lattice with Rot(b) as the basis. Thus, we set BI←Rot(b), and I is (b). In εs, b can be seen as the secret key. The encryption and decryption algorithms are described as follows.E
n
c
ε
s
(
b
,
π
). It takes as input the key b and a plaintext π. It sets r←RR and outputs ψ←π+b∗r.D
e
s
ε
s
(
b
,
ψ
). It takes as input the key b and a ciphertext ψ. It outputs π←[ψ]BI, where BI=Rot(b).Besides, there is an algorithm denoted as Eval which operates on ciphertext.E
v
a
l
ε
s
(
f
,
Ψ
). It takes as input a set of ciphertexts Ψ=ψ0,ψ1,…,ψt, where Decεs(b,ψk)=πk, and a function f(π0,π1,…,πt) consisting of “AddBI” and “MultBI”. It outputs f′(ψ0,ψ1,…,ψt) by replacing “πk”, “AddBI”, and “MultBI” with “ψk”, “+”, and “∗”, respectively.Now let us consider the correctness ofEvalεs; that is, εs satisfies (1).Proof.
ForΨ=ψ0,ψ1,…,ψt, ψk=πk+ik, where πk∈Π, and ik∈I, we have(3)Evalεsf,Ψ=f′ψ0,ψ1,…,ψt=f′π0+i0,π1+i1,…,πt+it,Decεsb,Evalεsf,Ψ=f′π0+i0,π1+i1,…,πt+itmodBI=f′π0,π1,…,πtmodBI.
Inf(π0,π1,…,πt), instead of computing “AddBI” and “MultBI”, we can compute “+” and “∗” to get a result π∈R and then output πmodBI. Thus,(4)f′π0,π1,…,πtmodBI=fπ0,π1,…,πt.
That is,εs satisfy (1).The security ofεs is the same as ε, that is, semantic security, as they are all based on ICP.Definition 1 (ideal coset problem (ICP) in [5]).
FixR, B, and an algorithm Samp1 that efficiently samples R. The challenger sets b←R{0,1}. If b=0, it sets r←RSamp1(R), t←rmodB. If b=1, it samples t uniformly from RmodB. The problem is guessing b by given (t,B).Theorem 2.
Suppose that there is an algorithmA1 that breaks the semantic security of εs with advantage ϵ. Then there is an algorithmA2 that solves the ICP with advantage ϵ/2.Proof.
The challenger sendsA2 an ICP instance (t,B). A2 sets β←R{0,1}, t0←t and samples t1 uniformly from RmodB. Then, A2 gives ψβ←Encεs(B,tβ) to A1; A1 sends back a guess of β as β′. Finally, A2 guesses b as b′=β⊙β′.
Ifb=0, ψ0 is a well-formed ciphertext. As t1 is uniformly random element of [R]B, and r is uniformly random element of R, then ψ1 is uniformly random element of R. In this case, A1 should have advantage ϵ to get β′=β, which translates into an advantage of ϵ for A2 to get b′=β⊙β′=1.
Ifb=1, both t0 and t1 are uniformly random elements of RmodB. In this case, whatever β is, the ciphertexts ψβ are uniformly random element of R. A1’s advantage is 0, which translates into an advantage of 0 for A2 to get b′=β⊙β′=1.
Overall,A2’s advantage is ϵ/2.The ICP asks one to decide whethert is uniform moduloB(b=1) or whether it was chosen according to a known “clumpier” distribution induced by Samp1 (b=0). According to [5], there is no such algorithm that can solve the ICP with an unnegligible probability. Thus, according to Theorem 2, the advantage of algorithm A1 breaking the semantic security of εs can be ignored; that is, εs is semantic security.WhenBI=Rot(b), the modular operation [v]BI can be calculated as v-b∗⌊b-1∗v⌉ or denoted as [v]b. As “∗” and b-1 can be operated with O(n·log⁡n) operations using the Fast Fourier Transform (FFT) [12], the time complexity of εs is O(n·log⁡n). Furthermore, as a secret key encryption, a small value of n will make εs security enough. Thus, εs is efficient and secure for being used in image encryption. But the plaintext space of εs is [R]b, while, in image processing, the data types include integer and float. So we need a mapping between the floats and R.


## 3.3. Expanding Plaintext Space into Floats

### 3.3.1. A Mapping between Integers andR

For∀v∈R, v can be written as the polynomial ∑i=0n-1vi·ximodg(x). If we set x a fixed value (e.g., x=2 or 10), each v is corresponding to a number; this numeralization of v is denoted as ηx(v). Meanwhile, any integer v with v<ηxg(x) is equal to the polynomial ∑i=0n-1vi·ximodg(x), where vi=±v/ximodx; the sign of vi is the same as v. Thus, each number v is corresponding to an element in R, denoted as ρx(v). Thus, for an integer plaintext p<ηxg(x), in encryption (denoted as Encε1), after getting π←ρx(p), it outputs ψ←Encεs(b,π). In decryption (denoted as Decε1), when getting π←Decεs(b,ψ), it outputs p←ηx(π).This scheme is denoted asε1. We discuss the conditions to make ε1 satisfy (1), that is, Decε1b,h′ψ0,…,ψt=hp0,…,pt, where ψk=Encε1b,pk. The operations in h are “+” and “×” in real number field.Lemma 3.
For an integerN, if hp0,…,pt<min⁡N,ηxg(x) and 1/2·b-1≥N, then ε1 satisfies (1).Proof.
Obviouslyηxπk=pk, where πk=ρxpk. If hp0,…,pt<ηxgx, then ηxh′′π0,…,πt=hp0,…,pt, where h′′ consists of “+” and “∗” in R. Besides, we have proved that Decεsb,f′ψ0,…,ψt=fπ0,…,πt, where f′ is equivalent to h′.
Asf consists of “AddBI” and “MultBI”, [h′′]BI=f. Denoting the output of h′′ as h, then h=∑ihi2≤∑ihi·xi=ηx(h)<N≤1/2·b-1. According to Lemma 1 in [5], if h<1/2·b-1, then h∈[R]BI, that is, h′′=[h′′]BI.
Above all, we haveDecε1b,h′=ηxDecεs(b,f′)=h, that is, ε1 satisfies (1).


### 3.3.2. A Mapping between Floats andR

Now we need to expand the plaintext space into floats. To encrypt a floating numberp which is accurate to x-m (i.e., p·xm-⌊p·xm⌉=0), we can change it into integer p·xm and encrypt p·xm to output the ciphertext ψ←Encε1(b,p·xm). In this case, Decε1(b,ψ)=p·xm, and Decε1(b,ψ1+ψ2)=(p1+p2)·xm. So, the correct output of decryption should be Decε1·x-m. But as Decε1(b,ψ1∗ψ2)=(p1·p2)·x2m, to keep the multiplication homomorphic, we redefine it (“∗(m)”) as u∗(m)v=u(m)∗v, where u(m)=u·x-mmodg(x), that is, ui(m)=ui+mmodn.Lemma 4.
If(u·v)·x2m≤ηxg(x) and (u·v)·xm-⌊(u·v)·xm⌉=0, then Decε1(b,ψu∗(m)ψv)=(u·v)·xm, where ψu=Encε1(b,u), ψv=Encε1(b,v).See the proof in AppendixB.Finally, our homomorphic encryption (IGHE) is described as follows.KeyGen
(
n
,
N
). It takes as input the security parameters n and N. It chooses a random vector b from Zn repeatedly until 1/2·b-1>N, and then it outputs (b,b-1).Enc
(
b
,
m
,
p
). It takes as input the key b and a plaintext p∈(-N,N). It sets π←ρx(⌊p·xm⌉); then, after choosing a random vector r from Zn, it outputs ψ←π+b∗r.Dec
(
b
,
m
,
ψ
). It takes as input the key b and a ciphertext ψ. It sets π←[ψ]b and outputs p←ηxπ·x-m.Eval
(
f
,
m
,
Ψ
). It takes as input a function f(p0,p1,…,pt) and a set of ciphertexts Ψ=ψ0,ψ1,…,ψt, where Dec(b, m, ψk)=pk. It outputs f′=ψ0,ψ1,…,ψt by replacing “pk”, “+”, and “×” in f with “ψk”, “+”, and “∗(m)” in R, respectively.According to Lemmas3 and 4, if f includest multiplications, as long as f≤ηxg(x)·x-t·m and f·xt·m-⌊f·xt·m⌉=0, IGHE satisfies (1). To gain a high accuracy with a small value of m, we set x=10. Next, we will use IGHE to realize the encrypted image processing model in Figure 1(b).We have proved thatεs is semantic security. If algorithm A3 can break the semantic security of IGHE, then, for εs, one can first map the ciphertext ψβ into float and use A2 to break the security of εs. Thus, IGHE is also semantic security.So far, we have introduced our homomorphic encryption IGHE which is simplified and improved from Gentry’s homomorphic encryption. The differences between IGHE and Gentry’s scheme are as follows:(i)
IGHE is a symmetric encryption, while Gentry is a public key encryption. The purpose of public key is for service to use the public key to operate on the encrypted data. We omitted the public key encryption part, because we have another way to let service operate on the encrypted data without using key (see Section4.2). The main benefit of symmetric encryption is that a smaller size of secret key can reach to the security level as high as public key. Then, in the same security level, as the size of key is smaller, our scheme is more efficient than Gentry’s scheme.(ii)
Gentry’s scheme is universal and fully homomorphic; it takes each bit as the plaintext. As the image processing can also be presented as a batch of operations of bit, theoretically the scheme can be used for encrypted image processing. But considering the complexity, it is hard to implement. While our scheme takes the byte as plaintext, and, after inducing the homomorphic addition and multiplication operations on floats, we can easily realize the encryption image processing.


## 3.3.1. A Mapping between Integers andR

For∀v∈R, v can be written as the polynomial ∑i=0n-1vi·ximodg(x). If we set x a fixed value (e.g., x=2 or 10), each v is corresponding to a number; this numeralization of v is denoted as ηx(v). Meanwhile, any integer v with v<ηxg(x) is equal to the polynomial ∑i=0n-1vi·ximodg(x), where vi=±v/ximodx; the sign of vi is the same as v. Thus, each number v is corresponding to an element in R, denoted as ρx(v). Thus, for an integer plaintext p<ηxg(x), in encryption (denoted as Encε1), after getting π←ρx(p), it outputs ψ←Encεs(b,π). In decryption (denoted as Decε1), when getting π←Decεs(b,ψ), it outputs p←ηx(π).This scheme is denoted asε1. We discuss the conditions to make ε1 satisfy (1), that is, Decε1b,h′ψ0,…,ψt=hp0,…,pt, where ψk=Encε1b,pk. The operations in h are “+” and “×” in real number field.Lemma 3.
For an integerN, if hp0,…,pt<min⁡N,ηxg(x) and 1/2·b-1≥N, then ε1 satisfies (1).Proof.
Obviouslyηxπk=pk, where πk=ρxpk. If hp0,…,pt<ηxgx, then ηxh′′π0,…,πt=hp0,…,pt, where h′′ consists of “+” and “∗” in R. Besides, we have proved that Decεsb,f′ψ0,…,ψt=fπ0,…,πt, where f′ is equivalent to h′.
Asf consists of “AddBI” and “MultBI”, [h′′]BI=f. Denoting the output of h′′ as h, then h=∑ihi2≤∑ihi·xi=ηx(h)<N≤1/2·b-1. According to Lemma 1 in [5], if h<1/2·b-1, then h∈[R]BI, that is, h′′=[h′′]BI.
Above all, we haveDecε1b,h′=ηxDecεs(b,f′)=h, that is, ε1 satisfies (1).


## 3.3.2. A Mapping between Floats andR

Now we need to expand the plaintext space into floats. To encrypt a floating numberp which is accurate to x-m (i.e., p·xm-⌊p·xm⌉=0), we can change it into integer p·xm and encrypt p·xm to output the ciphertext ψ←Encε1(b,p·xm). In this case, Decε1(b,ψ)=p·xm, and Decε1(b,ψ1+ψ2)=(p1+p2)·xm. So, the correct output of decryption should be Decε1·x-m. But as Decε1(b,ψ1∗ψ2)=(p1·p2)·x2m, to keep the multiplication homomorphic, we redefine it (“∗(m)”) as u∗(m)v=u(m)∗v, where u(m)=u·x-mmodg(x), that is, ui(m)=ui+mmodn.Lemma 4.
If(u·v)·x2m≤ηxg(x) and (u·v)·xm-⌊(u·v)·xm⌉=0, then Decε1(b,ψu∗(m)ψv)=(u·v)·xm, where ψu=Encε1(b,u), ψv=Encε1(b,v).See the proof in AppendixB.Finally, our homomorphic encryption (IGHE) is described as follows.KeyGen
(
n
,
N
). It takes as input the security parameters n and N. It chooses a random vector b from Zn repeatedly until 1/2·b-1>N, and then it outputs (b,b-1).Enc
(
b
,
m
,
p
). It takes as input the key b and a plaintext p∈(-N,N). It sets π←ρx(⌊p·xm⌉); then, after choosing a random vector r from Zn, it outputs ψ←π+b∗r.Dec
(
b
,
m
,
ψ
). It takes as input the key b and a ciphertext ψ. It sets π←[ψ]b and outputs p←ηxπ·x-m.Eval
(
f
,
m
,
Ψ
). It takes as input a function f(p0,p1,…,pt) and a set of ciphertexts Ψ=ψ0,ψ1,…,ψt, where Dec(b, m, ψk)=pk. It outputs f′=ψ0,ψ1,…,ψt by replacing “pk”, “+”, and “×” in f with “ψk”, “+”, and “∗(m)” in R, respectively.According to Lemmas3 and 4, if f includest multiplications, as long as f≤ηxg(x)·x-t·m and f·xt·m-⌊f·xt·m⌉=0, IGHE satisfies (1). To gain a high accuracy with a small value of m, we set x=10. Next, we will use IGHE to realize the encrypted image processing model in Figure 1(b).We have proved thatεs is semantic security. If algorithm A3 can break the semantic security of IGHE, then, for εs, one can first map the ciphertext ψβ into float and use A2 to break the security of εs. Thus, IGHE is also semantic security.So far, we have introduced our homomorphic encryption IGHE which is simplified and improved from Gentry’s homomorphic encryption. The differences between IGHE and Gentry’s scheme are as follows:(i)
IGHE is a symmetric encryption, while Gentry is a public key encryption. The purpose of public key is for service to use the public key to operate on the encrypted data. We omitted the public key encryption part, because we have another way to let service operate on the encrypted data without using key (see Section4.2). The main benefit of symmetric encryption is that a smaller size of secret key can reach to the security level as high as public key. Then, in the same security level, as the size of key is smaller, our scheme is more efficient than Gentry’s scheme.(ii)
Gentry’s scheme is universal and fully homomorphic; it takes each bit as the plaintext. As the image processing can also be presented as a batch of operations of bit, theoretically the scheme can be used for encrypted image processing. But considering the complexity, it is hard to implement. While our scheme takes the byte as plaintext, and, after inducing the homomorphic addition and multiplication operations on floats, we can easily realize the encryption image processing.


## 4. Encrypted Image Processing Using IGHE

### 4.1. Image Encryption Using IGHE

The values of colors are less than 256, and it usually has only one multiplication in image processing. By choosing an appropriate value ofm and n, after process, it is easy to keep the result less than 10n-m-10-m (ηxg(x)·x-m when x=10) and accurate to 10-m. Thus, IGHE can be applied in encrypted image processing.An image withw width and h height consists of w×h pixels. As we know, a pixel can be seen as a combination of the three-primary colors, we denote the pixel in the ith row and jth column as Pi,j(p0,p1,p2), with p0,p1,p2 representing the color of red, green, and blue, respectively. Firstly, we use KeyGen to output the key b. Then, after reading the image file and getting the pixels array P={Pi,j}, we encrypt P by calling ImgEnc(b,m,P).ImgEnc
(
b
,
m
,
P
). For each pixel Pi,j(p0,p1,p2) in P, it encrypts p0,p1,p2 sequentially to get c0,c1,c2, where ck←Enc(b,m,pk). The ciphertext of Pi,j is denoted as Ci,j(c0,c1,c2). After getting all Ci,j, it outputs C←{Ci,j} as a w×h ciphertexts array of P.For a given image, there arew·h pixels with each having 3 integers. ImgEnc encrypts all these plaintexts separately. Thus, the time complexity of ImgEnc is O(w·h·n·log⁡n). C is the set of all the encrypted pixels, as each ciphertext is an n-dimensional column vector; Ci,j is an n×3 matrix. Thus, the size of C is O(w·h·n).In decryption algorithm, eachCi,j in C will be decrypted separately to get the pixel Pi,j(p0,p1,p2).ImgDec
(
b
,
m
,
C
). For each cipher pixel Ci,j in C, we decrypt c0,c1,c2 sequentially to get Pi,j(p0,p1,p2), where pk←⌊Dec(b,m,ck)⌉; if pk<0, set pk←0; if pk>255, set pk←255. Then, after getting all Pi,j, it outputs P←{Pi,j} as the pixels array of plain image.As the color must be an integer in[0,255], after getting pk←Dec(b,m,ck), the result will be rounded into the nearest integer in [0,255]. The time complexity of ImgDec is O(w·h·n·log⁡n).


### 4.2. Processing Encrypted Image

We concentrate on the processing method which is based on addition and multiplication operations on the pixels. In these processes, the new colorp′ in a pixel is calculated by a function fp0,p1,…,a0,a1,…, where pk represents the color of a pixel and ak represents the data from SP. As IGHE is a secret key encryption, SP does not have the key to encrypt ak. However, SP can translated ak into ρx(⌊ak·xm⌉), which is a special ciphertext with r=0 in Enc(b, m, ak). We denote this translation as Enc(m, ak), which can be run by SP without the key b.As shown in Figure1(b), firstly, user uploads the encrypted image by calling ImgEnc and asks for a processing method request corresponding to the function f. Then, SP returns to user the encrypted result by calling Eval(f,m,Ψ). Finally, by calling ImgDec, user will get the correct plain result same as Figure 1(a). In Eval, the function f′c0,c1,…,ψ(a)0,ψ(a)1,… was generated to process the encrypted image, where ck←Enc(b,m,pk), and ψ(a)k←Enc(m,ak). In these methods, as SP does not need any key, there is no need to share the key. User just needs to keep the secret key safely.In the image processing, we may like to change the color of the image, add a watermark (or photo frame) on the image, or change the size of the image. To illustrate our scheme, we use these three common kinds of image processing as instances.


#### 4.2.1. Color Transformation

The original color transformation is based on the color matrix [13]CM which is a 5×5 matrix. The ith row and jth column are denoted as cmij, where cmij is often a floating number. GivenCM and the original pixel Pi,j(p0,p1,p2), the resulting pixel P′i,j(p′0,p′1,p′2) is computed as(5)p′k=f1Pi,j,cmk0,…,cmk4=p0·cmk0+p1·cmk1+p2·cmk2+αi,j·cmk3+cmk4,where k is 0,1,2, and αi,j is the transparency of the pixel Pi,j. For the image without transparency, the default value of αi,j is 255.In the instance, DO wants to change the color of his image, such as grayness and binarization. But he does not know the value ofCM, while there are many kinds of color transformation operations in SP, with each kind corresponding to a value ofCM.DO uploads the ciphertextC, then, in encrypted image color transformation, SP uses the encrypted form ofCM (ψij←Enc(m,cmij)) to compute each encrypted resulting pixel C′i,j(c′0,c′1,c′2).(6)c′k=f′1Ci,j,ψk0,…,ψk4=c0∗mψk0+c1∗mψk1+c2∗mψk2+Encm,αi,j·cmk3+cmk4.As SP knowsαi,j,cmk3,cmk4, he can compute and then encrypt αi,j·cmk3+cmk4 as one plaintext.


#### 4.2.2. Image Addition

Give two imagesP1, P2, add P1 on P2 with a transparency tp; then the resulting pixel P′i,j is(7)P′i,j=f2tp,P1i,j,P2i,jtp·P1i,j+1-tp·P2i,j.In one instance, IO gives SP two encrypted imagesC1 and C2 and asks SP to add them with the transparency tp. The encrypted resulting pixel is (8)C′i,j=f′2tp,C1i,j,C2i,j=Encm,tp∗mC1i,j+Encm,1-tp∗mC2i,j.In another instance, IO gives SP one encrypted imageC and chooses a plain image P (e.g., a photo frame) from SP to add on the encrypted image with the transparency tp. In SP’s image, the pixels may have different transparencies αi,j; when added on Ci,j, the true transparency of Pi,j is tp·αi,j. And the encrypted resulting pixel is(9)C′i,j=f′2tp,Pi,j,αi,j,Ci,j=Encm,tp·αi,j·Pi,j+Encm,1-tp·αi,j∗mCi,j.As SP knowsαi,j,tp,pk, he can compute and then encrypt tp·αi,j·pk and 1-tp·αi,j as one plaintext.


#### 4.2.3. Image Scaling

Image scaling is also common image processing. Here we discuss the quadratic linear interpolation method. The size of original imageP is w×h. Suppose that, after scaling, the size of P′ becomes λ·w×γ·h. Then, P′i,j(p′0,p′1,p′2)(i=0,1,…,λ·w-1,j=0,1,…,γ·h-1) is computed according to four adjacent pixels in P. They are Ps,t,Ps,t+1,Ps+1,t,Ps+1,t+1, where s=i/λ, t=j/γ, and(10)P′i,j=f2Ps,t,Ps,t+1,Ps+1,t,Ps+1,t+1,u,v=Ps,t·1-u·1-v+Ps,t+1·u·1-v+Ps+1,t·1-u·v+Ps+1,t+1·u·v,where u=i/λ-s,v=j/γ-t.In the instance, IO asks SP to scale the encrypted imageCλ times in width and γ times in height. So the encrypted resulting pixel is(11)C′i,j=f′3Cs,t,Cs,t+1,Cs+1,t,Cs+1,t+1,u,v=Cs,t∗mmt0+Cs,t+1∗mt1+Cs+1,t∗mt2+Cs+1,t+1∗mt3,where t0=Encm,(1-u)·(1-v), t1=Encm,u·(1-v), t2=Encm,(1-h)·v, and t3=Encm,u·v.


## 4.1. Image Encryption Using IGHE

The values of colors are less than 256, and it usually has only one multiplication in image processing. By choosing an appropriate value ofm and n, after process, it is easy to keep the result less than 10n-m-10-m (ηxg(x)·x-m when x=10) and accurate to 10-m. Thus, IGHE can be applied in encrypted image processing.An image withw width and h height consists of w×h pixels. As we know, a pixel can be seen as a combination of the three-primary colors, we denote the pixel in the ith row and jth column as Pi,j(p0,p1,p2), with p0,p1,p2 representing the color of red, green, and blue, respectively. Firstly, we use KeyGen to output the key b. Then, after reading the image file and getting the pixels array P={Pi,j}, we encrypt P by calling ImgEnc(b,m,P).ImgEnc
(
b
,
m
,
P
). For each pixel Pi,j(p0,p1,p2) in P, it encrypts p0,p1,p2 sequentially to get c0,c1,c2, where ck←Enc(b,m,pk). The ciphertext of Pi,j is denoted as Ci,j(c0,c1,c2). After getting all Ci,j, it outputs C←{Ci,j} as a w×h ciphertexts array of P.For a given image, there arew·h pixels with each having 3 integers. ImgEnc encrypts all these plaintexts separately. Thus, the time complexity of ImgEnc is O(w·h·n·log⁡n). C is the set of all the encrypted pixels, as each ciphertext is an n-dimensional column vector; Ci,j is an n×3 matrix. Thus, the size of C is O(w·h·n).In decryption algorithm, eachCi,j in C will be decrypted separately to get the pixel Pi,j(p0,p1,p2).ImgDec
(
b
,
m
,
C
). For each cipher pixel Ci,j in C, we decrypt c0,c1,c2 sequentially to get Pi,j(p0,p1,p2), where pk←⌊Dec(b,m,ck)⌉; if pk<0, set pk←0; if pk>255, set pk←255. Then, after getting all Pi,j, it outputs P←{Pi,j} as the pixels array of plain image.As the color must be an integer in[0,255], after getting pk←Dec(b,m,ck), the result will be rounded into the nearest integer in [0,255]. The time complexity of ImgDec is O(w·h·n·log⁡n).


## 4.2. Processing Encrypted Image

We concentrate on the processing method which is based on addition and multiplication operations on the pixels. In these processes, the new colorp′ in a pixel is calculated by a function fp0,p1,…,a0,a1,…, where pk represents the color of a pixel and ak represents the data from SP. As IGHE is a secret key encryption, SP does not have the key to encrypt ak. However, SP can translated ak into ρx(⌊ak·xm⌉), which is a special ciphertext with r=0 in Enc(b, m, ak). We denote this translation as Enc(m, ak), which can be run by SP without the key b.As shown in Figure1(b), firstly, user uploads the encrypted image by calling ImgEnc and asks for a processing method request corresponding to the function f. Then, SP returns to user the encrypted result by calling Eval(f,m,Ψ). Finally, by calling ImgDec, user will get the correct plain result same as Figure 1(a). In Eval, the function f′c0,c1,…,ψ(a)0,ψ(a)1,… was generated to process the encrypted image, where ck←Enc(b,m,pk), and ψ(a)k←Enc(m,ak). In these methods, as SP does not need any key, there is no need to share the key. User just needs to keep the secret key safely.In the image processing, we may like to change the color of the image, add a watermark (or photo frame) on the image, or change the size of the image. To illustrate our scheme, we use these three common kinds of image processing as instances.


### 4.2.1. Color Transformation

The original color transformation is based on the color matrix [13]CM which is a 5×5 matrix. The ith row and jth column are denoted as cmij, where cmij is often a floating number. GivenCM and the original pixel Pi,j(p0,p1,p2), the resulting pixel P′i,j(p′0,p′1,p′2) is computed as(5)p′k=f1Pi,j,cmk0,…,cmk4=p0·cmk0+p1·cmk1+p2·cmk2+αi,j·cmk3+cmk4,where k is 0,1,2, and αi,j is the transparency of the pixel Pi,j. For the image without transparency, the default value of αi,j is 255.In the instance, DO wants to change the color of his image, such as grayness and binarization. But he does not know the value ofCM, while there are many kinds of color transformation operations in SP, with each kind corresponding to a value ofCM.DO uploads the ciphertextC, then, in encrypted image color transformation, SP uses the encrypted form ofCM (ψij←Enc(m,cmij)) to compute each encrypted resulting pixel C′i,j(c′0,c′1,c′2).(6)c′k=f′1Ci,j,ψk0,…,ψk4=c0∗mψk0+c1∗mψk1+c2∗mψk2+Encm,αi,j·cmk3+cmk4.As SP knowsαi,j,cmk3,cmk4, he can compute and then encrypt αi,j·cmk3+cmk4 as one plaintext.


### 4.2.2. Image Addition

Give two imagesP1, P2, add P1 on P2 with a transparency tp; then the resulting pixel P′i,j is(7)P′i,j=f2tp,P1i,j,P2i,jtp·P1i,j+1-tp·P2i,j.In one instance, IO gives SP two encrypted imagesC1 and C2 and asks SP to add them with the transparency tp. The encrypted resulting pixel is (8)C′i,j=f′2tp,C1i,j,C2i,j=Encm,tp∗mC1i,j+Encm,1-tp∗mC2i,j.In another instance, IO gives SP one encrypted imageC and chooses a plain image P (e.g., a photo frame) from SP to add on the encrypted image with the transparency tp. In SP’s image, the pixels may have different transparencies αi,j; when added on Ci,j, the true transparency of Pi,j is tp·αi,j. And the encrypted resulting pixel is(9)C′i,j=f′2tp,Pi,j,αi,j,Ci,j=Encm,tp·αi,j·Pi,j+Encm,1-tp·αi,j∗mCi,j.As SP knowsαi,j,tp,pk, he can compute and then encrypt tp·αi,j·pk and 1-tp·αi,j as one plaintext.


### 4.2.3. Image Scaling

Image scaling is also common image processing. Here we discuss the quadratic linear interpolation method. The size of original imageP is w×h. Suppose that, after scaling, the size of P′ becomes λ·w×γ·h. Then, P′i,j(p′0,p′1,p′2)(i=0,1,…,λ·w-1,j=0,1,…,γ·h-1) is computed according to four adjacent pixels in P. They are Ps,t,Ps,t+1,Ps+1,t,Ps+1,t+1, where s=i/λ, t=j/γ, and(10)P′i,j=f2Ps,t,Ps,t+1,Ps+1,t,Ps+1,t+1,u,v=Ps,t·1-u·1-v+Ps,t+1·u·1-v+Ps+1,t·1-u·v+Ps+1,t+1·u·v,where u=i/λ-s,v=j/γ-t.In the instance, IO asks SP to scale the encrypted imageCλ times in width and γ times in height. So the encrypted resulting pixel is(11)C′i,j=f′3Cs,t,Cs,t+1,Cs+1,t,Cs+1,t+1,u,v=Cs,t∗mmt0+Cs,t+1∗mt1+Cs+1,t∗mt2+Cs+1,t+1∗mt3,where t0=Encm,(1-u)·(1-v), t1=Encm,u·(1-v), t2=Encm,(1-h)·v, and t3=Encm,u·v.


## 4.2.1. Color Transformation

The original color transformation is based on the color matrix [13]CM which is a 5×5 matrix. The ith row and jth column are denoted as cmij, where cmij is often a floating number. GivenCM and the original pixel Pi,j(p0,p1,p2), the resulting pixel P′i,j(p′0,p′1,p′2) is computed as(5)p′k=f1Pi,j,cmk0,…,cmk4=p0·cmk0+p1·cmk1+p2·cmk2+αi,j·cmk3+cmk4,where k is 0,1,2, and αi,j is the transparency of the pixel Pi,j. For the image without transparency, the default value of αi,j is 255.In the instance, DO wants to change the color of his image, such as grayness and binarization. But he does not know the value ofCM, while there are many kinds of color transformation operations in SP, with each kind corresponding to a value ofCM.DO uploads the ciphertextC, then, in encrypted image color transformation, SP uses the encrypted form ofCM (ψij←Enc(m,cmij)) to compute each encrypted resulting pixel C′i,j(c′0,c′1,c′2).(6)c′k=f′1Ci,j,ψk0,…,ψk4=c0∗mψk0+c1∗mψk1+c2∗mψk2+Encm,αi,j·cmk3+cmk4.As SP knowsαi,j,cmk3,cmk4, he can compute and then encrypt αi,j·cmk3+cmk4 as one plaintext.


## 4.2.2. Image Addition

Give two imagesP1, P2, add P1 on P2 with a transparency tp; then the resulting pixel P′i,j is(7)P′i,j=f2tp,P1i,j,P2i,jtp·P1i,j+1-tp·P2i,j.In one instance, IO gives SP two encrypted imagesC1 and C2 and asks SP to add them with the transparency tp. The encrypted resulting pixel is (8)C′i,j=f′2tp,C1i,j,C2i,j=Encm,tp∗mC1i,j+Encm,1-tp∗mC2i,j.In another instance, IO gives SP one encrypted imageC and chooses a plain image P (e.g., a photo frame) from SP to add on the encrypted image with the transparency tp. In SP’s image, the pixels may have different transparencies αi,j; when added on Ci,j, the true transparency of Pi,j is tp·αi,j. And the encrypted resulting pixel is(9)C′i,j=f′2tp,Pi,j,αi,j,Ci,j=Encm,tp·αi,j·Pi,j+Encm,1-tp·αi,j∗mCi,j.As SP knowsαi,j,tp,pk, he can compute and then encrypt tp·αi,j·pk and 1-tp·αi,j as one plaintext.


## 4.2.3. Image Scaling

Image scaling is also common image processing. Here we discuss the quadratic linear interpolation method. The size of original imageP is w×h. Suppose that, after scaling, the size of P′ becomes λ·w×γ·h. Then, P′i,j(p′0,p′1,p′2)(i=0,1,…,λ·w-1,j=0,1,…,γ·h-1) is computed according to four adjacent pixels in P. They are Ps,t,Ps,t+1,Ps+1,t,Ps+1,t+1, where s=i/λ, t=j/γ, and(10)P′i,j=f2Ps,t,Ps,t+1,Ps+1,t,Ps+1,t+1,u,v=Ps,t·1-u·1-v+Ps,t+1·u·1-v+Ps+1,t·1-u·v+Ps+1,t+1·u·v,where u=i/λ-s,v=j/γ-t.In the instance, IO asks SP to scale the encrypted imageCλ times in width and γ times in height. So the encrypted resulting pixel is(11)C′i,j=f′3Cs,t,Cs,t+1,Cs+1,t,Cs+1,t+1,u,v=Cs,t∗mmt0+Cs,t+1∗mt1+Cs+1,t∗mt2+Cs+1,t+1∗mt3,where t0=Encm,(1-u)·(1-v), t1=Encm,u·(1-v), t2=Encm,(1-h)·v, and t3=Encm,u·v.


## 5. Experiments

We run some experiments to test the performance of our scheme. All the experiments are carried out on a computer equipped with two processors, each with 3.1 GHz clock speed, and the computer has 4 GB RAM.


### 5.1. Security

Now we analyze the statistical security of the encrypted image.In our scheme, the ciphertextck∈R is an n-dimensional integer vectors. We use 4 bytes to represent the integer; then each element of ck can represent a new pixel in the encrypted image. The top byte represents the transparency α, and the rest represent the color of red, green, and blue, respectively. So a plain pixel will be changed into n×3 new pixels in encrypted image. We store the encrypted image in.PNG format and calculate the histograms of original and encrypted image, respectively. Figure 2(a) is the original image, and its histogram is shown in (b). Figure 2(c) is a part of the encrypted image, and the histogram is shown in (d).Figure 2
The histogram of the original and encrypted image.
(a)
The original image
(b)
Histogram of the original image
(c)
The encrypted image (partly)
(d)
Histogram of the encrypted imageFigure2 indicates that the histogram of the encrypted image is fairly uniform and is significantly different from that of the original image. Thus, our scheme can resist the statistical analysis attack.


### 5.2. Correctness

We do the same type of processing both on the original imageP and on the encrypted image C to get the processed image P′ and C′. The error between P′i,j and C′i,j is(12)erri,j=∑k=02Decb,m,c′k-p′k3.Iferri,j≠0, the encryption pixel of C′i,j is error. If all the erri,j are zero, our scheme is correct.As the floating numbers are accurate to10-m, the value of m will affect the correctness of our scheme. To test this, we choose different value of m. For each m, we encrypt an image P to get C and do the same kind of image processing on P and C to get P′ and C′. Then, we compute the erri,j for every pixel.We fixn=8. Table 1 shows the correctness of our scheme with different value of m. The “Error Rate” means the rate of error C′i,j in C. “None” means decrypted C with no process. In “color transformation (CT),” each time we set the value ofCM randomly. The elements ofCM are accurate to 0.001. In “image addition (Add.),” we add the same image on P and C several times. Each time we set a different value of transparency ranging from 0 to 100%. In “image scaling (Scal.),” each time we choose λ from (0,4], and set γ=λ.Table 1
The correctness with different value ofm.
m
Error rate (%)
Max. error
Average error
None
CT
Add.
Scal.
CT
Add.
Scal.
CT
Add.
Scal.
1
0
28.1
99.3
54.4
17
13
26
2.34
5.46
5.45
2
0
15.5
0
37.6
3
0
3
0.26
0
0.54
3
0
0
0
8.4
0
0
1
0
0
0.08
4
0
0
0
0
0
0
0
0
0
0In Table1, the error becomes less and smaller as m increases. When m increases to 4, there is no error; then our scheme is correct. The error rate of “None” is zero, so no matter what m is, if we decrypt an encrypted image with no process, we can get the original image with no error. That is because the value of color is integers, so the accuracy of 100 is enough.In “Add.”, the transparency is a number with two decimals, so whenm=2, there is no error any more. In “CT”, as the random value ofCM has three decimals, the error is zero when m=3. In “Scal.”, the data may be an infinite decimal. But since the value of color is smaller than 256, when m≥4, 256·10-m<0.1. So there will be no error after rounding the result to the nearest integer.Figure3 shows some result of image P′ (left image) and image Dec(C′) (right image) after the image processing when n=8 and m=4. In (a), the left image is the original image. We encrypt the left image and decrypt the cipher image to get the right image. In (b), we remove the color (grayness) of the original image; this is realized by settingCM a specific value. In (c), we set the elements ofCM random values. And in (d), we choose a photo frame to add on the original image; the transparency is 60%.Figure 3
The result ofP′ and Dec(C′).
(a)
No processing
(b)
Color Trans. (grayness)
(c)
Color Trans. (randomly)
(d)
Image additionThe two images in each figure look the same. According to Table1, they do have the same pixel in the same position.Above all, the image can be processed in encrypted form. After decryption, user will get the same image as processing directly on plain image. Thus, our scheme is correct.


### 5.3. Efficiency

Figure4 shows the runtime of the key generation, encryption, decryption, addition, and multiplication processes of our scheme IGHE and Gentry’s scheme.Figure 4
The runtime of IGHE and Gentry’s scheme.We can see, when, in the same value ofn, our scheme is more efficient than Gentry’s scheme. When n is 32, the runtime of “DEC” of Gentry is even more than 100 ms, which is not marked in Figure 4. What is more, note that as Gentry’s scheme is a public encrypt system, to keep security, n is at least 512 [9]. Then, the running time of each process will be more than 5 s. Thus, IGHE is more efficient than Gentry’s scheme.Encryption and decryption will cost extra running time. Besides, processing encrypted image is slower than processing plain image. We test the efficiency of ImgEnc, ImgDec, and the three encrypted image processing algorithms (CT, Add., and Scal.). We choose different values ofn and record the running time of each algorithm. Figure 5 shows the average running time of each algorithm on one pixel. The common time means the running time of plain image processing.Figure 5
The running time of each algorithm.From Figure5, we can see that all the running time increases as n increases. When n=8, all algorithms can process each pixel in 10 μs. This is 10 times slower than processing the plain pixel. But for a 1-megapixel image, the process can be finished in 10 seconds. To protect the privacy, this compromise of efficiency is worthy. When n is 16 or 32, it may take a long time to process the large size image, but our scheme is still suitable for the small size image.


### 5.4. Size of Encrypted Image

After encryption, the size of encrypted image is enlarged. By setting different value ofn, we record the size of secret key, the size of encrypted image, and the space of encrypted image file in.PNG format. See Table 2. “Plain” means the original image.Table 2
The size of key and image in different value ofn.
n
Key (byte)
Width (pixel)
Height (pixel)
.PNG (Kb)
Plain
—
256
256
192
8
128
768
2048
6K
16
256
768
4096
12K
32
512
768
8192
24KAs described in Section5.1, the key and ciphertext of IGHE are n-dimensional vectors, with each element having a 4-byte integer. The size of secret key is O(n). A plain color takes one byte. After encryption, the encrypted color takes 4n bytes, with n bytes representing the transparency. So, in the encrypted image, the width grows by 3 times, and the height grows n times. And the size of  .PNG file is enlarged 4n times.Figure6 shows that, with the size of image increasing, both the size of encrypted image and the runtime of CT process are increasing.Figure 6
Runtime of CT and encrypted picture size with different original picture size.Forn=16, the time for processing a 5-megapixel image is about 1 minute, but the size of the encrypted image is up to 200 megapixels. So considering both the efficiency and the communication overhead, our scheme is suitable for small size image encryption and processing, but not proper for larger size of image yet. According to Figure 6, for n=8, the proper size range may be less than 2 megapixels, and, for n=16, it should be less than 1 megapixel.


## 5.1. Security

Now we analyze the statistical security of the encrypted image.In our scheme, the ciphertextck∈R is an n-dimensional integer vectors. We use 4 bytes to represent the integer; then each element of ck can represent a new pixel in the encrypted image. The top byte represents the transparency α, and the rest represent the color of red, green, and blue, respectively. So a plain pixel will be changed into n×3 new pixels in encrypted image. We store the encrypted image in.PNG format and calculate the histograms of original and encrypted image, respectively. Figure 2(a) is the original image, and its histogram is shown in (b). Figure 2(c) is a part of the encrypted image, and the histogram is shown in (d).Figure 2
The histogram of the original and encrypted image.
(a)
The original image
(b)
Histogram of the original image
(c)
The encrypted image (partly)
(d)
Histogram of the encrypted imageFigure2 indicates that the histogram of the encrypted image is fairly uniform and is significantly different from that of the original image. Thus, our scheme can resist the statistical analysis attack.


## 5.2. Correctness

We do the same type of processing both on the original imageP and on the encrypted image C to get the processed image P′ and C′. The error between P′i,j and C′i,j is(12)erri,j=∑k=02Decb,m,c′k-p′k3.Iferri,j≠0, the encryption pixel of C′i,j is error. If all the erri,j are zero, our scheme is correct.As the floating numbers are accurate to10-m, the value of m will affect the correctness of our scheme. To test this, we choose different value of m. For each m, we encrypt an image P to get C and do the same kind of image processing on P and C to get P′ and C′. Then, we compute the erri,j for every pixel.We fixn=8. Table 1 shows the correctness of our scheme with different value of m. The “Error Rate” means the rate of error C′i,j in C. “None” means decrypted C with no process. In “color transformation (CT),” each time we set the value ofCM randomly. The elements ofCM are accurate to 0.001. In “image addition (Add.),” we add the same image on P and C several times. Each time we set a different value of transparency ranging from 0 to 100%. In “image scaling (Scal.),” each time we choose λ from (0,4], and set γ=λ.Table 1
The correctness with different value ofm.
m
Error rate (%)
Max. error
Average error
None
CT
Add.
Scal.
CT
Add.
Scal.
CT
Add.
Scal.
1
0
28.1
99.3
54.4
17
13
26
2.34
5.46
5.45
2
0
15.5
0
37.6
3
0
3
0.26
0
0.54
3
0
0
0
8.4
0
0
1
0
0
0.08
4
0
0
0
0
0
0
0
0
0
0In Table1, the error becomes less and smaller as m increases. When m increases to 4, there is no error; then our scheme is correct. The error rate of “None” is zero, so no matter what m is, if we decrypt an encrypted image with no process, we can get the original image with no error. That is because the value of color is integers, so the accuracy of 100 is enough.In “Add.”, the transparency is a number with two decimals, so whenm=2, there is no error any more. In “CT”, as the random value ofCM has three decimals, the error is zero when m=3. In “Scal.”, the data may be an infinite decimal. But since the value of color is smaller than 256, when m≥4, 256·10-m<0.1. So there will be no error after rounding the result to the nearest integer.Figure3 shows some result of image P′ (left image) and image Dec(C′) (right image) after the image processing when n=8 and m=4. In (a), the left image is the original image. We encrypt the left image and decrypt the cipher image to get the right image. In (b), we remove the color (grayness) of the original image; this is realized by settingCM a specific value. In (c), we set the elements ofCM random values. And in (d), we choose a photo frame to add on the original image; the transparency is 60%.Figure 3
The result ofP′ and Dec(C′).
(a)
No processing
(b)
Color Trans. (grayness)
(c)
Color Trans. (randomly)
(d)
Image additionThe two images in each figure look the same. According to Table1, they do have the same pixel in the same position.Above all, the image can be processed in encrypted form. After decryption, user will get the same image as processing directly on plain image. Thus, our scheme is correct.


## 5.3. Efficiency

Figure4 shows the runtime of the key generation, encryption, decryption, addition, and multiplication processes of our scheme IGHE and Gentry’s scheme.Figure 4
The runtime of IGHE and Gentry’s scheme.We can see, when, in the same value ofn, our scheme is more efficient than Gentry’s scheme. When n is 32, the runtime of “DEC” of Gentry is even more than 100 ms, which is not marked in Figure 4. What is more, note that as Gentry’s scheme is a public encrypt system, to keep security, n is at least 512 [9]. Then, the running time of each process will be more than 5 s. Thus, IGHE is more efficient than Gentry’s scheme.Encryption and decryption will cost extra running time. Besides, processing encrypted image is slower than processing plain image. We test the efficiency of ImgEnc, ImgDec, and the three encrypted image processing algorithms (CT, Add., and Scal.). We choose different values ofn and record the running time of each algorithm. Figure 5 shows the average running time of each algorithm on one pixel. The common time means the running time of plain image processing.Figure 5
The running time of each algorithm.From Figure5, we can see that all the running time increases as n increases. When n=8, all algorithms can process each pixel in 10 μs. This is 10 times slower than processing the plain pixel. But for a 1-megapixel image, the process can be finished in 10 seconds. To protect the privacy, this compromise of efficiency is worthy. When n is 16 or 32, it may take a long time to process the large size image, but our scheme is still suitable for the small size image.


## 5.4. Size of Encrypted Image

After encryption, the size of encrypted image is enlarged. By setting different value ofn, we record the size of secret key, the size of encrypted image, and the space of encrypted image file in.PNG format. See Table 2. “Plain” means the original image.Table 2
The size of key and image in different value ofn.
n
Key (byte)
Width (pixel)
Height (pixel)
.PNG (Kb)
Plain
—
256
256
192
8
128
768
2048
6K
16
256
768
4096
12K
32
512
768
8192
24KAs described in Section5.1, the key and ciphertext of IGHE are n-dimensional vectors, with each element having a 4-byte integer. The size of secret key is O(n). A plain color takes one byte. After encryption, the encrypted color takes 4n bytes, with n bytes representing the transparency. So, in the encrypted image, the width grows by 3 times, and the height grows n times. And the size of  .PNG file is enlarged 4n times.Figure6 shows that, with the size of image increasing, both the size of encrypted image and the runtime of CT process are increasing.Figure 6
Runtime of CT and encrypted picture size with different original picture size.Forn=16, the time for processing a 5-megapixel image is about 1 minute, but the size of the encrypted image is up to 200 megapixels. So considering both the efficiency and the communication overhead, our scheme is suitable for small size image encryption and processing, but not proper for larger size of image yet. According to Figure 6, for n=8, the proper size range may be less than 2 megapixels, and, for n=16, it should be less than 1 megapixel.


## 6. Conclusion

In this paper, we improve Gentry’s homomorphic encryption to propose an efficient, simplified secret key homomorphic encryption (IGHE). We use it in the image encryption, so that the image can be processed in encrypted form to protect the privacy. Any image processing that consists of addition and multiplication operations on single pixel can be translated into the encrypted-formed process. We give the color transformation, image addition, and image scaling as the examples.By using our scheme, the image can be processed in the server in encrypted form; after decryption in client, user can get the correct processed image that is the same as processing the plain image. So our scheme can protect privacy in online image processing. Our scheme is secure, but it enlarges the running time of process and the space for storing encrypted image. So our scheme is not proper for processing large size of image yet.As the value of color is less than 256, when translating into vector, most elements of the vector are zero. To use these elements, we will research on translating batch colors in one vector to decrease the running time and the size of encrypted image.



---

*Source: 7695751-2017-05-14.xml*