Homomorphic Operations, Part 2

Table of Contents:

Week 5 at SuperSecure

Code

Explanation

Remark

In this chapter, we’ll continue where we left off with homomorphic operations, diving deeper into how they enable more flexible encrypted computations.

This time, we’ll focus on two powerful operations: rotation and conjugation. These are essential tools when working with vectorized encrypted data, and understanding how to use them will open the door to more advanced use cases.

Week 5 at SuperSecure, Inc.

Thanks to the successful launch of our linear model inference service, we’re now adding a new layer on top of it—an average layer that computes the mean of the result vector. This additional step helps minimize potential information leakage about the model when returning results to clients.

To maximize throughput, we also recommend that clients split real-valued input data into two parts: the real and imaginary components of a complex message. Since our model uses only real-valued weights and biases, this kind of complex packing preserves the correctness of the computation.

Keep in mind that when applying the average layer, you must compute the sum across both the real and imaginary parts, as both carry meaningful input data.

In this example, separating the key management system is not required.

TASK: The server computes the sum of all slots in the result vector by applying a sequence of rotations and additions to accumulate values into a single slot. At this point, the real and imaginary parts store partial sums of different segments.

To combine them, the server applies multImagUnit followed by addition, effectively computing (real + imag) in the real part.

Finally, conjugation and addition are applied to eliminate any remaining imaginary part, yielding a real-valued result. This helps minimize potential information leakage from the complex representation.

Code

open code

#include "HEaaN/HEaaN.hpp"

#include <complex>
#include <cstdlib>
#include <iomanip>
#include <iostream>

int main() {
    const auto preset{HEaaN::ParameterPreset::SD3};
    const auto context = HEaaN::makeContext(preset);

    const auto sk = HEaaN::SecretKey(context);
    const auto pack = HEaaN::KeyPack(context);
    const auto keygen = HEaaN::KeyGenerator(context, sk, pack);

    std::cout << "Generate Rotation / Conjugation Keys ... \n";
    keygen.genRotKeyBundle();
    keygen.genConjKey();
    std::cout << "done\n";

    const auto log_slots = HEaaN::getLogFullSlots(context);
    HEaaN::Message message(log_slots);
    const auto message_size = message.getSize();

    for (int i = 0; i < message_size; ++i) {
        message[i].real(std::rand() / static_cast<HEaaN::Real>(RAND_MAX));
        message[i].imag(std::rand() / static_cast<HEaaN::Real>(RAND_MAX));
    }

    const auto enc = HEaaN::Encryptor(context);
    auto ctxt = HEaaN::Ciphertext(context);
    enc.encrypt(message, sk, ctxt);

    const auto eval = HEaaN::HomEvaluator(context, pack);

    // TASK : Compute the average of the input.
    auto ctxt_res = ctxt;
    auto ctxt_rot = HEaaN::Ciphertext(context);
    for (HEaaN::u64 i = 0; i < log_slots; ++i) {
        eval.leftRotate(ctxt_res, (HEaaN::u64(1) << i), ctxt_rot);
        eval.add(ctxt_res, ctxt_rot, ctxt_res);
    }
    {
        auto ctxt_i = HEaaN::Ciphertext(context);
        eval.multImagUnit(ctxt_res, ctxt_i);
        eval.add(ctxt_res, ctxt_i, ctxt_res);

        auto ctxt_conj = HEaaN::Ciphertext(context);
        eval.conjugate(ctxt_res, ctxt_conj);
        eval.add(ctxt_res, ctxt_conj, ctxt_res);
    }

    const auto dec = HEaaN::Decryptor(context);
    HEaaN::Message decrypted_average;
    dec.decrypt(ctxt_res, sk, decrypted_average);

    std::cout << "Original Message : \n";
    for (HEaaN::u64 i = 0; i < 10; i++) {
        std::cout << std::fixed << std::setprecision(4) << message[i] << '\n';
    }

    std::cout << "The average of the results is: " <<
        decrypted_average[0] / (2 * static_cast<HEaaN::Real>(message_size)) << '\n';

}

Explanation

Let's explore the code line by line.

Getting started with the key generation parts.

    std::cout << "Generate Rotation / Conjugation Keys ... \n";
    keygen.genRotKeyBundle();
    keygen.genConjKey();
    std::cout << "done\n";

In our scenario, key generator needs to generate rotation and conjugation keys. A set of rotation keys is generated via genRotKeyBundle() which generates all rotation keys corresponding to the power-of-two indices, as described in the Chapter 4.

    // TASK : Compute the average of the input.
    auto ctxt_res = ctxt;
    auto ctxt_rot = HEaaN::Ciphertext(context);
    for (HEaaN::u64 i = 0; i < log_slots; ++i) {
        eval.leftRotate(ctxt_res, (HEaaN::u64(1) << i), ctxt_rot);
        eval.add(ctxt_res, ctxt_rot, ctxt_res);
    }

We begin by preparing the result ciphertext and a temporary ciphertext used during computation. The result ciphertext is initialized as a deep copy of the input ciphertext, ensuring that modifications don't affect the original.

