1
$\begingroup$

I've been messing around with SEAL library for a few days and I've got a following question.

I've got a bunch of datapoints [x_1, ..., x_n], n < poly_mod_deg of type 'double' and I use batch encoding and CKKS sceheme to calculate their average and variance. Calculating average works fine and I like the result, but I would like to calculate variance in more efficient way.
To explain what I mean:

Going into variance calculation I have following data:
Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0]) and
Encrypted([x_avg, x_avg, x_avg, ..., x_avg]) (*)

Next I calculate their difference and get something like:
Encrypted([x_1 - x_avg, x_2 - x_avg, x_3 - x_avg, ..., x_n - x_avg, -x_avg, -x_avg, ..., -x_avg]) (**)

Then I square and get:
Encrypted([(x_1 - x_avg)^2, (x_2 - x_avg)^2, (x_3 - x_avg)^2, ..., (x_n - x_avg)^2, x_avg^2, x_avg^2, ..., x_avg^2]) (***)

And then I sum first n values using n left by-one rotations and divide the result by n to finally get the variance.
-----------------------------------------------------------------
This works fine for small n. But I want to zero-out useless components at (*) or (**) or (***) so that after squaring I'd get the following:
Encrypted([(x_1 - x_avg)^2, (x_2 - x_avg)^2, (x_3 - x_avg)^2, ..., (x_n - x_avg)^2, 0, ..., 0])

I want that because then I'm able to calculate their sum using only log2(poly_mod_deg/2) sumations using technique described in https://www.youtube.com/watch?v=XaYEHnaAg8M&t=47m29s Is it possible to achieve that in simple, secure in efficient way?

I've tried to multiply (*) or (**) or (***) by [1.0, 1.0, ..., 1.0, 0.0, ..., 0.0], where all but the first n components are zero. It didn't work because compiler complained with 'result ciphertext is transparent' and aborted the mission and I didn't like that solution anyway since it uses one more multiplication, which hopefully is excessive.

Increasingly desperate I also tried to copy encrypted zero from
Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0]) into last components of
Encrypted([x_avg, x_avg, x_avg, ..., x_avg]).
I did something like:

c_zero = Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0])[n+1];
while n < i < poly_mod_deg:
    Encrypted([x_avg, x_avg, x_avg, ..., x_avg])[i] = c_zero;
    i++;

But i guess this stuff just doesn't work this way, since printing out last 20 or 30 values of
Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0]) shows no repetition.
On that note, this also probably means that i always have to inform "server-side" about the number of encrypted datapoints in ciphertext? How unsafe is that?

I didn't want to bloat the post with code, so it's here: https://pastebin.com/Uy0wdgG9. Also deleted comments from the code, since they were in my native tongue. Sorry.

Also on the chance that someone from the SEAL team sees this: great job, fun stuff!

$\endgroup$
4
  • $\begingroup$ What about if you also precompute the ciphertext $c = enc(0, 0, ..., 0, -x_{avg}^2, ..., -x_{avg}^2)$ and add it to (***)? $\endgroup$ Oct 13, 2020 at 12:39
  • $\begingroup$ How do you compute $enc( x_{avg}, x_{avg}, x_{avg}, ..., x_{avg})$ in (*)? Couldn't you simply compute $enc( 0, ..., 0, x_{avg}, x_{avg}, ..., x_{avg})$ instead? Then your difference followed by the square would result in the desired value. $\endgroup$ Oct 13, 2020 at 12:43
  • $\begingroup$ @HilderVitorLimaPereira from their variance computation (and their code, but I am not familiar with SEAL in particular) it seems like they compute the sum of (enough) cyclic rotations of $\vec{x} = (x_1,\dots, x_n, 0,\dots, 0)$ to get each slot to contain $\sum_i \vec{x}_i$. $\endgroup$
    – Mark Schultz-Wu
    Oct 14, 2020 at 5:19
  • $\begingroup$ Also, it is worth mentioning that you are already informing the server of the number of encrypted datapoints $N$ to compute the division in $\mu = \sum_i \vec{x}_i / N$. This explicitly leaks the number of datapoints that you have, which may or may not be an issue. Of course, if you're ok with the quantity being public you can just have your initial array be $(x_1,\dots, x_n)$, and compute their mean via your cyclic rotation trick to get an array of the right size containing the mean, so I assume you do not want to make the number of encrypted data points public. $\endgroup$
    – Mark Schultz-Wu
    Oct 14, 2020 at 5:26

1 Answer 1

1
$\begingroup$

As a caveat, I have never worked with Microsoft SEAL. But the following may still be useful.

The formula for the variance of a finite dataset $(x_1,\dots, x_n)$ can be written as: $$\sigma^2 = \frac{1}{n}\sum_{i = 1}^n(x_i - \mu)^2$$ where: $$\mu = \frac{1}{n}\sum_{i = 1}^n x_i$$ Note that $n\mu = \sum_{i = 1}^n x_i$ --- I will switch between these two expressions freely.

