Make SymmSHE handle noise estimates and rescaling, at runtime

[cpeikert]

ALCHEMY's type families for tracking noise levels and choosing the moduli from a pool are really complicated, and tax ghc so badly that we often can't even compile.

So, an idea is to make noise-tracking and modulus selection dynamic (at runtime) rather than static, and do this within an SHE implementation. (This should probably sit as an alternative SHE alongside the existing SymmSHE, since it's a very different approach, and there are merits to both.)

The basic idea is that CT would be parameterized by a list of moduli that it could use, though the ciphertext might use only a prefix of that list for its actual modulus. Additionally, a CT value would internally carry a noise estimate (essentially, its pNoise), which would be used to decide when to mod-switch. When two ciphertexts (with the same type list of moduli) are combined in some way, their actual moduli might not match and would need to be reconciled, probably by switching down to match the one with the smaller pNoise.

I'm not sure about the exact form of the CT data type and its implementation. It would probably need to be a GADT: when you match on the constructor, you would discover the type of the actual modulus being used, and it should give you some guarantee (in the form of a constraint) that it's a prefix of the full modulus list. When combining two ciphertexts of the same type, their respective constraints should allow for determining the largest common prefix or whatever, and getting a Rescale[Cyc] constraint, and anything else that would be needed. This all seems doable in principle, but is nontrivial to work out properly.

Tracking pNoise and selecting moduli dynamically has some advantages. Obviously, the main one is the removal of many complex type families, including ones like PreMul. Less significantly, the noise estimates can be made somewhat more accurate because they can use the actual values of the moduli and degrees (n'=phi(m')) and so forth, rather than a "one size fits all" formula.

The main disadvantage is that we'd have runtime errors (or incorrect decryption) in cases where the moduli in the CT type aren't big enough to handle the results of a homomorphic computation. This is not the end of the world, as one can just add more moduli at one place in the code.

What would be really cool is to get something like the best of both worlds, where the SHE implementation is able to do some global (but runtime) analysis to figure out how many moduli of a huge given list are needed, and starts with those for fresh ciphertexts.