# Can we construct fully homomorphic encryption scheme based on non-circuit approach?

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 ?

• Could you explain (probably in an edit to your question) exactly what the "circuit approach" is? Sep 27 '12 at 11:36

Is Polly cracker non-circuit approach?

Polly Cracker is non-circuit.

Can we construct fully homomorphic encryption scheme based on non-circuit approach?

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:

The main works on homomorphic encryption algorithms are circuit based. They develop the encryption schemes and computation algorithms considering a single bit plaintext. All operations on various operand types can then be achieved by constructing the corresponding circuits.

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.

• Xiao' paper I read before two weeks, so this problem produce in my mind. Gentry's definition of FHE isnot same as in xiao's paper. The defination in Xiao's paper is homomorphic rather than fully homomorphic. Even though Polly Cracker is non-circuit, this scheme isnot fully homomorphic encryption.
– user3942
Sep 27 '12 at 14:32
• @ZhigangChen, I'm not sure I follow. Could you explain what Gentry's definition of FHE is and the difference with Xiao's? Do you mean that Xiao's system does not require bootstrapping, and other tricks that Gentry's system does require? Sep 27 '12 at 14:40
• Homomorphic scheme in Xiao's paper can only compute polynomial on encrypted data rather than arbitary functions, for example, loop, Xiao's scheme cannot compute. Fully homomorphic scheme can compute arbitary functions(include loop), it is because circuit model is used in FHE. Any computation in FHE first express circuit to compute.
– user3942
Sep 28 '12 at 11:40
• @mikeazo, circuit and non circuit is nothing but black box and non black box way of solving , see my answer below Nov 13 '12 at 9:18
• @ZhigangChen thanks a lot for clarifying the difference, i almost missed it ! Apr 23 '13 at 23:49

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.

• It's hard for me to tell (the original question is not very clearly written), but my guess is that I don't think this is what the original question-asker meant by "circuit approach".
– D.W.
Nov 14 '12 at 3:58

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.

• I posted this on your other post, but what you are describing is not fully homomorphic. $m_2$ is not encrypted. You can not get the multiplication of two encrypted values (at least I'm assuming not, I haven't read the paper). Furthermore, I don't see how this particular answer goes along with the question of non-circuit based FHE. Dec 3 '12 at 2:36
• I count three or four red flags just in the abstract and keywords of this paper. Also, what is the security reduction? What evidence is there that the underlying problem is computationally hard? Oct 13 '15 at 20:07
• "ZK111 is perhaps the only known public-key encryption algorithm which is also Information Theoretic Secure." My bullshit detector is going crazy. Oct 13 '15 at 20:09