Unlimited computations on same ciphertext with fixed precision requirements

FHE Use Cases
1

Hi,

I am currently trying to apply the OpenFHE library to my use case:

  1. Vectors of arbitrary length, either integer or floating point (depending on the applicability of bootstrapping)
  2. Computation function consisting of multiple multiplications and additions of ciphertexts and plaintexts
  3. Apply computation function (theoretically) unlimited amount of times to the same resulting ciphertext, without runtime limits

My question is, if it is possible to utilize the OpenFHE library (the python wrapped one in particular) to realize such an application. I tested the “Iterative CKKS bootstrapping” example test and found that the bit precision decreases with each multiplication between two floating point vectors until the point of 0 bit precision is reached and the computation fails.
As far as I understood, using bootstrapping after each multiplication should allow me to apply multiplication to the same ciphertext an unlimited amount of times, if performance and runtime is not an issue.
Is this a wrong assumption? And if I switch to integer vectors, is it then possible to realize arbitrary many computations with OpenFHE?
The result of the computation does not require high precision, it would suffice to provide 2 decimal digits for floating point numbers.

Thanks in advance

2

Hi!

You should totally watch some of the videos from Duality on Youtube. They are @dualitytechnologies796, and you’ll find nice descriptions.

I don’t see BGV bootstrapping in the code base (someone correct me if I’m wrong). You can use CKKS pretty well, though. You don’t need to bootstrap after each multiplication. Bootstrapping usually sets up the ciphertext to do a bunch of multiplications before it’s needed again. A fresh ciphertext is like a new car. First, it takes a long time to get dirty. Then you clean it, and it’s never that new car clean again.

If the vector is arbitrary length, you write code to split the vector among arbitrary ciphertexts.

The theoretically unlimited part is dicey. When a bootstrap refreshes a ciphertext, there is some noise, still, and this builds up. You’d have to test it for particular parameters.

So I think you’re in the right ballpark, but go watch a video.
Hope All Is Well,
Drew

1 Like
3

The current version of OpenFHE includes approximate bootstrapping for CKKS and bootstrapping for binfhe schemes (TFHE and FHEW).

1 Like
4

You can find the answer to your question in this thread.

Also, I would like to note that OpenFHE includes 128-bit implementation of CKKS which offers higher precision. See the example (src/pke/examples/advanced-real-numbers-128.cpp) for more details.

1 Like
5

Thanks for the quick responses @adolgert and @Caesar!

I’ll check out your mentioned approaches. So as far as I understood, Integer Bootstrapping is not yet possible. Maybe it helps if I outline my design a little bit more in detail:

  • First my formula looks like this, where c* represents ciphertext vectors and p* represents plaintext vectors: (c1 * c2)+(c3 * p1)+p2 = c4
  • Then I perform the following computation: c4+c5=c6, where c5 is also some ciphertext vector resulting from the same formula as noted in my first bullet point but with other values for the vectors.
  • And these two calculations should theoretically be performed an unlimited amount of times. Due to the multiplications, the vector values can also become quite large.

Additions do not add a significant amount of noise, as far as I understood. However, multiplications are more of a problem. (c1 * c2) increases the multiplicative depth by 1, but is that also the case for ciphertext-plaintext multiplication (c3 * p1)?

I (maybe) also found a bug in the python implementation of the “simple-ckks-bootstrapping.py” example. When I run the same example in C with the corresponding codebase I get the following output:

CKKS scheme is using ring dimension 4096

Input: (0.25, 0.5, 0.75, 1, 2, 3, 4, 5, ... ); Estimated precision: 59 bits

Initial number of levels remaining: 1

Number of levels remaining after bootstrapping: 10

Output after bootstrapping: (0.250002, 0.500002, 0.750008, 1, 2, 3, 4, 5.00001,  ... ); Estimated precision: 18 bits

But the python code gives me the following output:

CKKS is using ring dimension 4096

Input: [0.25, 0.5, 0.75, 1.0, 2.0, 3.0, 4.0, 5.0]

Initial number of levels remaining: 0

Number of levels remaining after bootstrapping: 0

Output after bootstrapping: (0.25, 0.5, 0.75, 1, 2, 3, 4, 5,  ... ); Estimated precision: 46 bits

Is that correct?

Thanks in advance

6

The Python doesn’t look right, as you know. It wouldn’t bootstrap with no levels remaining, and if there were no levels after the bootstrap (which can happen for certain choices of parameters) then the bootstrap would inform you that it failed. Also, Python doesn’t truncate 0.250002 to 0.25 when it prints.

