Enabling Practical and Privacy-Preserving Image Processing
Chao Wang Shubing Yang Xiaoyan Sun Jun Dai Dongfang Zhao

















    




Enabling Practical and Privacy-Preserving Image Processing
    
Chao Wang
cwang17@wpi.edu

Worcester Polytechnic Institute
Shubing Yang
sueyoung@uw.edu

University of Washington
Xiaoyan Sun
xsun7@wpi.edu

Worcester Polytechnic Institute
Jun Dai
jdai@wpi.edu

Worcester Polytechnic Institute
Dongfang Zhao
dzhao@uw.edu

University of Washington

    
=============================================================================================================================================================================================================================================================================================







empty


 

[1]Chao Wang and Shubing Yang made equal contributions to this work. Corresponding authors: Drs. Dongfang Zhao and Jun Dai.





 §.§ Abstract


Fully Homomorphic Encryption (FHE) enables computations on encrypted data, preserving confidentiality without the need for decryption. However, FHE is often hindered by significant performance overhead, particularly for high-precision and complex data like images. Due to serious efficiency issues, traditional FHE methods often encrypt images by monolithic data blocks (such as pixel rows), instead of pixels. However, this strategy compromises the advantages of homomorphic operations and disables pixel-level image processing. In this study, we address these challenges by proposing and implementing a pixel-level homomorphic encryption approach, , based on the CKKS scheme.
To enhance the computational efficiency of CKKS in image processing, we propose three novel caching mechanisms to pre-encrypt radix values or frequently occurring pixel values, substantially reducing redundant encryption operations. Extensive experiments demonstrate that our approach achieves up to a 19-fold improvement in encryption speed

compared to the original CKKS, while maintaining high image quality. Additionally, real-world image applications such as mean filtering, brightness enhancement, image matching and watermarking are tested based on FHE, showcasing up to a 91.53% speed improvement. We also proved that our method is IND-CPA (Indistinguishability under Chosen Plaintext Attack) secure, providing strong encryption security. These results underscore the practicality and efficiency of , marking a significant advancement in privacy-preserving image processing at scale.






§ INTRODUCTION


Fully homomorphic encryption (FHE), a revolutionary concept pioneered by Gentry <cit.>, has emerged as a focal point in privacy-preserving computational research. Its unprecedented ability to perform arbitrary computations on encrypted data without decryption has catalyzed a paradigm shift in secure data processing, particularly in sensitive domains such as healthcare and finance. Various FHE schemes have been proposed, including BFV <cit.>, BGV <cit.> and CKKS <cit.>, each designed to address specific computational needs and applications. However, despite its transformative potential, FHE continues to face challenges in computational efficiency and practical implementation when applied to real-world scenarios, especially in the realms of cloud computing and medical imaging <cit.>, where data integrity and confidentiality are paramount <cit.>.

While extant research on homomorphic encryption has predominantly concentrated on optimizing underlying mathematical constructs and enhancing the efficiency of fundamental arithmetic operations on ciphertexts <cit.>, the specific challenges inherent in applying FHE to image data have received comparatively little attention.
Due to the substantial computational overhead and low efficiency, current implementations for FHE-based image encryption typically treat images as monolithic data blocks <cit.>, encrypting them without considering the images' intrinsic structure and properties. An example is to encrypt the image with CKKS by pixel rows, instead of individual pixels, to reduce the number of encryption operations and thus reduce total time needed for encryption. However, this approach compromises the advantages of homomorphic operations and greatly impedes the practical application of FHE in image-related tasks <cit.>. 









In the domain of image processing, encryption by pixel is often required to offer unparalleled flexibility and granularity. Despite its higher computational demands, pixel-wise encryption enables a diverse range of sophisticated homomorphic operations directly on encrypted data <cit.>. This method excels in facilitating advanced image processing techniques such as mean filtering, brightness adjustment, and watermarking, all while maintaining data privacy <cit.>. The pixel-level granularity not only enhances privacy protection but also provides precise control over each image element, making it ideal for applications dealing with sensitive visual data or requiring intricate manipulation of encrypted images.

While encryption by row or even by image offers certain performance and efficiency advantages, particularly in processing speed and resource utilization, encryption by pixel presents a more versatile foundation for advanced homomorphic image processing. Although it may initially seem less efficient due to the increased number of encryption operations, the pixel-wise approach opens up a wealth of possibilities for complex algorithms and fine-grained data manipulation. 






In response to these limitations, we propose a novel pixel-level homomorphic encryption approach, iCHEETAH (image-focused Caching-optimized fully Homomorphic Encryption for Efficient Transformation of Assets with High resolutions) based on the CKKS framework, which is renowned for its support of approximate arithmetic <cit.>. This granular approach facilitates fine-grained pixel-level control over encrypted data and enables the direct implementation of various pixel-level image processing operations on ciphertexts. 
The reason why we choose CKKS as the base scheme is because CKKS is the only FHE scheme supporting homomorphic operations over floating numbers, which are commonly used in image processing (e.g., intermediate results). 
To combat the efficiency issue of pixel-level encryption, we introduce three types of caching mechanism, radix-based caching, scanning-based caching, and full caching, to pre-compute and store encrypted radix or frequently occurring pixel values. This approach achieves a remarkable acceleration in the encryption process. 

Particularly, the full caching mechanism results in a more than 19-fold speed improvement compared to original CKKS methods.
This substantial performance boost makes large-scale image encryption and processing both feasible and highly efficient, underscoring the practical potential of FHE-based privacy-preserving techniques.









Furthermore, to showcase the versatility of our pixel-level homomorphic encryption approach, we implement a comprehensive suite of fundamental image processing operations, including image brightening, contrast enhancement, and denoising, directly on encrypted data. By leveraging the homomorphic properties of the CKKS scheme, we execute these operations without compromising the encryption of the images, thereby ensuring the utmost privacy and security of sensitive visual information. Our experimental results demonstrate the efficacy of our approach and highlight its potential to enable privacy-preserving image processing across various domains. 

Threat Model. 

Our threat model involves a secure system for storing and processing confidential images (such as medical ones), utilizing pixel-level homomorphic encryption.
We assumes that users (such as medical institutions) need to upload sensitive images to the central storage (such as cloud, or central servers) for processing and sharing. The primary assets we aim to protect are the images and the associated encryption keys.

The adversary in our model is assumed to have potential access to the central storage, either as an external attacker or a curious but honest insider within the organization. We assume the storage provider is “honest but curious”  correctly executing operations but potentially attempting to learn about the data they're processing <cit.>. The users and institutions involved are considered trusted entities with secure local environments for encryption and decryption processes.

Additionally, our threat model explicitly assumes that while attackers may observe the encrypted data (ciphertext) within the central storage, they are unable to compromise or gain access to the users' encryption keys required to decrypt this data. As a result, even if the attacker has full visibility of the ciphertext, the lack of access to the decryption keys ensures that the data remains secure and unreadable.