To compute the average of all encrypted slots, the first step is to sum over all components. But how can we perform computations across different slots (also called components)?

The typical approach is to rotate the ciphertext so that values from other slots are moved into the first slot, allowing for accumulation. This requires a special operation called left rotation, which shifts the positions of the slot values to the left within the ciphertext.

Here's how rotation works : $$ (x_0,x_1,\cdots, x_i, \cdots, x_{n-1}) \xrightarrow{\text{left rot by }i} (x_i, x_{i+1},\cdots, x_{n-1}, x_0, \cdots, x_{i-1}) $$

Now, let’s explore how the average is computed using rotations and additions on small-sized messages. Consider the case where $\text{log_slots} = 2$, meaning we have 4 slots. The computation involves two rotation steps — by 1 and by 2 positions.

Imagine how each slot in the result ciphertext (ctxt_res) evolves during this process. The following diagram illustrates how the values shift and accumulate through each rotation and addition:

$$ \begin{aligned} (x_0,x_1,x_2,x_3) &\xrightarrow{\text{left rot by 1}} (x_1, x_2, x_3, x_0) \\ (x_0 + x_1,x_1 + x_2,x_2 + x_3,x_3 + x_0) &\xrightarrow{\text{left rot by 2}} (x_2 + x_3, x_3 + x_0, x_0 + x_1, x_1 + x_2) \\ \end{aligned} $$ These steps show how ctxt_res is updated by adding rotated versions of itself (ctxt_rot) at each stage. At every iteration, we rotate the current ciphertext and add it back to the result.

If you focus on the first slot (index 0), you can see the core idea of the algorithm:

In the first rotation, $x_1$ is brought to the first slot and added to $x_0$.
In the next step, $x_2 + x_3$ is rotated into the first slot and added to the previous sum, $x_0 + x_1$.

This pattern generalizes to any message size $n$. In the final step, a rotation by $n/2$ brings the sum of the back half of the message (i.e., $x_{n/2} +\cdots + x_{n-1}$ ) to the front, and it is combined with the sum of the front half $(x_0 + x_1+\cdots + x_{n/2-1})$.

Now, you can see how the sum is computed using a series of rotations and additions. While the average is typically obtained by dividing the sum by $n$, we chose to perform this division after decryption in the cleartext domain. Since the message size $n$ isn't considered sensitive information, exposing it doesn't pose a significant security risk.

    {
        auto ctxt_i = HEaaN::Ciphertext(context);
        eval.multImagUnit(ctxt_res, ctxt_i);
        eval.add(ctxt_res, ctxt_i, ctxt_res);

        auto ctxt_conj = HEaaN::Ciphertext(context);
        eval.conjugate(ctxt_res, ctxt_conj);
        eval.add(ctxt_res, ctxt_conj, ctxt_res);
    }

Next, we want to combine the real and imaginary parts of each slot into a single real value. To do this, we introduce two new operations: multImagUnit() and conjugate().

multImagUnit() multiplies the encrypted complex message by the imaginary unit $i$. Note that this operation doesn't require any evaluation key.
conjugate() applies complex conjugation to the encrypted message.

When we apply multImagUnit() followed by an addition, we obtain the following transformation: $$ x + iy \mapsto (x + y) + i (x - y)$$ This result still contains an imaginary component. Since clients could potentially recover the original complex value $x+iy$ from it, we further eliminate the imaginary part using conjugation and addition: $$ (x + y) + i (x - y) \xrightarrow{conj + add} 2(x + y) \\ $$ This allows us to extract only the real part $2(x+y)$, effectively summing the real and imaginary parts. At this point, we've completed the summation across both slots and imaginary parts.

Give it a try yourself and see if you can follow how the rotations and conjugations work together to enable this transformation!

Remark - Rotation without exact keys

In this scenario, we only performed rotations with power-of-two indices, so using genRotKeyBundle() was sufficient. This method conveniently generates just the necessary keys for those specific rotations.

However, in more general cases, supporting all possible rotation indices would require generating a large number of keys — which quickly becomes inefficient in terms of both memory and performance.

To address this, HEaaN employs a clever strategy: Even if you only generate the rotation key for index $1$, the library can internally compose multiple rotations to achieve any desired index. The downside is that this approach can be significantly slower, especially when many rotations are needed.

A more efficient approach is to generate a select set of rotation keys that can be combined to perform any required rotation with fewer operations. HEaaN supports this optimization and automatically minimizes the number of rotation steps based on the available keys.

So if you're looking to minimize key size, you can compute a minimal key set tailored to your rotation pattern. But if memory size isn't a major concern, sticking with genRotKeyBundle() is still a simple and practical choice.

No portion of this book may be reproduced in any form without written permission from CryptoLab, Inc.

Keyboard shortcuts

The HEaaN Book

Homomorphic Operations, Part 2

Week 5 at SuperSecure, Inc.

Code

Explanation

Remark - Rotation without exact keys