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.


1 Answer 1


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.

  • $\begingroup$ @Also, for an example of what D.W. is saying see the hcrypt project. $\endgroup$
    – mikeazo
    Aug 22, 2012 at 0:35
  • $\begingroup$ 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? $\endgroup$
    – Also
    Aug 22, 2012 at 19:27
  • $\begingroup$ 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. $\endgroup$
    – Also
    Aug 22, 2012 at 19:33
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Aug 23, 2012 at 7:03
  • $\begingroup$ BTW on a related note around homomorphic comparisions, there is a description by Shai that sketches out a way to compute an encryption of a bit that is 1 if the comparision is true and 0 otherwise -github.com/shaih/HElib/issues/45 $\endgroup$ Oct 21, 2015 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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