Figure <ref> represents our threat model. It compares two scenarios: non-homomorphic encryption and homomorphic encryption using the CKKS scheme. In the non-homomorphic scenario, images are encrypted before upload but must be decrypted for processing, creating a vulnerability window where an attacker could potentially access sensitive patient data. Our proposed homomorphic encryption scenario uses CKKS to encrypt images before upload, allowing all processing to occur on encrypted data without decryption in the central storage <cit.>. This eliminates the vulnerability window present in the non-homomorphic approach but introduces a trade-off: the initial CKKS encryption process is significantly slower than non-homomorphic methods. The primary security goal is to maintain the confidentiality of images throughout their lifecycle in the central storage, enabling secure processing without exposing unencrypted data.





Our approach guards against potential attacks such as data interception during upload or download and unauthorized access to decrypted images (in the non-homomorphic scenario). The use of CKKS homomorphic encryption mitigates many of these risks by ensuring data remains encrypted during processing. However, the performance impact of CKKS encryption creates a trade-off between security and efficiency that must be carefully balanced. Our work focuses on enhancing the encryption efficiency for pixel-level CKKS-based FHE to make it more practical for real-world image applications, without compromising security.





Contributions. The key insights and contributions of this paper are summarized as follows.
    
    
    
  * First, we propose a novel pixel-level homomorphic encryption approach that adapts CKKS to operate on individual pixels, enabling fine-grained control over encrypted image data while preserving homomorphic properties (Section <ref>). To dramatically increase processing speed, we introduce three caching mechanisms – radix-based, scanning-based, and full caching – that significantly boost the efficiency of CKKS-based encryption, making FHE practical for fast and secure image processing (Section <ref>).


    
  * Second, we prove that our method is IND-CPA (Indistinguishability under Chosen Plaintext Attack) secure, providing strong encryption security. We include a detailed analysis and proof to confirm this, illustrating that our approach combines both high efficiency and robust protection, ensuring it is both secure and practical (Section <ref>). 

    
        

        
        
        
  * Third, we demonstrate the versatility and practicality of our approach by implementing a range of fundamental image processing operations directly on encrypted data, such as mean filtering, brightness enhancement, image matching, and watermarking. Our experimental results validate the effectiveness of our technique and highlight its potential for enabling privacy-preserving image processing across various domains, including healthcare and finance (Section <ref>). We also utilize hundreds of real and complex images from the USC-SIPI <cit.> database to demonstrate the applicability of our approach to a wide range of images (Section <ref>).
        
        
        
        
        
        
    



§ BACKGROUND

In this section, we briefly review FHE and CKKS, to facilitate a comprehensive understanding.



 §.§ Fully Homomorphic Encryption (FHE)

Fully Homomorphic Encryption (FHE) stands as a groundbreaking cryptographic method, enabling computations on encrypted data without the need for prior decryption, as initially proposed by Rivest in 1978 <cit.>. Gentry  <cit.> introduced the first viable framework for fully homomorphic encryption using lattice-based cryptography, a type of cryptographic approach that relies on the hardness of mathematical problems related to lattices in high-dimensional spaces. Lattice is a grid-like structure in mathmatics. Gentry's method allows for both addition and multiplication operations on encrypted data, enabling the construction of circuits (such as circuits composed of gates) to perform arbitrary computations <cit.>. The approach [id=SY]of Gentry involves several stages where noise is initially introduced and then carefully managed <cit.>. [id=SY]The noise refers to a small amount of random data added to the ciphertext to ensure security. It is introduced as part of the encryption process to make it difficult for an attacker to recover the original plaintext from the ciphertext <cit.>.This ensures that an unlimited number of additions and multiplications can be performed without excessively amplifying the noise. C. Gentry, A. Sahai, and B. Waters (GSW) <cit.> in 2013 introduced a new method for constructing FHE schemes that eliminates the costly “relinearization” step in homomorphic multiplications.














Noise management is critical in FHE. The noise level η in a ciphertext c is controlled to remain manageable after a series of operations, often using techniques like bootstrapping[id=SY], which reduces accumulated noise and enables further computations by refreshing the ciphertext through homomorphic decryption and re-encryption, ensuring the ciphertext's integrity remains uncompromised.

















 



 §.§ CKKS


CKKS (Cheon-Kim-Kim-Song) was originally introduced by Cheon, Kim, Kim and Song in 2016 <cit.>. It leverages the RLWE (Ring Learning with Errors) problem, a foundational problem in lattice-based cryptography [id=SY]that involves adding small random errors to polynomial equations, making it difficult for adversaries to solve and ensuring security while supporting efficient homomorphic operations on encrypted data.  Table <ref> shows key parameters of CKKS we use in this paper <cit.>. 




CKKS scheme supports arithmetic operations over ℂ^N/2. [id=SY]ℂ^N/2  represents a space of complex vectors of length N/2, where N is a power of 2.
The plaintext space and ciphertext space are defined over the same domain, as given by the formula ℤ_Q[X]/(X^N + 1), 



[id=SY]where ℤ_Q is the ring of integers modulo Q and X is the polynomial variable.

The batch encoding of this scheme maps an array of complex numbers to a polynomial with the property ℂ^N/2↔ℤ_Q[X]/(X^N + 1),



where ↔ denotes the encoding and decoding processes between the two sides.


The property of the encoding and decoding is given by decode(encode(m_1) ⊗encode(m_2)) ≈ m_1 ⊙ m_2,



where ⊗ represents a component-wise product, and ⊙ represents a nega-cyclic convolution.

In CKKS, N represents the ring dimension, and Q is the ciphertext modulus. Increasing N and Q enhances security but also increases computational complexity. A larger N boosts security by expanding key size and encrypted data complexity. However, it also increases encryption/decryption time and storage needs. Additionally, a larger N improves noise tolerance, supporting more homomorphic operations. Conversely, a larger Q enhances precision and noise management but raises computational demands. Thus, choosing N balances security and performance, while selecting Q manages precision and noise tolerance.







  §.§.§ RLWE


RLWE (Ring Learning with Errors) <cit.> 
 is defined over a polynomial ring R = ℤ[X]/f(X),



where f(X) is typically a cyclotomic polynomial, and a modulus q ∈ℤ [id=SY](q is a positive integer that defines the modulus for the coefficients of polynomials).


Let R_q = R/qR be the quotient ring. 

Given a secret element s ∈ R_q and access to a set of noisy ring products, the RLWE problem can be described as (a_i, b_i = a_i · s + e_i) ∈ R_q × R_q,



where a_i represents uniformly random elements in R_q, [id=SY]b_i is the polynomial generated in the encryption process and e_i denotes small error terms sampled from a discrete Gaussian distribution. The RLWE problem is to distinguish the pairs (a_i, b_i) from uniformly random pairs in R_q × R_q <cit.>.



  §.§.§ CKKS Basics


RLWE provides a strong foundation for lattice-based cryptography, enabling secure and efficient encryption schemes. CKKS builds on this by extending these capabilities to homomorphic encryption, allowing for approximate arithmetic on encrypted data.

