Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 1 down vote favorite

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 ?

share|improve this question
1  
Could you explain (probably in an edit to your question) exactly what the "circuit approach" is? – mikeazo♦ Sep 27 '12 at 11:36

3 Answers

up vote 2 down vote

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.

share|improve this answer
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. – Zhigang Chen 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? – mikeazo♦ 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. – Zhigang Chen 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 – sashank Nov 13 '12 at 9:18
@ZhigangChen thanks a lot for clarifying the difference, i almost missed it ! – sashank Apr 23 at 23:49
up vote 0 down vote

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.

share|improve this answer
2  
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
up vote -1 down vote

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.

share|improve this answer
2  
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. – mikeazo♦ Dec 3 '12 at 2:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.