At present, all FHE scheme are be constructed based on circuit approach. Can we construct fully homomorphic encryption scheme based on non-circuit approach? Is Polly cracker non-circuit approach ?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Polly Cracker is non-circuit.
The best info for this I could find comes from a recent paper proposing a non-circuit approach due to Xiao, et al..
They identify a number of non-circuit systems, but go on to say that "they all either have been broken or lack conclusive security evidence."
They then propose a symmetric system which reduces to the problem of factoring.
So it seems that the answer is yes, one can be constructed. It is still an active area of research, however, and I personally wouldn't use the proposed systems yet.
Now, what I am exactly not quite sure of is what non-circuit means? In the paper I reference, they state:
So is a circuit approach simply that the cryto algorithms assume a single bit plaintext? If that is the case, then there are many, many more FHE systems which are "non-circuit". In fact, the BGV system does not require single bit plaintexts. So perhaps I am missing something in the circuit vs non-circuit discussion.
In cryptographic literature ,a black-box construction is one that uses only the input/output behavior of its components. By contrast, a non-black-box construction relies on the code of its components ( i.e circuit representation gate by gate etc). Non circuit based approach is usually called "black box" approach , a recent paper , although not directly on homomorphic encryption but very close concept can be found here . (Note: I am yet to read it completely, but this is very fascinating paper on black box and non black box approaches ) . If interested you can read "instance hiding" schemes, which are usually on blackbox approaches.
Yes There was recently a breakthrough FHE and it used p-adic ring homomorphism. the paper was published on nov 10 2012. and the algorithm is LITERALLY quasi-linear time without any "lambda" factor in the keys and NO noise in the ciphertext. it seems to be a very big breakthorugh and i don't know why no one has paid attention yet but me :P . here is a link to that paper, its VERY mind boggling and amazing. If you dont know p-adic numebrs, then take a look at the abstract and conclusion; and if the algorithm really works as claimed then it will throw IBM and Microsoft decades behind. here is the link http://www.ijtpc.org/volume1/JTPC1386.pdf I hope you enjoy reading about this breakthrough. btw, the homomorphic part of the encryption "LITERALLY" goes like for addition E(m1)*E(m2) = E(m1+m2) and multiplication is like E(m1)^m2 = E(m1*m2) ; Algorithm says it used p-adic ring exp to obtain this effect. Its way different and much advanced than Gentry's scheme.