Key generation in CKKS involves the following steps:

    
  * Select a secret key s ∈ R_Q, typically sampled from a small discrete distribution.
    
  * Generate a public key (a, b = a · s + e), where a is uniformly random in R_Q and e is sampled from a discrete Gaussian distribution. The public key is (a, b) ∈ R_Q × R_Q.
    
  * Generate an evaluation key required for homomorphic operations.



To encrypt a plaintext m ∈ R_Q, the CKKS encryption process is as follows:

    
  * Encode the plaintext message m into a polynomial m(X) ∈ R_Q, where a cyclotomic polynomial ring is R_Q = ℤ_Q[X]/(X^N + 1).
    
    
    
  * Choose a random polynomial r ∈ R_Q and compute the ciphertext (ct_0, ct_1) as ct_0 = r · a + m + e_0 and ct_1 = r · b + e_1,
    
    
    
    where e_0, e_1 are small error terms.





To decrypt a ciphertext (ct_0, ct_1), the decryption algorithm computes m' = ct_0 - s · ct_1 = m + e',



where e' is the combined error term. If the error is sufficiently small, the original message m can be recovered by rounding. <cit.>






  §.§.§ Operations of CKKS


The CKKS scheme allows for approximate arithmetic on encrypted data, making it well-suited for applications in machine learning and signal processing <cit.>. In CKKS, plaintexts are encoded as complex vectors, and ciphertexts are structured to support homomorphic addition and multiplication, albeit with some approximation error. There are two basic homomorphic operations in CKKS: homomorphic addition (⊕) and homomorphic multiplication (⊗).

Homomorphic addition in CKKS is straightforward. Given two ciphertexts ct_1 and ct_2 that encrypt plaintexts m_1 and m_2, respectively, their sum is computed as ct_add = ct_1 ⊕ ct_2.



This operation results in a new ciphertext ct_add that encrypts the sum of the plaintexts, i.e., m_1 + m_2. The addition of ciphertexts does not introduce additional noise beyond what is present in the original ciphertexts, preserving the integrity of the computation.

Homomorphic multiplication is more complex due to the need to handle the growth of noise and manage scaling factors. For two ciphertexts ct_1 and ct_2, the product is computed as ct_mul = ct_1 ⊗ ct_2.



The resulting ciphertext ct_mul encrypts the product of the plaintexts m_1 × m_2. However, multiplication increases both the degree and noise in the ciphertext, making it necessary to apply a process known as relinearization.

Relinearization reduces the degree of the resulting ciphertext back to its original form, which is crucial for maintaining efficiency in further operations. This is done by using an evaluation key evk generated during the key generation phase ct_rel = Relin(ct_mul, evk).



Here, ct_rel is the relinearized ciphertext, which now has a reduced degree, making it more manageable for subsequent operations.

After multiplication, the ciphertext may require rescaling to maintain the balance between the ciphertext and the plaintext. Rescaling involves dividing the ciphertext by a scaling factor Δ to reduce the noise ct_rescaled = Rescale(ct_rel, Δ)



This operation helps in maintaining the correctness of the plaintext after decryption and prevents the noise from overwhelming the signal.





§ OUR APPROACH



In the following sections, we will provide a detailed overview of our approach (Section <ref>), the caching mechanisms (Section <ref>), how to add randomness (Section <ref>), and our approach's compliance to IND-CPA security (Section <ref>). 




 §.§ Overview


Our approach is designed to encrypt image data while preserving the homomorphic properties of the ciphertext, thereby enabling ciphertext-based image processing. 
To accomplish this, implementing pixel-level FHE for image encryption is essential, however, it will entail a substantial time overhead. Based on the CKKS scheme, our approach achieves pixel-level image encryption and addresses the incurred time overhead through the strategic use of precomputation and caching. The approach is also structured to ensure that the encrypted data is resistant to chosen plaintext attacks (CPA) while maintaining computational efficiency.

Figure <ref> shows our approach overview. Adapted from the CKKS scheme, this approach begins with encoding and encrypting plaintext values, which are then cached to be used in subsequent operations. The plaintext values can be encrypted and cached in three ways: Radix-based caching that encrypts radix values, scanning-based caching that scans pixel values contained in an image and then encrypts these values, and full caching that encrypts all possible pixel values. 

Based on the using scenario, one of the three caching strategies can be selected to produce the cached ciphertexts. These ciphertexts are then directly used during the image encryption process and thus effectively reduces the computational complexity.

Once the ciphertexts for radices or pixel values are cached, theoretically the image can be encrypted by directly using the cached values to encrypt each pixel. However, this will suffer from CPA because identical pixel values result in identical ciphertexts due to using cached values. Adversaries can reveal the plaintexts by encrypting chosen plaintexts and comparing the ciphertexts, which is known as CPA. Therefore, our approach also needs to add randomness to the ciphertext of each pixel to make sure same plaintexts will generate different ciphertexts. We impose randomness through two different homomorphic operation strategies: 1) For radix-based caching, we perform some extra adding and subtracting operations to the cached ciphertext of the original pixel, such as adding ciphertext of 32, and then substrcting ciphertext of 16 twice.

2) For scanning-based and full caching, we add cached ciphertexts of zeros to the cached ciphertext of the original pixel. The ciphertext of zero can be different every time when zero is encrypted, and thus brings in randomness.
Both strategies do not change the decrypted value for the original pixel, guaranteeing that the encrypted image can be accurately decrypted and the integrity of the original data is preserved. More details about randomness is in Section <ref>.




 












































 §.§ Radix-based Caching, Scanning-based Caching, and Full Caching



To address the performance challenges of pixel-level FHE encryption, which is crucial for enabling ciphertext-based image processing, a strategic approach is needed to accelerate FHE operations. Section <ref> reviews existing work on HE acceleration, but few of these methods are directly applicable to the goals of this paper, or fully consider the unique characteristics of image data. In contrast, the design of  is informed by our insights on image data, with the underlying rationale detailed below:

Insight 1: Pixel-level image data consists exclusively of integer values. Consequently, pixel-level FHE image encryption is inherently encrypting a matrix of integers, with each operation carried out at the level of individual pixel values. To expedite the homomorphic encryption of various integer values, it is effective to cache the encryption of specific unit values and reconstruct the ciphertext for a target value by applying homomorphic additions to the cached ciphertexts of the corresponding unit values that sum to the target value. A natural selection for unit values is the radices. This strategy, rooted in math, is consistent with previous works, such as <cit.> and <cit.>, despite their differing objectives and scenarios. This caching strategy based on CKKS is formalized as follows.

Radix-based Caching. Radix-based caching leverages base-r representation to decompose each value in the dataset into a sum of powers of r. For any value p in the dataset, it can be represented as a sum of distinct powers of r, where each component is then encrypted using the CKKS scheme:

    c_p = ∑_i=0^nCKKS.Enc(r^k_i)

By precomputing and caching the ciphertexts for these powers of r, computational overhead during the encryption process is significantly reduced, as retrieving the ciphertext for any pixel value becomes a simple lookup operation. A common choice for the radix is 2, i.e., r=2, where the CKKS ciphertexts of 0, 2, 4, 8, 16, … are precomputed and cached.

