Privacy-Preserving High-Resolution Image Gradient Computation Based on Fully Homomorphic Encryption

arXiv:2606.03513 · cs.CR · Submitted 2026-08-22 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia, and with me are Elias and Priya, guest researcher.

Elias: Today's paper: "Privacy-Preserving High-Resolution Image Gradient Computation Based on Fully Homomorphic Encryption".

Nadia: I. Problem Statement and Motivation The paper addresses the challenge of privacy-preserving image processing for high-resolution images (e.g., 2K resolution). While homomorphic encryption (HE),

Elias: First, who's behind it and why it matters.

Title and authors: Nadia: Now that we understand the mechanics of the "Privacy-Preserving High-Resolution Image Gradient Computation Based on Fully Homomorphic Encryption" paper, let’s look at the title and who wrote it, to see what those details tell us about its scope.

Elias: The title itself is quite descriptive; it sets a very specific expectation that this work is focused on achieving high resolution gradient computation using fully homomorphic encryption. It clearly signals that they aren't just doing low-resolution stuff anymore, which is a key distinction from previous work in the field.

Priya: The authors are clearly targeting researchers who need to process large visual data while maintaining a strong privacy guarantee. Their choice of CKKS for the underlying scheme suggests they are prioritizing computations involving real numbers, which is perfect for gradient calculations and image processing where precision matters.

Nadia: That’s true; the authors are signaling that they are tackling the inherent scalability problem head-on by focusing on 2K resolution images specifically, which was a gap in existing research. They're not just iterating on old techniques; they are proposing a new architecture to handle that scale efficiently.

Elias: The focus on "fully homomorphic encryption" is important because it means the operations they are performing—addition and multiplication—are supported without needing external servers for intermediate steps, relying only on the server's ability to handle the computation over encrypted data.

Priya: And when we think about implications, this points toward a future where high-resolution analysis becomes a standard tool in privacy-preserving applications rather than just an experimental curiosity. It moves us closer to practical deployment in sensitive domains.

Nadia: I agree; it shifts the focus from theoretical feasibility to practical implementation challenges, and that's where the real engineering work lies for this specific paper.

Elias: And considering the constraints they put on their model, we have to remember that security relies entirely on CKKS ciphertext security because no secret key is ever shared with the server.

Priya: So, if we look at the data they are using, what do you think the real-world implications are for researchers in areas like medical imaging or remote sensing?

Nadia: It implies that we can start running sophisticated analyses on sensitive medical scans or satellite imagery privately without needing to send that raw, identifiable data to a central cloud server.

Elias: That’s the core value proposition of using this specific paper; it allows for complex mathematical operations, like calculating Sobel operators, directly on encrypted data.

Priya: It means we can get high-fidelity feature extraction from things like retinal vessel boundaries or subtle defects without compromising patient or proprietary information.

Nadia: So, the authors are essentially proposing a way to make privacy a scalable constraint that doesn't destroy the capability to perform detailed image analysis on large inputs.

Elias: That’s the tightrope they’re walking between computational feasibility and maintaining cryptographic rigor in this specific context.

Priya: It seems like a solid foundation for moving high-resolution private CV from the lab to something more deployable.

Nadia: That's the direction we need to look at as we move into the next phase of this paper, and that sets us up perfectly for discussing how they handle those specific mathematical challenges.

The paper's summary: Elias: Moving on to the summary section of "Privacy-Preserving High-Resolution Image Gradient Computation Based on Fully Homomorphic Encryption," we can see exactly what the authors are proposing. They are detailing the technical solution they developed for scaling up image size.

Priya: Essentially, they're explaining how to handle large images without needing to adjust HE parameters drastically, which is a crucial first step in making this technique practical.

Nadia: They explain that the main problem was that standard HE methods required increasing the polynomial ring dimension when dealing with 2K images, which led to huge computational overhead and increased key generation costs for users.

Elias: Their solution is the multi-ciphertext privacy-preserving framework, where they divide the large image into multiple sub-images to keep the HE parameters small and reduce key size compared to encrypting the whole thing as one ciphertext.

Priya: So, this means instead of one massive encryption task that would choke resources, we can handle several smaller tasks in parallel with less strain on any single user's hardware.

Nadia: The authors also introduced a key technique called "repeated packing method" to handle the boundary issues between these sub-images during convolution operations efficiently.

Elias: That packing method is designed to prevent interference and avoids the need for expensive cross-ciphertext rotations, allowing for fast parallel processing of the sub-image ciphertexts.

Priya: I’m wondering how this specific packing strategy affects the actual quality of the resulting gradient maps; does it introduce any artifacts that we should be worried about?

