Take the 2-minute tour ×
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.

I am not a hardcore cryptographer so this might be a really stupid question. I am looking through some papers in homomorphic encryption and discovered they describe computation as "circuits", why do they use this particular term? Isn't algorithm a more suitable word? Do "circuits" have some special meaning in cryptography?

share|improve this question

2 Answers 2

up vote 6 down vote accepted

Circuits can be expressed using very simple operations. For example, a boolean circuit consists of only two types of gates, addition and multiplication (where the input values are each 1 bit). Furthermore, (boolean) circuits can describe any computation.

This is very nice when it comes to fully-homomorphic encryption. All we have to do is provide a way to homomorphically evaluate two types of gates and voila, we can evaluate any computation homomorphically. As pointed out in a comment below, circuits have been used for more than just homomorphic encryption. Secure multiparty computation (both the secret sharing and the garbled circuits variants) uses this as well.

This makes the job for cryptographers much easier, but makes things harder on users, right. If I want my super awesome algorithm to be evaluated homomorphically, I've got to come up with a way to implement it as a boolean circuit. That means no loops, no conditionals, etc. I only get addition and multiplication. Other computation paradigms have been looked at. One early one was moving from boolean circuits to arithmetic circuits (not too big of a jump).

Update
Recent work is interested in not limiting programmers to circuits. For example this, this, and this all look at language based approaches.

P.S. Sorry for the link dump. I haven't properly read through these so I can't really comment. A question on how non-circuit approaches work could be a good question to ask. I'm betting there is someone on here who can go into detail on those.

share|improve this answer
1  
@dorafmon It is worth noting that this appears a lot in the field of MultiParty Computation (MPC, such as linear secret sharing and Garbled Circuits) as well as HE. In addition, the circuits don't have to be boolean, there are arithmetic garbled circuits. The basic idea is the expression should be a DAG - no loops and conditionals are just a bit masking of the branches, each of which are evaluated. –  Thomas M. DuBuisson Nov 6 at 19:42
    
@ThomasM.DuBuisson that (conditionals become bit masking where each branch is evaluated) is something that I think a lot of people miss. Thanks for pointing that out. –  mikeazo Nov 6 at 19:49
    
So in this sense, the FHE scheme can support any algorithm, i.e. it is Turing Complete upon encrypted data, right? –  dorafmon Nov 6 at 20:10
2  
About Turing completeness. As I recall, the reason a single circuit can not be said to be Turing complete is because the input size is fixed. However, one also talks about circuit families. Roughly speaking in a circuit family you have one circuit for each input size. To solve a problem you pick the circuit corresponding to the concrete input size. Circuit families are Turing complete. So yes you could theoretically support any algorithm supported by a Turing machine with FHE. –  Guut Boy Nov 7 at 9:13
1  
Ok you are right, you can of course think of it as arithmetic over GF(2). I just find it more clear to talk about XOR and AND to avoid confusion. BTW. actually XOR and AND are not functionally complete, a fact many MPC papers ignore. You also need constant TRUE (or 1) gates. –  Guut Boy Nov 7 at 12:57

IIRC, most current homomorphic encryption systems can evaluate a boolean function. A boolean function can be implemented as a logic circuit. The term was borrowed.

share|improve this answer
    
so homomorphic encryption does not support evaluating arbitrary algorithms on encrypted data? I thought it wouold. –  dorafmon Nov 6 at 16:55
1  
Caveat lector, I am not aware of any homomorphic encryption algorithms that are also Turing complete. Arbitrary mathematical functions are computable over rings, but evaluation of functions involving diverging execution paths are not yet doable in anything approaching polynomial time. –  BitShifter Nov 6 at 16:58
    
@dorafmon : That would be completely incompatible with confidentiality, since one could evaluate an algorithm that will either halt immediately or run for a long time depending on what the data is. –  Ricky Demer Nov 6 at 17:29
1  
@dorafmon, I found this answer and the comments to be interesting and related. –  mikeazo Nov 6 at 18:52

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.