Insight 2: Pixel values frequently recur in image data. Images often contain frequently occurring values within their pixel datasets. By identifying and caching the ciphertexts of these frequently occurring pixel values, we can further optimize the homomorphic encryption process. Specifically, because many images have large regions with uniform or similar pixel values, this strategy can significantly enhance performance in image encryption. Additionally, it is adaptable to handle a wide range of values beyond image data. We refer to this strategy as scanning-based caching.

Scanning-based Caching.  Scanning-based caching conducts a pre-processing scan of the dataset, and identifies the most common values, p_1, p_2, …, p_k. For each value p_j, we compute and store the corresponding ciphertext:

    c_p_j = CKKS.Enc(p_j)

Scanning-based Caching can be used in many circumstances. When encrypting the image, these precomputed ciphertexts are retrieved from the cache, thereby avoiding the need to repeatedly encrypt the same pixel values. This caching strategy reduces the computational burden and enhances the overall efficiency of the encryption process, particularly in images with high redundancy or repeated patterns.

Insight 3: Pixel values in an image are drawn from a finite set of numbers. An image is a visual representation made up of a grid of pixels, each corresponding to a specific point. In digital imaging, we assume the use of the RGB color scheme, where each pixel's color is defined by a combination of Red, Green, and Blue. Each color channel is represented by a pixel value ranging from 0 to 255, with 0 indicating no intensity and 255 indicating full intensity. We therefore pursue offline caching of all such values, referring to this strategy as full caching. Other schemes such as HSV (Hue, Saturation, Value) and HSL (Hue, Saturation, Lightness) are not focus of this paper and can be the future work.  

Full Caching. Full caching involves precomputing and caching the ciphertexts for all possible pixel values p in the range [0, 255], ensuring that every potential pixel value has a corresponding cached ciphertext c_p:

    c_p = CKKS.Enc(p)

This approach is perfectly suited for image processing and ensures that each pixel value in the image can be encrypted efficiently without the need for on-the-fly computation. While scanning-based caching can handle cases where plaintext values are indefinite, full caching are applicable to cases where all possible plaintext values are already known. 








































 §.§ Adding Randomness


When ciphertexts are exposed, they become vulnerable to chosen-plaintext attacks (CPA). Thus, it is essential to introduce randomness each time a cached ciphertext is used.

For radix-based caching, we proposed to iterate through each precomputed ciphertext in radixes[i] and randomly decide whether to add it to the main ciphertext Ctxt[i], where i is the iteration index. If this addition occurs, the process then subtracts radixes[i-1] from Ctxt[i] a total of r times, effectively introducing a controlled form of randomness to the ciphertext modification process:




    Ctxt[i] ⊕radixes[i] ⊖ r ×radixes[i-1]

where ⊕ represents the homomorphic addition between 2 cipertexts and ⊖ represents the homomorphic subtraction between 2 ciphertexts. For example, if radix r=2 and i=5, the randomness for Ctxt[5] can be done through 

    Ctxt[5] ⊕ 2^5 ⊖ 2 × 2^4


For scanning-based caching and full caching, we implement a thread pool-like mechanism, called “randomness pool”, by creating a pool consisting exclusively of precomputed ciphertexts of zeros. This pool ensures a continuous and efficient supply of ciphertexts of zeros, which are retrieved as needed during encryption or homomorphic operations. This pool consists of pre-encrypted zero values {c_z1, c_z2, …, c_zn}, where each c_zi is an encrypted zero:

    c_zi = CKKS.Enc(0)

During the encryption process, for each pixel value p, a randomly selected zero ciphertext c_zi from the pool is added to the cached ciphertext:

    c_p, final = c_p + c_zi

This addition ensures that identical pixel values do not produce identical ciphertexts. By maintaining the certain number of encrypted zeros in the randomness opol,  is provably IND-CPA secure (see Section <ref>) while reducing the computational load associated with image encryption.













 encrypts the pixel values of an image using the CKKS scheme and then caches the ciphertexts to accelerate subsequent operations on the encrypted data. Assuming that the pixel values of the image lie within the range [0, 255], we can represent each pixel value as an element in the integer set, i.e., p ∈{0, 1, 2, …, 255}. For each pixel value p, we apply the CKKS encryption scheme to generate the corresponding ciphertext c_p = CKKS.Enc(p), which is then stored in a cache to avoid redundant encryption in future operations.

Specifically, since there are only 256 possible pixel values, we precompute and cache these 256 ciphertexts, denoted as {c_0, c_1, c_2, …, c_255}. During the encryption of an image, for each pixel value p, we can directly reference the corresponding cached ciphertext c_p, significantly reducing the time complexity of the encryption process. This caching strategy not only minimizes computational overhead but also enhances the overall efficiency of the encryption process. Mathematically, this precomputation approach is analogous to constructing a lookup table, where the encrypted mapping of each pixel value p is pre-stored as a cached ciphertext, enabling retrieval in O(1) time.


Building on this approach, the implementation optimizes the caching mechanism by ensuring that all 256 possible pixel values are pre-encoded as ciphertexts using the CKKS encryption scheme. This is done by encoding each value p into a plaintext format m_p, encrypting it, and storing the result as a ciphertext c_p in memory:

    c_p = CKKS.Enc(m_p)

where m_p = p, p ∈ [0, 255].

By doing so, we guarantee that the system can handle pixel values efficiently during image encryption operations without the need for on-the-fly computation, which is both time-consuming and computationally expensive.

Since adding encrypted zeros is essential for the security of this method, generating the encrypted zeros is an indispensable step. To save the time of encrypting zeros and speed up the image encryption process, a secondary list of zero-valued ciphertexts {c_z_1, c_z_2, …, c_z_n} is generated and stored, where each c_z_i corresponds to an encrypted zero value. These zero-valued ciphertexts are then randomly selected and added to the primary pixel ciphertexts during the encryption process to ensure that identical pixel values do not result in identical ciphertexts:

    c_p^final = c_p + c_z_i,

where c_p is the cached ciphertext for pixel value p, and c_z_i is a randomly selected zero ciphertext. This randomization adds a layer of security by introducing variability in the encrypted output, even for identical pixel values.


This method of caching precomputed ciphertexts is critical for large-scale image encryption, where the pixel values are densely populated. Without such a cache, the system would face significant delays due to repetitive encryption operations. The cache not only reduces encryption time but also lowers the overall computational burden, which is particularly advantageous when processing high-resolution images or performing operations on encrypted data in real-time.

Overall, the cache serves as an essential component of , enabling efficient encryption of image data while maintaining the robustness of the underlying homomorphic encryption scheme. By leveraging precomputation and storage of ciphertexts, the system ensures fast and secure processing of pixel data, making it well-suited for applications where both performance and security are paramount.
































































 §.§ Security Analysis



In this section, we establish that our modified CKKS scheme, which includes caching ciphertexts for plaintexts 0 to 255 and the use of pre-encrypted zeros, maintains IND-CPA (Indistinguishability under Chosen Plaintext Attack) security. This is achieved by reducing the security of the modified scheme to that of the original CKKS scheme.