Nadia: The goal here is to ensure that the packing strategy doesn't introduce significant errors, and they used horizontal or vertical slicing techniques to pack rows such that necessary boundary pixels for convolution are repeated within the same ciphertext.

Elias: That repetition is key because it eliminates the need for complex cross-ciphertext rotations, which simplifies things considerably in terms of cryptographic complexity.

Priya: That sounds like a smart trade-off: accepting some structural packing complexity to gain massive parallel processing speed without sacrificing the integrity of the gradient information.

Nadia: Precisely; they are balancing those competing demands of speed and data integrity within the HE constraints, which is a very fine line to walk.

Elias: And they also introduced polynomial approximations for non-polynomial functions like square root and arctan, which is essential because arithmetic HE only supports addition and multiplication.

Priya: So, the entire summary boils down to a method that smartly decomposes the problem into smaller pieces to make it manageable for both computation speed and privacy requirements.

Nadia: It’s a very sophisticated approach to managing complexity through decomposition, and I think that decomposition strategy is central to the success of this paper.

Elias: And it really shows how structural organization can be used as a tool for optimization in a way that goes beyond just parameter tuning.

Priya: So, if I understand correctly, this framework is about making high-resolution gradient computation practical through decomposition into multiple sub-images and smart packing strategies?

Nadia: That’s the gist of it; it's about turning an intractable problem into a manageable one by breaking down the image size.

Elias: And that decomposition allows them to manage multiplicative depth effectively with bootstrapping when necessary.

Priya: It sounds like they’ve engineered a way to make high-resolution gradient computation practical through decomposition into multiple sub-images and smart packing strategies?

Nadia: That’s the gist of it; it's about turning an intractable problem into a manageable one by breaking down the image size.

Elias: And that decomposition allows them to manage multiplicative depth effectively with bootstrapping when necessary.

Priya: It sounds like they’ve engineered a way to make high-resolution gradient computation practical through decomposition into multiple sub-images and smart packing strategies?

Nadia: That’s the gist of it; it's about turning an intractable problem into a manageable one by breaking down the image size.

The paper's improvements: Elias: Now that we understand the summary of "Privacy-Preserving High-Resolution Image Gradient Computation Based on Fully Homomorphic Encryption," let’s discuss the specific technical tweaks they made to their methodology to make this work in practice.

Priya: I'm interested in what concrete changes they implemented beyond just the high-level framework; what are the specific engineering decisions that differentiate this from other HE solutions?

Nadia: The key improvements lie in how they implemented those non-polynomial functions, specifically replacing them with Chebyshev series approximations for square root, reciprocal, and arctan to ensure smooth computation.

Elias: That’s the technical meat of the improvement; without those specific polynomial approximations, the Sobel operator simply couldn't run under arithmetic HE.

Priya: Those approximations are crucial because they allow them to compute complex functions that are mathematically necessary for edge detection, even though standard HE doesn't support those operations directly.

Nadia: And then there’s the "preBTS" strategy, which is a clever way to manage the multiplicative depth before execution, reducing user overhead by performing bootstrapping only when needed.

Elias: It’s an optimization of the computational workflow; they are essentially front-loading the work to ensure that when they finally do need a heavy operation, the ciphertext is ready for it.

Priya: So, these specific tweaks show a clear path toward making this system usable because they’ve engineered a way to manage the complexity in a way that feels less like an overwhelming monolithic burden.

Nadia: I think the combination of structural decomposition, polynomial approximations and optimized depth management is what makes this work; it's not just one fix, but several interconnected optimizations working together.

Elias: And considering those specific engineering decisions, can you pinpoint exactly where the system might still break down or introduce vulnerabilities?

Priya: One thing that seems to be their limitation is that while they handle non-polynomial functions well, the overall security still relies heavily on the robustness of their chosen CKKS scheme and whether any subtle side-channel attacks against the computation itself could compromise the secret key.

Nadia: That’s a good point about side channels; if an attacker can probe how many bootstrapping operations are happening or how long they take, they might infer things about the data being processed.

Elias: And parameter selection is always a vulnerability; if the chosen parameters aren't robust enough against specific algebraic attacks, the entire scheme could fall apart.

Priya: So, while they solve many problems, it seems they haven't fully eliminated all potential security risks inherent in moving complex math into an encrypted space.

Nadia: That’s a balanced view; they’ve made massive strides in making this feasible, but the challenge now is ensuring that every layer of their system remains impenetrable under real-world attack scenarios.

Elias: So, we've covered the technical improvements and potential weaknesses, and next up is segment five to wrap up our discussion on "Privacy-Preserving High-Resolution Image Gradient Computation Based on Fully Homomorphic Encryption."

