6 ms·

Maybe I'm not understanding this, but how is it that you can know enough about the data to process it without undermining the fundamental concept of encryption?

• luckydata 1mo ago
  you can produce a correct result without knowing what that result means as long as the person you then provide that result to can decrypt it. So the way it works is the server does the job on data it can't read, sends an answer to the device, the device decrypts it. It's very useful for things like healthcare data for example but also for products like "home assistants", and it's one of the use cases that the team hiring internally was giving in their job req. I tried to apply too but didn't get it unfortunately, this was a very interesting product to work on imho, congrats to whoever got my job :)
• mswphd 1mo 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 1mo ago
    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) that some part of the HE inflates some component of the result?
    • 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.
• jijji 1mo ago
  this isnt about the progress of FHE, this is about models hiding reasoning traces (i.e. "thinking") from their paying customers because they dont want them knowing how question A got to answer B.