Assume for the sake of contradiction that the modified CKKS scheme Π̃ is not IND-CPA secure. This would imply the existence of a probabilistic polynomial-time (PPT) adversary 𝒜 capable of distinguishing between the encryptions of two plaintexts m_0 and m_1 under Π̃ with a non-negligible advantage:

    | [𝒜(Π̃(m_0)) = 1] - [𝒜(Π̃(m_1)) = 1] | ≥ϵ(n),

where ϵ(n) is a non-negligible function of the security parameter n.

To derive a contradiction, we construct a PPT adversary ℬ, which uses 𝒜 as a subroutine to break the IND-CPA security of the original CKKS scheme Π. The adversary ℬ is provided with a public key pk and receives two challenge ciphertexts c_0 = Π(m_0) and c_1 = Π(m_1) from the IND-CPA challenger for Π. Then, ℬ randomly selects a ciphertext z from the set Z = {Π(0)} of pre-encrypted zeros. The adversary ℬ computes the following ciphertexts:

    c̃_0 = c_0 + z   and  c̃_1 = c_1 + z

Subsequently, ℬ feeds the ciphertexts c̃_0 and c̃_1 to 𝒜 and outputs 𝒜's guess as its own.

Since 𝒜 can distinguish between c̃_0 and c̃_1 with a non-negligible advantage, ℬ would similarly distinguish between c_0 and c_1, thereby breaking the IND-CPA security of the original CKKS scheme Π. This contradicts the established security of the CKKS scheme, which is proven to be IND-CPA secure under the hardness assumption of the Ring-LWE problem. Hence, no such adversary 𝒜 can exist, and we conclude that the modified CKKS scheme Π̃ is also IND-CPA secure.

It is important to note that the use of zero ciphertexts does not significantly impact noise levels, thus preserving the correctness of decryption. Furthermore, caching encryptions of known plaintexts introduces no additional vulnerabilities, as these ciphertexts are generated using the original CKKS encryption function, which is secure.



    



 §.§ Security Analysis




In this section, we establish that our modified CKKS scheme, which includes the caching of ciphertexts for plaintexts 0 to 255 and the use of pre-encrypted zeros, maintains IND-CPA (Indistinguishability under Chosen Plaintext Attack) security. This is accomplished by demonstrating that the security of our approach can be reduced to the security of the original CKKS scheme.

The following format/presentation looks like being generated by GPT. Please take a look at the security proof in other published papers.

Assumption: Suppose, for the sake of contradiction, that the modified CKKS scheme Π̃ is not IND-CPA secure. Specifically, assume there exists a probabilistic polynomial-time (PPT) adversary 𝒜 capable of distinguishing between the encryptions of two plaintexts m_0 and m_1 under Π̃ with non-negligible advantage:

    | [𝒜(Π̃(m_0)) = 1] - [𝒜(Π̃(m_1)) = 1] | ≥ϵ(n),

where ϵ(n) is a non-negligible function of the security parameter n.

To derive a contradiction, we construct a PPT adversary ℬ that leverages 𝒜 as a subroutine to break the IND-CPA security of the original CKKS scheme Π.

Adversary Construction:


    
  * ℬ is given a public key pk and receives two challenge ciphertexts c_0 = Π(m_0) and c_1 = Π(m_1) from the IND-CPA challenger for Π.
    
  * ℬ selects a zero ciphertext z uniformly at random from the set Z = {Π(0)} of pre-encrypted zeros.
    
  * ℬ then computes:
    
    c̃_0 = c_0 + z   and  c̃_1 = c_1 + z

    
  * Finally, ℬ runs 𝒜 on the ciphertexts c̃_0 and c̃_1, and outputs whatever 𝒜 outputs as its own guess for the challenge bit.


Since 𝒜 can distinguish between c̃_0 and c̃_1 with a non-negligible advantage, the adversary ℬ will similarly distinguish between c_0 and c_1, thereby breaking the IND-CPA security of the original CKKS scheme Π.

However, this contradicts with the established security of CKKS, which is proven to be IND-CPA secure under the hardness assumption of the Ring-LWE problem. Therefore, no such adversary 𝒜 can exist, and we conclude that our modified CKKS scheme Π̃ is also IND-CPA secure.

Remarks:


    
  * The inclusion of zero ciphertexts does not significantly impact noise levels, thus preserving the decryption correctness.
    
  * Caching encryptions of known plaintexts introduces no additional vulnerabilities, as these ciphertexts are generated using the original CKKS encryption function, which is secure.




















































§ EVALUATION





This section will present our evaluation objectives (Section <ref>), setup of experiments (Section <ref>), performance comparisons (Section <ref>), real-world applications as case studies (Section <ref>), and broader applicability (Section <ref>). Notably, our method demonstrates exceptional scalability and can successfully handle operations on 1024×1024 images – an achievement not previously reported in the literature <cit.>.  




 §.§ Objectives



We aim to address the following questions through our experimental evaluation:
    
  * How does our pixel-level homomorphic encryption method with caching optimization perform compared to existing methods in terms of encryption time and scalability? (Section <ref>)
    
  * When performing secure image processing operations for encryption and decryption, to which extent can our approach preserve image quality while maintaining computational efficiency? (Section <ref>)
    
  * Does our approach effectively enable ciphertext-based image processing in real-world image processing and analysis applications? (Section <ref>)
    
  * Can our approach be broadly applicable to a diverse range of images? (Section <ref>)
    




 §.§ Experimental Setup



Our implementation is based on the Lattigo library <cit.>, an open-source Go library for lattice-based cryptography. We chose Lattigo for its efficient implementation of the CKKS scheme and its support for homomorphic operations.  consists of roughly 4K lines of code (LOC) of Go. Our solution is integrated with the Go image processing library for handling various image operations. The project is developed using Go 1.20.4 and compiled with the standard Go compiler. For parallelization, we utilize the built-in concurrency features of Go, including goroutines and channels.Our experiments are conducted on a high-performance computing cluster of CloudLab Clemson. Each node is equipped with Two 32-core AMD 7542 at 2.9GHz, 512 GB of RAM, and 2 TB of SSD storage. The operating system is Ubuntu 20.04 LTS.We utilize the USC-SIPI Image Database <cit.> for our experiments. This dataset was chosen for its diverse range of image types and content, which allows us to test our encryption method across various scenarios. Additionally, the USC-SIPI database is free from copyright restrictions, making it ideal for research purposes. The dataset includes a wide variety of images, such as textures, aerial photographs, and standard test images, providing a comprehensive basis for our experiments.

As we mentioned in Section <ref>, increasing N and Q can indeed enhance the security of the system, but it also introduces trade-offs in computational complexity and performance. Therefore, in our experiments, we chose N = 2^12 and Q = 2^109, making sure a security of 128 bits for a secret key with uniform ternary distribution equation s ∈{-1, 0, 1}^N. These parameters also ensure that our experiments can proceed efficiently within the constraints of our limited resources.

