search

google / heir

A compiler for homomorphic encryption
https://heir.dev/
Apache License 2.0
290 stars 43 forks source link

Support "compressed" ciphertext encryption #886

Open AlexanderViand-Intel opened 1 month ago

AlexanderViand-Intel commented 1 month ago

We might want to eventually support "compressed" encryption, where instead using the whole random "a" polynomial, you just provide the seed for "a" and what PRNG to use. This gives a nearly free 2x reduction in communication overhead (for the client->server direction) and is therefore used pretty much universally when fresh ctxts are stored/sent across the network.

I'm guessing it'd need its own lwe.compressed_encrypt (or similar), and probably also an explicit "decompression" op to turn it into a "real" ciphertext. In terms of type, this could either output an (R)LWE ciphertext with one of the Attributes (which are currently being reworked) indicating the compressed nature, or it could output a special compressed ciphertext type.

Lowering the encrypt op would probably produce a tuple<!polynomial.polynomial<...>, i32> (or whatever integer type is required for the seed), and the lowering the decompress op would be basically the "previously skipped" parts of the encrypt lowering.

ai-mannamalai commented 2 weeks ago

You'd also need a PRNG state machine Op description ?