Conclusion: Nadia: Alright team, for the final segment of this discussion on "Privacy-Preserving High-Resolution Image Gradient Computation Based on Fully Homomorphic Encryption," let’s summarize the overall impact and say goodbye to this paper.

Elias: We've seen how they manage scaling through multi-ciphertext decomposition and how they use polynomial approximations for functions like square root and arctan to enable gradient computation.

Priya: From a research standpoint, I think the main implication is that we now have a robust method for handling high-resolution data privately.

Nadia: That’s right; this fundamentally alters the landscape for computer vision applications in general because it addresses a major privacy hurdle we've been facing.

Elias: The ability to perform complex, non-polynomial functions like the reciprocal and arctan securely using sign functions combined with Chebyshev polynomials is a powerful technique that makes complex data truly actionable within a secure environment.

Priya: I think the biggest practical impact is enabling sophisticated analysis on sensitive imagery without compromising privacy in areas like medical imaging or remote sensing.

Nadia: That’s right; this paper, "Privacy-Preserving High-Resolution Image Gradient Computation Based on Fully Homomorphic Encryption," has set a new benchmark for what’s possible.

Elias: We can see that the combination of structural decomposition, polynomial approximations and optimized depth management is what makes this work.

Priya: I think we're ready to conclude our thoughts here, but it’s been a very insightful discussion on how they manage the technical challenges they faced.

Nadia: I agree; it’s been an incredibly deep dive into this topic, and I think we'm ready for a break from this topic.

Elias: Agreed; we've covered the technical details of this paper, from scaling to the mathematical approximations that make complex math work in HE.

Priya: It was a very insightful discussion on how they manage the technical challenges they faced.

Yufei Zhou

School of Computer Science and Engineering, Sun Yat-sen University · Sun Yat-sen University

cs.CR

Submitted: 2026-08-22

Updated: 2026-08-25

Comments: Due to the need for extensive modifications, I have decided to withdraw the current version

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 79/100

The gist: " I.

Key concepts

Fully Homomorphic Encryption (FHE)
FHE allows computations, such as addition and multiplication, to be performed directly on encrypted data without needing the secret key. This means calculations can happen while the data remains private, relying only on the server's ability to process the encrypted information.
Multi-ciphertext Privacy-Preserving Framework
To handle large images, authors divide them into multiple sub-images. This approach keeps HE parameters small and reduces key size compared to encrypting one large image, allowing for parallel processing with less strain on hardware.
Polynomial Approximations
Since arithmetic HE only supports addition and multiplication, the authors used Chebyshev series approximations to replace non-polynomial functions like square root and arctan. This allows complex mathematical operations needed for gradient computation to run securely under the scheme.
PreBTS Strategy
This is an optimization of the computational workflow that manages multiplicative depth before execution. It reduces user overhead by performing bootstrapping only when necessary, ensuring the ciphertext is ready for heavy operations.

Terminology

Summary

"

I. Problem Statement and Motivation

The paper addresses the challenge of privacy-preserving image processing for high-resolution images (e.g., 2K resolution). While homomorphic encryption (HE), particularly based on the CKKS scheme, is a mainstream method for privacy preservation due to its non-interactive nature, existing research predominantly focuses on low-resolution images. When attempting to process large images using established methods, the necessary adjustments to HE parameters—such as increasing the polynomial ring dimension—lead to significant computational overhead and increased key generation costs for resource-constrained users.

II. Proposed Methodology: Multi-Ciphertext Framework

The authors propose a multi-ciphertext privacy-preserving framework designed for large images, which achieves efficiency by decoupling the image into multiple sub-images. This approach allows the maintenance of smaller HE parameters and reduces key size compared to encrypt an entire image as a single ciphertext.

A. Parallel Convolution via Repeated Packing

To address the computational difficulty of handling boundaries between adjacent ciphertexts in multi-ciphertext encryption, which is a common issue in convolution operations, the paper introduces a repeated packing method. This method is designed to:

  1. Prevent interference between convolutions of different ciphertexts.

  2. Avoid expensive cross-ciphertext rotations.

  3. Enable fast parallel processing of sub-image ciphertexts (Fig. 6).

The authors detail how this works when an image h times w is divided into n small images, utilizing strategies like horizontal slicing or vertical slicing (Fig. 5). In the horizontal slicing method, for the i-th ciphertext, the image rows are packed from N over w - kh to N over w + kh, where N is the number of slots. This packing strategy ensures that boundary pixels required for convolution are repeated within the same ciphertext, eliminating the need for complex cross-ciphertext rotations.

B. Polynomial Approximation for Sobel Operator Computation