Prior to our experiments, we perform several preprocessing steps to standardize the dataset. First, we conduct image cropping and resizing. As the original dataset contains images of varying resolutions, we create subsets of images at specific resolutions: 8x8, 64x64, 128x128, 256x256, 512x512, and 1024x1024 pixels. This standardization allows us to evaluate our encryption method's performance across different image sizes. Second, we convert all images to BMP (Bitmap Image File) format to ensure a consistent file format, which guarantees compatibility and facilitates accurate performance comparisons <cit.>. BMP is selected for its pixel-based structure, which is ideal for applications such as medical imaging due to its uncompressed format and high image quality. 





 



 §.§ Performance Comparison


This subsection presents the results of performance comparison between our proposed approaches and the baseline method (without any caching optimization) for pixel-level encryption across a diverse range of images. 





  §.§.§ Time and Scalability





In our evaluation of the encryption methods, we observed significant differences in encryption efficiency. Figure <ref> compares the encryption times of these methods across various image sizes, presented on a linear scale. The methods analyzed include the baseline pixel-level encryption without caching, pixel-level encryption with scanning-based caching, pixel-level encryption with full caching, and pixel-level encryption using radix-based caching, both with and without randomness.













As evident in the graph, the baseline method (Enc by Pixel without Caching) shows a steep increase in encryption time as the image size grows. This method, while straightforward, lacks optimizations to mitigate the computational complexity inherent in pixel-level encryption, particularly for larger images. The encryption time for this method rises exponentially, making it less practical for high-resolution image processing.

In contrast, the full caching method (Enc by Pixel with Full Caching) demonstrates a substantial improvement in efficiency across all image sizes. 

The most substantial improvement is observed with the largest image sizes, where the full caching method achieves up to 19 times the performance of the baseline. This method also outperforms the radix-based caching method, regardless of whether randomness is applied to radix-based caching. 

The scanning-based caching, which only differs from full caching by the scanning part which occurs before image encryption, produces nearly identical results to full caching. Consequently, in the graph, the full caching and scanning-based caching methods are represented by the same plot, though the scanning-based caching may encrypt and cache less pixel values than full caching during the caching phase.





The radix-based caching method (Enc by Pixel with Radix-based Caching), with or without randomness, exhibits enhanced performance over the baseline, though it does not match the level of efficiency achieved by the full caching method.

The substantial reduction in encryption time observed in our experiments can be attributed to our innovative caching strategy. The full caching method resembles the creation of a lookup table, where the encrypted mapping of each pixel value p is pre-stored as a cached ciphertext. This allows retrieval of the encrypted value in O(1) time, remarkably reducing the computational overhead of encrypting each pixel individually. 
It is important to note that this performance gain significantly outweighs the overhead associated with adding randomness to defeat CPA attacks. Consequently, we transform the traditionally time-consuming encryption process into a swift lookup operation, enabling the efficient processing of large images without compromising security.



  §.§.§ Image Quality




Upon completing the tests and analyzing the images, we observed that the decrypted images exhibit a high degree of similarity to the original images, as demonstrated in Figure <ref>. To rigorously assess the effectiveness of our encryption methods in preserving image integrity and quality, we conducted extensive tests utilizing a range of image quality metrics. 






We evaluated the Mean Squared Error (MSE), which measures the average squared difference between pixel values of the original and decrypted images. It is defined as the average of the squared differences between corresponding pixels of the two images <cit.>. The formula for MSE is MSE = 1/mn∑_i=1^m∑_j=1^n( I(i,j) - K(i,j) )^2,



where I(i,j) and K(i,j) represent the pixel values at position (i,j) in the original and the decrypted images, respectively, and m and n are the number of rows and columns in the image.  A lower MSE indicates higher similarity between the original and decrypted images. 

We also assessed the Peak Signal-to-Noise Ratio (PSNR), which quantifies the reconstruction quality of the decrypted image. It is usually expressed in decibels (dB) <cit.>. The formula for PSNR is PSNR = 10 ·log_10( MAX_I^2/MSE),



where MAX_I is the maximum possible pixel value of the image (e.g., MAX_I = 255 for an 8-bit image). A higher PSNR indicates better quality and higher similarity of a decrypted image to the original image.


As shown in Table <ref>, the low MSE and high PSNR values confirm that our encryption and decryption processes preserve the image quality effectively. This demonstrates that our caching-optimized encryption method maintains the integrity and visual fidelity of processed images while significantly enhancing encryption efficiency. Specifically, we obtained a Mean Squared Error (MSE) of 0.48 and a Peak Signal-to-Noise Ratio (PSNR) of 51.31 dB, indicating a high level of fidelity between the original and decrypted images.

As shown in Table <ref>, the low MSE and high PSNR values demonstrate that our encryption and decryption processes effectively preserve image quality. These results confirm that our caching-optimized encryption method not only maintains the integrity and visual fidelity of the processed images, but also significantly enhances encryption efficiency. In particular, we achieved an average MSE of 0.476 and an average PSNR of 51.30 dB. In the field of image processing, MSE values below 10 and PSNR values above 40 dB are typically considered to indicate high similarity between two images <cit.>. Our results, therefore, indicate a high degree of similarity between the original and decrypted images after employing our FHE encryption method, ensuring minimal perceptual loss.

















 §.§ Real-world Applications


To demonstrate that  enables ciphertext-based
image processing in real-world applications, we will implement it across four distinct use cases: mean filtering, brightness enhancement, image matching, and watermarking.



  §.§.§ Mean Filtering

Mean filtering is a fundamental image processing technique used for noise reduction and image smoothing. It replaces each pixel value with the average value of its neighboring pixels within a specified window. In this case study, we demonstrate the implementation of mean filtering on image ciphertext generated by our FHE method.Given a pixel value at position (i, j) within an image I, the mean filter operation in the plaintext domain is mathematically expressed as I'_(i,j) = 1/n^2∑_k=-n/2^n/2∑_l=-n/2^n/2 I_(i+k,j+l),





where n is the size of the filter window (e.g., n = 3 for a 3x3 filter), and I'_(i,j) is the filtered pixel value <cit.>.











The process of mean filtering in the encrypted domain involves three key steps:
    
  * Homomorphic addition of pixel values within the filter window:
    S_(i,j) = ∑_k=-n/2^n/2∑_l=-n/2^n/2 Enc(I_(i+k,j+l)),

where S_(i,j) is the sum of encrypted neighboring pixel values.

    
  * Homomorphic multiplication by a constant: 
    
    Enc(I'_(i,j)) = 1/n^2· S_(i,j),

where n^2 is the total number of pixels in the filter window. For a 3x3 filter, n^2 = 9.
    
  * Rounding and decryption of the result:
    
    I'_(i,j) = Dec( ⌊ Enc(I'_(i,j)) ⌋),

    where Dec(·) is the decryption operation, and ⌊·⌋ denotes the rounding operation, ensuring the final pixel value is an integer.