One can algebraically manipulate the expression for $\sigma^2$ to the following expression: $$\sigma^2 = \frac{n\sum_{i = 1}^n x_i^2 - \sum_{i = 1}^n x_i}{n^2}$$ (check that this is an identical formula)! This expression can be computed more easily as follows. Let $\vec{x} = (x_1,x_2,\dots, x_n, 0,0,\dots,0)$ be your plaintext vector, where I assume $n$ is a secret parameter (things are easier if this is not the case, but not by much). Let $c$ be the encryption of $\vec{x}$.

  1. Compute the ciphertext vector $c_{n\mu} =(n\mu, n\mu,\dots, n\mu)$ via your rotation trick (you already do this)

  2. Square $c$ coordinate-wise to get the vector $c_{x_i^2}$ with "slots" $(x_1^2,\dots, x_n^2, 0^2,\dots, 0^2)$

  3. Apply your rotation trick to $c_{x_i^2}$ get the vector $c_{\sum_i x_i^2} = (\sum_i x_i^2, \sum_i x_i^2,\dots, \sum_i x_i^2)$

Now, any slot of $c_{n\mu}$ (they all take the value $n\mu$), any slot of $c_{\sum_i x_i^2}$ (they all take the value $\sum_{i = 1}^n x_i^2$), and $N$ are sufficient to compute the variance via the formula: $$\sigma^2 = \frac{n\sum_{i = 1}^n x_i^2 - n\mu}{n^2}$$ If you can defer this computation to decryption (even as $N\to\infty$ it should remain quite efficient, like 4 arithmetic operations) then you should do that (and the ciphertext can take the form $(c_{n\mu}[0], c_{\sum_i x_i^2}[0], c_N)$, where $c_N$ is a ciphertext encrypting $N$). If not, the problem is reduced to being able to extract (any) "slot" of a SEAL ciphertext, which is likely quite possible without doing more multiplications.

This leads to a number of different situations:

  • If $N$ must be kept secret and you cannot defer this computation, you then must clearly compute the multiplications $c_N\times c_N$, $c_N\times c_{\sum_i x_i^2}$ (which can be done in parallel, increasing multiplicative depth by 1), and the division by $c_N\times c_N$, leading to a computation of multiplicative depth 3 (the same complexity as your "bad" situation of zeroing things by multiplying by the ciphertext encryption $(1,1,\dots,1,0,0,\dots,0)$.)

  • If $N$ can be public, you only have to compute scalar multiplications, so can be done in (total) multiplicative depth 1

  • If you can defer the computation to decryption, you can do the entire computation in total multiplicative depth 1 again (even while keeping $N$ secret).

All of this discussion is assuming that you want to minimize multiplicative depth. It looks like you are using CKKS as your underlying scheme, and I can't remember if its complexity is controlled by multiplicative depth or something more esoteric (such as GSW's way of computing the complexity of multiplications). Still, the two points of:

  • Rewriting computations to be algebraically identical, while (hopefully) simpler to compute homomorphically
  • Deferring (small) parts of the computation for execution on the client when possible

are worth keeping in mind as generic ways to optimize things.

$\endgroup$
6
  • $\begingroup$ Thank you for taking time trying to answer my question. I took last of your equations and canceled out n. What i got is (sum((x_i)^2) - mean)*(1/n), which is equal to original equation for variance (first equation for variance you stated) only when mean = 0 or mean = 1/n, neither is general case. I also have troubles with understanding what is 'N'. The same as 'n'? That would contextually kind of make sense but on the other hand renaming variable for seemingly no reason makes no sense to me... $\endgroup$
    – vids
    Oct 14, 2020 at 8:35
  • $\begingroup$ ...and thirdly i am not sure about the next statement: "If N can be public, you only have to compute scalar multiplications, so can be done in (total) multiplicative depth 1". Even if your technique for calculating variance was correct, we'd still have at least multiplicative depth 2: squaring and dividing by N (i am assuming here that N = n). I have to rescale after plaintext multiplication and thats why in my mind plaintext multiplication increases multiplicative depth of expression. I don't know about formal definition of the term though. $\endgroup$
    – vids
    Oct 14, 2020 at 8:40
  • $\begingroup$ but i took your advice and with some algebraic manipulation got equivalent expression for variance: (1/n)*(sum((x_i)^2)) - mean^2*(2+n) which has multiplicative depth 3 (first term: squaring and multiplying with scalar is depth 2, second term is mean (multiplicative depth 1) squared (multiplicative depth 2) and multiplied by scalar (multiplicative depth 3)?) and also i can compute the sum inside efficiently. So I'll probably try it that way and see how it does. $\endgroup$
    – vids
    Oct 14, 2020 at 9:01
  • $\begingroup$ @vids The variance of a probability distribution is equal to $\mathsf{Var}[X] = \mathbb{E}[(X - \mu)^2] = \mathbb{E}[X^2] - \mathbb{E}[X]^2$. I was assuming that you were given a finite number of samples from a distribution and wanted to compute the sample variance. And if $N$ can be public, you can "simply" compute $1/N$, and then compute the "scalar multiplication" of $1/N$ and your ciphertext. Scalar multiplications are a much easier problem to solve than general multiplications (for example, any linearly homomorphic encryption scheme $\endgroup$
    – Mark Schultz-Wu
    Oct 14, 2020 at 17:43
  • $\begingroup$ can compute this by essentially repeated addition, but this does not give you FHE schemes from linearly homomorphic encryption schemes). As LWE is noisy there are other techniques which are preferable, but I don't know enough about CKKS to know the precise technique which should be used instead, just that there's likely a cheaper technique which is closer to the cost of an addition than a (ciphertext times ciphertext) multiplication. $\endgroup$
    – Mark Schultz-Wu
    Oct 14, 2020 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.