Amazing summary, Jeremy!<p>One nitpick is regarding the double-CRT: you are referring to the RNS encoding, when the original paper[0] uses the term to talk about how polynomials are stored for fast computation. It's a nice philosophical view of decomposing the polynomial Φm(X) into products X − ζi the same way that the integer modulus Q is decomposed into primes. So it's more like one CRT on the coefficients, and another implemented as a DFT.<p>[0] <a href="https://eprint.iacr.org/2012/099" rel="nofollow">https://eprint.iacr.org/2012/099</a>
for those wondering about the and/xor thing, well, of course a nand b is just 1 xor (a and b), but you can do enormously better than that!<p>it turns out there's a very pretty formulation of boolean combinational logic (i can't bring myself to say 'circuits') called zhegalkin polynomials, in which arbitrary boolean functions are just polynomials in gf(2). i wrote a simple implementation of them in <a href="http://canonical.org/~kragen/sw/dev3/zhegalkin.py" rel="nofollow">http://canonical.org/~kragen/sw/dev3/zhegalkin.py</a>.
Again my math ignorance screws me, I wish I had more acumen here to grasp it all but this did catch my eye: “ In one example FHE scheme with lightweight keys, a ciphertext encrypting a single integer is on the order of 25 KB, and the special keys are about 0.5 GB.”
I’ve been trying to puzzle out the market for this kind of technology.<p>Making truly private data actually useful while retaining the privacy would of course be incredible and the use cases are obvious. But the people that have big data generally are not interested in privacy at all.<p>Academic interest in fhe is understandable since it’s fascinating, but why does industry care? Is this just hedging their bets for if/when the future brings stronger data regulation?
I wonder is there is some restricted kind of homomorphic encryption so that the encryption is tailored to be used for certain kind of programs. For example if the program is to compute the average of a list of numbers then some simple encryption could be done just to compute the average and nothing more. Is there some related concept to this idea of the encryption restricted to a concrete computation?
> For example, it is not be possible to write an FHE program that uses fewer instructions than the program’s worst-case input. Doing so would reveal information that the input is not the worst-case, which contradicts the security of the cryptography. Instead, an FHE program must eagerly compute all branches of if-statements, and then use a select statement to decide which result should be used.<p>What exactly is "select statement"? Curious to know how to select a value without giving away what this value equals to (even in encrypting form). Otherwise I assume it would give away as much as seeing which branch was taken.
I've been following Jeremy's blog for some years now and although I don't always understand everything, I appreciate it for being a relatively accessible look into the research that's going on.<p>> you can implement ciphertext-ciphertext multiplication: x.y = ((x^2 + y^2) - (x^2 - y^2))/4<p>However this one part confused me - the RHS seems to simplify to y^2 / 2. Is there a mistake here or is this specific to the polynomial fields being worked in? (Or am I being dumb?)
> Much of the FHE industry is focused right now on the subset of applications where legal hurdles make the two available options “slow, but compliant” and “fast, but incurs prison time.”<p>Anyone have any examples of these applications?
what are potential benefits and use cases of writing a program using FHE if the program is literally a million times slower than a similar program without FHE?
I believe that homomorphic encryption is one of those technologies that is too dangerous to develop. It is one step to a path where any person on earth will eventually have access to enormous amounts of computation. Is that a good thing? Well, it means one can do high-powered AI research on chemical and biological weapons or advanced malware by using high-powered compute clusters that they may not otherwise have access to. Moreoever, it will be impossible to detect since the computations themselves are encrypted.