The core challenge in implementing the Sobel operator under HE is that its calculation of gradient magnitude and angle involves non-polynomial operations (square root, reciprocal, and arctan). The paper presents a novel approach to enable fully HE-based computation:

  1. Square Root Function: The square root function is approximated using Chebyshev polynomial series (Eq. 12), which is numerically stable.

  2. Reciprocal Function & Gradient Angle: To compute the gradient angle theta = (g y over g x), the authors address the discontinuity of the reciprocal function near zero and its tendency to infinity:

  • They first compute g x using = sign(g x) times g x (Eq. 17).

  • They separate the zero point using a mask m r, where m r = sign(g x) squared (Eq. 18).

  • They approximate g x using Chebyshev polynomials (y 1), temporarily ignoring the zero point.

The reciprocal function is then approximated as y rec = y 1 times sign(g x) + (1 - m r) times B (Eq. 20), where B is a constant, effectively handling the zero point.

  1. Arctan Function: The arctan function is approximated using Chebyshev polynomial series (y 3), with the final result combining the approximation at the zero point: theta = m r y 3 + (1 - m r) times pi over 2 (Eq. 22).

C. Optimization of Multiplicative Depth (BTS)

To mitigate the heavy computational burden imposed by high-degree polynomials, the paper introduces a preBTS strategy:

  • The user encrypt the image with a low multiplicative depth to reduce ciphertext size and encryption overhead.

The server then performs necessary Bootstrapping (BTS) operations before executing the concrete computation. This reduces both the user's computational and communication overhead.

III. Security and System Model

The system model involves a resource-constrained user who encrypt/decrypt data, and a powerful server that processes it. The threat model assumes the server is semi-honest (honest but curious). The security of the scheme relies on the security of CKKS ciphertexts, as the secret key is never sent to the server.

IV. Evaluation and Results

The method was evaluated using a 648 times 2040 image size across various cryptographic parameters (LHE, postBTS, preBTS).

  • Performance Comparison: The proposed Ours scheme significantly outperforms the baseline Compact scheme.

  • User Overhead: The preBTS strategy yields the lowest overhead in both key generation time and user online processing time.

  • Computational Efficiency: In Table VI, the server computation time for Ours is substantially faster than Compact. Furthermore, Figure 10 demonstrates that due to the parallelization enabled by multi-ciphertext packing, the server's total computation time is consistent across different image sizes.

  • Accuracy: Table VII shows that using the proposed method on real images from the DIV2K train HR dataset achieves high accuracy in magnitude calculation, with errors in angle being almost imperceptible when post-processing is applied.

V. Conclusion

The paper concludes by summarizing its contributions: proposing a multi-ciphertext framework for parallel convolution; designing a novel polynomial approximation path for the reciprocal and arctan functions to enable full HE computation of the Sobel operator; and introducing a preBTS placement strategy that significantly reduces user overhead.

Improvements for AI systems

Based on the synthesis of cryptographic literature (Homomorphic Encryption and Garbled Circuits) and advanced computer vision techniques (Sobel operators, CNN inference), I propose developing a Privacy-Preserving Edge Detection and Feature Extraction Engine. This system fundamentally shifts high-stakes CV analysis from insecure cloud environments to a fully encrypted, private computation model.

Improvement: Integrating the principles of deep convolutional neural networks (CNNs) and classic image feature extraction (like Sobel operators) into a single, end-to-end circuit designed to operate entirely on ciphertext. This creates a secure inference pipeline where the input image and the model weights remain encrypted throughout processing.

Mechanism:

  1. Ciphertext Input: The raw input image (I) is encrypted using a robust FHE scheme (e.g., BFV/CKKS, leveraging optimized bootstrapping techniques [23], [35]).

  2. Secure Pre-processing Layer: Edge detection is performed in the encrypted domain by implementing directional filters (like multi-directional Sobel operators [14], [26]) as polynomial approximations (e.g., using minimax approximation for sign functions [19]). This module extracts edge feature maps (E cipher).

  3. Encrypted Inference: The resulting feature map E cipher is fed into a low-complexity, multiplexed CNN structure (optimizing the depth and width of the network to minimize multiplicative depth [9]). The entire inference process—including convolution and pooling layers—is executed homomorphically on the ciphertext.

What the Improved AI System Can Do:

  • Private Industrial Defect Detection: Analyze high-resolution images (e.g., steel, circuit boards) for subtle defects or edges without ever decrypting the image data on the cloud server. The system can perform defect classification and localization by running secure feature extraction followed by encrypted CNN inference.

  • Secure Medical Imaging Analysis: Detect and segment critical anatomical features (like retinal vessel boundaries using Sobel segmentation [27]) from encrypted medical scans, ensuring patient privacy while maintaining diagnostic accuracy.

Related papers