As shown in Figure <ref>, we applied  to a 64×64 pixel image, followed by a 3x3 mean filtering operation.  Frequency domain analysis confirmed that the decrypted image accurately reflected the application of the mean filter, verifying the correctness of our ciphertext-based homomorphic operations for image mean filtering. Specifically, the MSE between the original image and the filtered image is 218.13, with a PSNR of 24.74 dB. Given that a PSNR value between 20 dB and 30 dB indicates noticeable differences, these results highlight a significant loss of detail, as anticipated from the mean filtering.








Our experimental results show remarkable performance improvements. Traditional pixel-wise encryption requwired 84.29 seconds, while our full cache method took only 4.65 seconds, achieving an 18-fold speedup. 





Without using , the  pixel-wise encryption time for this example was 84.29 seconds, whereas our full caching method reduced it to just 4.65 seconds, delivering an impressive 18-fold speedup. 



Our analysis confirms that the image processed based on ciphertext  indistinguishable from the ones processed directly on plaintext for mean filtering.







  §.§.§ Brightness Enhancement

Brightness enhancement is a common image processing technique used to improve image visibility.
We applied homomorphic operations to real images encrypted by , performing brightness enhancement while the images remained encrypted. Specifically, we incremented each pixel value by 50, resulting in brighter images <cit.>. The image was then decrypted to visualize the processed effect. It is important to note that this brightness enhancement technique is effective only when encryption is applied at the pixel level.







Figure <ref> illustrates the result of brightness enhancement applied to an encrypted image, showing a marked improvement in clarity. Our analysis confirms that the image processed based on ciphertext is indistinguishable from the image processed directly on plaintext.

In this example,  accelerated the image encryption by 4 times. For the 256×256 image, we reduced the encryption time from 16.96 seconds to 4.57 seconds. 





  §.§.§ Image Matching

Image matching is a fundamental task in computer vision, where the goal is to determine whether two images are similar. We're matching images using the L1 distance (also known as Manhattan distance) in a pixel-by-pixel manner and comparing the images directly based on their pixel values.
The L1 distance d_L1 between two images I_1 and I_2 is d_L1(I_1, I_2) = ∑_i=1^M ∑_j=1^N | I_1(i, j) - I_2(i, j) |,



where I_1(i, j) and I_2(i, j) represent the pixel intensities at position (i, j) in images I_1 and I_2, respectively <cit.>.

Using three 128×128 images for illustration, [id=SY]as shown in Figure <ref> , our specific operation involved applying  to encrypte them, followed by homomorphic subtraction and multiplication on the ciphertexts to compute the L1 distance in encrypted form. The user can then decrypt the distance using their key to determine which image in the database is most similar to the one they uploaded. This technique can be applied in facial recognition or medical image identification. 



As shown in Figure <ref>, Image 2 is obtained by brightening Image 1 and Image 3 is a totally different one. As shown in Table <ref>, the distances between the images are as follows: 11075.62 between Image 1 and Image 2; 21036.48 between Image 1 and Image 3; and 15133.89 between Image 2 and Image 3. The distance results are consistent with what we observe visually in Figure <ref>.


Without using , the encryption time for this example was 826.19 seconds. By using , it was reduced to 69.99 seconds. The performance has been improved by about 91.53%, which is a significant enhancement.



































  §.§.§ Watermarking

Watermarking images is crucial for ensuring the authenticity and ownership of digital content. In an era where digital media can be easily copied and distributed, embedding a watermark provides a layer of protection against unauthorized use and counterfeiting <cit.>. We performed a watermarking operation on the encrypted images by adding a value of x to a specific pixel. The value of x is set by the user; for the convenience of the experiment, we chose a value of 5.0. This slight alteration creates a watermark within the encrypted image, ensuring that the watermark is embedded securely without revealing any underlying data. 
This approach is valuable for scenarios where image authenticity and traceability are critical. 


Adding a watermark at a specific pixel location can make the watermark invisible, as shown in Image (a) and (b) from Figure <ref>. Image (c) from reflect the differences between (a) and (b): it is a binary image where the white areas represent the pixel locations with differences above the threshold. In this case, the thredshold is the value of 5.0 we chose before. This technique ensures that the watermark does not alter the visual appearance of the image, maintaining its aesthetic integrity.
















































































In this example, without using , the encryption time was 63.08 seconds. By using , it was reduced to 4.8 seconds, achieving an 16-fold improvement in speed. 





 §.§ Broader Applicability






To ensure that our approach is broadly applicable and robust across various image types and content, we conducted experiments using a diverse range of images, although not all could be displayed in this paper. To make sure the image selection captured a broad spectrum of variation, we calculated Structural Similarity Index (SSIM) values between images, quantifying their degrees of similarity and dissimilarity.

SSIM is a metric used to assess the similarity between two images, focusing on the preservation of structural information. Unlike MSE and PSNR, SSIM considers luminance, contrast, and structure in its assessment <cit.>. The formula for SSIM is SSIM(I, K) = (2μ_I μ_K + C_1)(2σ_IK + C_2)/(μ_I^2 + μ_K^2 + C_1)(σ_I^2 + σ_K^2 + C_2),



where μ_I and μ_K are the mean values of images I and K, σ_I^2 and σ_K^2 are the variances, σ_IK is the covariance between I and K, and C_1 and C_2 are constants included to stabilize the division when the denominator is close to zero.

This guided our selection of 200 distinct images, each with dimensions of 256×256 pixels, from the USC-SIPI <cit.> database. Five representative examples from this image set are displayed in Figure <ref>. The top row showcases the five original images with distinct characteristics: three in grayscale and two in color. We applied the  operation to all the images. The bottom portion of Figure <ref> illustrates the images after undergoing encryption and subsequent decryption, with each restored to its original form. The identical appearance of the images before and after the process highlights the effectiveness and broader applicability of our approach.



Figure <ref> presents the experimental results from processing images using both non-caching and full-caching approaches. The figure demonstrates a significant reduction in encryption time, with decrypted images closely matching the originals. Specifically, the average processing time decreased by a factor of 17.57, while the average MSE difference is 0.146. These results underscore the robustness and the broad applicability of our approach in practical scenarios <cit.>.

The SSIM values calculated between these images range from 0.0737 to 0.5640, reflecting a spectrum of similarity and diversity within the dataset. This variation in SSIM values corresponds to the differing structural characteristics among the images, illustrating the range of similarity and dissimilarity present. The variability in SSIM values highlights that the image set used in this study represents a wide range of image types, thereby reinforcing the broad applicability of our findings. This distribution of SSIM values suggests that the approach employed is robust across images with diverse structural content, thereby extending the applicability of our results to a broad array of real-world scenarios.















§ RELATED WORK


This section reviews relevant work of FHE, starting with a general overview (Section <ref>), HE performance acceleration (Section <ref>), followed by recent developments in the CKKS scheme (Section <ref>), and ending with the CKKS application to image encryption (Section <ref>).





 §.§ FHE



Fully Homomorphic Encryption (FHE) represents a groundbreaking advancement in the field of cryptography, enabling computations on encrypted data without needing to decrypt it first. It was initially proposed by Rivest <cit.> in 1978. Later, Gentry et al. <cit.> introduced pioneering work on FHE in 2009, which provided the first feasible construction of an FHE scheme, and since then there has been significant progress in making FHE more practical for real-world applications <cit.> .

