7 ms·

Will 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)

• mswphd 1mo ago
  only 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.