# 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? Commented Sep 27, 2012 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
Commented Sep 27, 2012 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? Commented Sep 27, 2012 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
Commented Sep 28, 2012 at 11:40
• @mikeazo, circuit and non circuit is nothing but black box and non black box way of solving , see my answer below Commented Nov 13, 2012 at 9:18
• @ZhigangChen thanks a lot for clarifying the difference, i almost missed it ! Commented Apr 23, 2013 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.
Commented Nov 14, 2012 at 3:58

• 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. Commented Dec 3, 2012 at 2:36