FHE schemes have evolved from theoretical constructs to more efficient implementations, addressing the challenges of high computational overhead and limited functionality. Various FHE schemes have been proposed, including BFV <cit.>, BGV <cit.>,  CKKS <cit.>, TFHE <cit.> and its optimizations, each tailored to specific types of computations and use cases. 

BFV and BGV both operate over integers, making them ideal for exact computations, with BFV generally offering faster performance for certain operations while BGV allows for deeper computational circuits before requiring bootstrapping. These distinctions have led to various optimization efforts. For instance, Halevi et al. <cit.> focused on enhancing the BFV scheme by optimizing decryption and homomorphic multiplication in the Residue Number System (RNS). Robin et al. <cit.> introduced BASALISC, the first to implement the BGV scheme with fully-packed bootstrapping, i.e., the noise removal capability necessary for arbitrary-depth computation. In contrast, CKKS is designed for approximate arithmetic on real and complex numbers, introducing controlled noise to enhance efficiency. This makes CKKS particularly well-suited for machine learning and signal processing tasks where minor approximation errors are acceptable <cit.>. While BFV and BGV provide precise results for integer arithmetic, CKKS trades some precision for improved performance and versatility in floating-point operations <cit.>. Additionally, TFHE, which was proposed by Chillotti et al. <cit.>, introduces significant optimizations in bootstrapping and leveled homomorphic encryption on Boolean circuits, reducing computational overhead and improving the practicality of FHE for arithmetic functions. There have been numerous efforts to optimize TFHE, including works such as <cit.>, <cit.>, and <cit.>. Unlike CKKS, schemes like BFV, BGV, and TFHE operate over integers rather than floating-point numbers, which are commonly used in image processing. The choice between these schemes depends on the specific requirements of the application, balancing factors such as data type, precision needs, computational depth, and overall performance considerations <cit.>.

While the first group of schemes – BFV, BGV, CKKS and TFHE – fall under the category of FHE, allowing for arbitrary-depth computation, another line of research is Partial Homomorphic Encryption (PHE) methods. This paper does not focus on PHE and will therefore not discuss it in detail.



 §.§ HE Performance Acceleration



While FHE methods have made significant strides in security, they often encounter challenges like high computational costs and slow processing speeds in real-world applications. Recently, there have been many works focusing on the acceleration on homomophic encryption (HE). Agrawal et al. <cit.> propose memory-aware design (MAD) techniques to accelerate the bootstrapping operation of CKKS. Genise et al. <cit.> improve the runtime of the main bottleneck operation using “gadget” by 18x for 2 attributes and up to 289x for 16 attributes. Additionally, efforts in hardware acceleration have been investigated to speed up homomorphic operations. For instance, Di Matteo et al. <cit.> propose hardware accelerator, presenting a configurable Number Theoretic Transform (NTT) unit for all the polynomial degrees available on the SEAL-Embedded. In addition to acceleration on FHE, PHE performance acceleration is also significantly improved. One of the state-of-the-art techniques is Rache <cit.>, which introduces a radix-based parallel caching optimization for accelerating the performance of homomorphic encryption (HE) of outsourced databases in cloud computing. However, it is only available for accelerating PHE schemes like Paillier <cit.> and Symmetria <cit.>, and was not designed for handling image data. 













 §.§ CKKS



The CKKS scheme, introduced by Cheon, Kim, Kim, and Song in 2017<cit.>, is a leveled homomorphic encryption scheme designed for approximate arithmetic. Unlike earlier schemes that focused on exact computations, CKKS allows for efficient encrypted computations with some tolerable error, which is often acceptable in real-world applications. This trade-off between accuracy and efficiency has made CKKS a popular choice for applications in privacy-preserving machine learning, encrypted databases, and secure cloud computing .

Recent work has focused on optimizing CKKS to reduce its computational overhead and enhance its practicality. Techniques such as bootstrapping, ciphertext packing, and key switching have been explored to improve the performance of CKKS-based systems. For example, Lee et al. <cit.> propose to compose the optimal approximate polynomial of the inverse sine function to the sine/cosine function to improve the precision of the bootstrapping. Cheon et al. <cit.> proposed Mult2 to perform ciphertext multiplication in the CKKS scheme with lower modulus consumption. Lee et al. <cit.> proposed a scheme to actively control the scale of a ciphertext, making the impact of noise on an error smaller. Bossuat et al. <cit.> optimize the key-switch procedure and propose a new technique for linear transformations. Chen et al. <cit.> generalize the bootstrapping techniques for HE to obtain multi-key fully homomorphic encryption schemes.  Jain et al. <cit.> proposed that the efficiency of ciphertext packing schemes, model optimization, and multi-threading strategies significantly impacts the throughput and latency during the inference process.



 §.§ CKKS for Images



Given the unique features of CKKS, its application in image encryption has been the subject of extensive research. Boemer et al. <cit.> introduced nGraph-HE2, which optimizes ciphertext-plaintext addition and multiplication using the CKKS scheme. Similarly, Mertens et al. <cit.> proposed a practical image compression and processing pipeline tailored for CKKS, emphasizing FHE-friendliness.

Recently, there has been a growing interest in integrating CKKS with machine learning frameworks for images. For example, Jia et al. <cit.> introduced Homomorphic Encryption Image Classification Evaluation (HEICE), a novel approach for secure image classification. Dimitris et al. <cit.> introduced a scheme combining federated learning and CKKS for neuroimaging analysis. Benaissa et al. <cit.> presented TenSEAL, an open-source library for Privacy-Preserving Machine Learning based on CKKS.

Despite these advancements, challenges persist in making FHE schemes, including CKKS, more accessible and scalable. Issues such as key management, noise growth during computations, and the requirement for high-performance hardware remain active areas of research <cit.>. Moreover, the trade-offs between security and efficiency—especially regarding bootstrapping and noise management—are critical considerations <cit.>. Nonetheless, the increasing focus on optimizing and applying CKKS in various domains, such as privacy-preserving machine learning <cit.> and secure data analytics, underscores its potential to become a cornerstone of secure computation in the era of big data and artificial intelligence.






§ CONCLUSION




In conclusion, this paper advances practical ciphertext-based image processing by proposing and implementing a pixel-level homomorphic encryption approach based on the CKKS scheme. Our approach employs three caching strategies – radix-based caching, scanning-based caching, and full caching – to pre-encrypt radix values and frequently occurring or all pixel values, thereby significantly reducing redundant encryption operations. Our evaluation across a diverse set of images demonstrates substantial improvements in encryption efficiency, with up to a 19-fold reduction in encryption time for large images, all while maintaining image quality. We further showcased the versatility and practicality of our approach by applying it to real-world image processing tasks, including mean filtering, brightness enhancement, image matching, and watermarking, all performed directly on ciphertexts. The results indicate notable performance gains, with encryption tasks becoming up to 91.53% faster and achieving a 16-fold reduction in encryption time. Additionally, we validated that our approach is IND-CPA secure, benefiting from the integrated randomness.




acm