For the calculation, all the iterative examples are fixed-point iterations, meaning they repeat but don’t blow up. Calculations that would normally blow up are even more likely to fail in CKKS because the underlying representation is integers with an implied denominator, more like fixed-point math. You may find a way to turn your calculation into something more stable by taking a single element of each vector and representing one iteration as a matrix multiplication where the matrix elements are from those vector elements. Then ask what happens when you raise that matrix to the N-th power. You want that not to blow up.

Like you, I’ve been trying to get a feel for how CKKS works in OpenFHE, and I’ve found a combination of listening to talks, reading articles and code, and trying it out has been the best way forward. In the code examples, they show you how to see how many levels remain in a ciphertext. You can try different operations and see how many levels remain.

HTH,
Drew

1 Like
7

@reneroliveira

Can you look into this? Specifically why there is a difference between the C++ and Python versions?

1 Like
8

@reneroliveira Looks like the precision used for outputting real-number results in Python should be increased.

1 Like
9

@ypolyakov Alright, that’s easy to change. @iquah I’m comparing the c++ and python source code, the main difference is in the GetBootstrapDepth‎ function.

C++ is using the following signature:

static uint32_t GetBootstrapDepth(const std::vector<uint32_t> &levelBudget, SecretKeyDist secretKeyDist)

While the Python wrapper is using another:

static uint32_t GetBootstrapDepth(uint32_t approxModDepth, const std::vector<uint32_t> &levelBudget, SecretKeyDist secretKeyDist)

I’ll add this bug as a Github Issue to be fixed in the next minor release

1 Like
10

Updates:

The bug was fixed in the dev branch and will be merged into the main in the next minor release.

Now, that’s how Python output will look like:

image
image783Ă—115 3.73 KB

To test this version, change the repository branch using git checkout dev and the git pull to get the latest development updates.

1 Like
11

I figured out that the problem here isn’t printing precision. The file is meant to test bootstrapping, but it constructs ciphertexts that have all of their towers. That’s why GetLevels() returns 0, because no multiplications have happened on these ciphertexts. The example should, instead, create the cipertext with:

cryptocontext.MakeCKKSPackedPlaintext(x, 1, depth - 1, None, num_slots)

The reason for this confusion is that the bootstrap operation makes a confusing algorithmic choice. It performs a bootstrap and, if the result has fewer towers than the input, it silently returns the input. That’s why GetLevels() returns 0 before bootstrap and 0 after bootstrap. This will be the case until you drop at least 22 levels.

Here, look at a for-loop. We’ll print out the starting levels and ending levels. When the start and end are the same, the maximum value is 5.0, on the dot. When the start and end differ, the maximum value has some noise.

Drop 19 Levels 19-19 5.0
Drop 20 Levels 20-20 5.0
Drop 21 Levels 21-21 5.0
Drop 22 Levels 22-21 4.9999999917905384
Drop 23 Levels 23-21 4.999999992390556
Drop 24 Levels 24-21 4.999999992828425
Drop 25 Levels 25-21 4.99999999158975
Drop 26 Levels 26-21 4.999999991378976
Drop 27 Levels 27-21 4.999999992965592
Drop 28 Levels 28-21 4.999999988505235
Drop 29 Levels 29-21 4.999999993169833
Drop 30 Levels 30-21 4.999999993553647

HTH,
Drew

12

Hi @adolgert,

The reason for this confusion is that the bootstrap operation makes a confusing algorithmic choice. It performs a bootstrap and, if the result has fewer towers than the input, it silently returns the input. That’s why GetLevels() returns 0 before bootstrap and 0 after bootstrap. This will be the case until you drop at least 22 levels.

Yes, this is by design as it does not make sense to call bootstrapping when the result one gets after bootstrapping has less multiplicative levels left than the input. This is often beneficial for initial iterations of deep ML applications. Using the leveled approach for the first few iterations in these cases is typically more efficient than calling bootstrapping after every iteration.

13

Hi Yuriy!

First, I see the update from yesterday fixed the bug, so my timing was terrible.

Second, thanks for addressing this minor complaint! It’s these lines, which return the original ciphertext after it goes to all the trouble to compute the bootstrap.

    if (bootstrappingNumTowers <= initSizeQ) {
        return ciphertext->Clone();
    }

As a user who is learning, I’ve written code that failed to notice that I had made a mistake because there is no feedback. You, of course, deal with more users and their experiences, but that’s mine.

Third, I’m loving the Python wrappers! I’m looking for a way to help with them. We’ll see how it goes.

Thanks,
Drew

1 Like
14

Hi @adolgert, thanks for the words about the wrappers, and the interest in helping us. You might like this post!

15

Thanks for the tip. I’ll talk with Yuriy. There might be a way we can do this work with funding. - Drew