4 ms·
the basic encryption scheme used here is fairly straightforward actually, at least the symmetric encryption version. Let s be a uniformly random, 512-dimensiona
by mswphd 2mo ago
the basic encryption scheme used here is fairly straightforward actually, at least the symmetric encryption version. Let s be a uniformly random, 512-dimensional u32 vector. To encrypt a message m (say a 512-dimensional bit vector for simplicity), you
1. generate a 512 x 512 random (u32) matrix A, and
2. generate a 512-dimensional rounded (to the nearest integer) Gaussian, say of standard deviation 10, e.
The ciphertext is then [A, b :=As + e + 2^8 m].
To decrypt, you compute b - As to recover 2^8 m + e. You can then recover m, as e << 2^8 with high probability.
Anyway, if you have two of these ciphertexts, you can sum them together to get
[A1 + A2, (A1 + A2)s + (e1 + e2) + 2^8 (m1 + m2)]
this decrypts to m1 + m2, so you can recover homomorphic sums (or scalings by small integers).
Multiplication is more complex, so I won't get into it here. But the high level from the above example is that you could have someone compute arbitrary linear functions of your data without them knowing what your data is.
- Chris2048 2mo agoWill the new (summed) A, e and b be the same size as the originals, and is m2 + m2 still a 512-dimensional bit vector? I though (when I tried to understand it) that some part of the HE inflates some component of the result?
- mswphd 2mo agoonly temporarily, and only for multiplication. At a very high level, the idea is that you view C := [A, b] as satisfying CS = 2^8 m + e here, S = [-s, 1] is a padded version of the initial secret. So recast everything as a linear equation (matrix) equation CS = 2^8m + e Without getting into too much details, one can define a "product" * such that (CC)(SS) = (2^8m + e)(2^8m + e) This becomes a "degree 2" equation. Mildly faking the details for simplicity, one can expand it out not in terms of A, b, but in terms of three components A, b, c, where c is the "degree 2" component. So here things have inflated. But there is also a technique to shrink this back down to a linear equation. This shrinking process requires some auxiliary data, namely an encryption of SS under S. it is not the problematic part of HE though. Instead, data movement (say a circular rotation by k indices) also requires some "fixing up", though here involving an encryption of rot^i(S) under S. This is more problematic, as there are many different rotations (often on the order of thousands), and you naively need a piece of auxiliary data for each of them (vs one for multiplication). There are ways to shrink the required number of keys, but in general they're the "heavyweight" part of FHE.