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 0 down vote favorite

If it isn't already apparent from the title of my question, i should make clear that I have only a very basic understanding of homomorphic encryption.

I would like to know why homomorphic encryption schemes cannot support algorithms with conditions/branching, and what the likely impact will be on the overall adoption of HE schemes. Given this limitation, are HE schemes likely to be useful in real life? Thanks.

share|improve this question

1 Answer

up vote 2 down vote accepted

I think you have a misconception. Fully homomorphic encryption can support algorithms with conditions and branching. Any such efficient algorithm can be unrolled to be implemented as a circuit (say, with just AND and NOT gates), removing all conditions and branching, and thus can be implemented on encrypted data using fully homomorphic encryption.

Of course, fully homomorphic encryption schemes are hardly practical right now; search this site for more details.

share|improve this answer
@Also, for an example of what D.W. is saying see the hcrypt project. – mikeazo♦ Aug 22 '12 at 0:35
Thanks for your answer. I think I need to understand the process for translating (compiling?) an algorithm to a circuit - any links to introductory texts/resources would be appreciated. I noticed on the hcrypt page that it states 'Garbled Circuits only support one-pass linear circuits' - whilst GC and secure function evaluation are an alternative to HE, this limitation in complexity sounds similar to what I believed about HE. I suppose the definition of an 'efficient' algorithm is important here. Is it is possible to express an upper bound on complexity for HE in simple terms? – Also Aug 22 '12 at 19:27
I hope the last question above is clear - I am trying to understand how sophisticated the processing algorithm in an HE system can be, which I have seen referred to as the evaluate() function in papers (apologies if I am misusing terms here). If this would be better as a separate question, let me know and I can delete these comments and re-post as a separate question. – Also Aug 22 '12 at 19:33
1  
@Also, It's a standard elementary result in computer science that any poly-time computation (say, taking a n-bit input and producing a 1-bit output) can be converted into a poly-size circuit. e.g., This is part of the Cook result for why SAT is NP-complete. For more details, you might ask on the Computer Science Stack Exchange site, as that result does not involve any crypto. – D.W. Aug 23 '12 at 7:03

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.