Homomorphic encryption and some black box attacks
We offer a systematic approach to a class of attacks on communication
channels protected by homomorphic encryption based on black box
algebraic analysis. Our conclusion is that wide classes of algebraic
structures should not be used as ambient structures for homomorphic
encryption. We give some examples for groups and rings, but our general
methodology is much wider applicable.
Black box algebra deals with a category where objects are finite
algebraic structures (fields, rings, group,s projective planes etc.)
with elements implemented as 0-1 strings of length L (perhaps different
for different objects) and operations are performed by external devices
or algorithms which work in time bounded by a polynomial in L).
Similarly, morphisms are homomorphisms computable in polynomial time.
We will show that this is a fascinating theory with many unusual
features and a huge range of open problems.
(Joint work with Sukru Yalcinkaya)
תאריך עדכון אחרון : 11/04/2021