undefined | Better HN

0 pointsxhrpost9mo ago0 comments

This made me wonder if there is such a thing as homomorphic compression. A cursory search says yes but seems like limited information.

0 comments

Tryk9mo ago

What do you mean by homomorphic compression?

Given that the operations you can execute on the ciphertext are Turing complete (it suffices to show that we can do addition and multiplication) then it follows that any conceivable computation can be performed on the ciphertext.

xhrpostOP9mo ago

Oh this is outside the context of encryption. My curiosity was, is there such a compression function that permits operations on the compressed data without first decompressing it?

dachrillz9mo ago

One that is kind of in this spirit is that you can describe sparse matrices by omitting all the zeros and only describe the indices that have data. In this compression you can still perform normal matrix operations without having to unpack them into the “normal form”. Now this is neither encryption nor a particularly interesting compression, but it does prove that it is possible in principle ;p

j / k navigate · click thread line to collapse