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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
10
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.
-
1$\begingroup$ @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. $\endgroup$ Commented Nov 6, 2014 at 19:42
-
$\begingroup$ @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. $\endgroup$– mikeazoCommented Nov 6, 2014 at 19:49
-
$\begingroup$ So in this sense, the FHE scheme can support any algorithm, i.e. it is Turing Complete upon encrypted data, right? $\endgroup$ Commented Nov 6, 2014 at 20:10
-
2$\begingroup$ 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. $\endgroup$– Guut BoyCommented Nov 7, 2014 at 9:13
-
2$\begingroup$ 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. $\endgroup$– Guut BoyCommented Nov 7, 2014 at 12:57
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ so homomorphic encryption does not support evaluating arbitrary algorithms on encrypted data? I thought it wouold. $\endgroup$ Commented Nov 6, 2014 at 16:55
-
1$\begingroup$ 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. $\endgroup$ Commented Nov 6, 2014 at 16:58
-
$\begingroup$ @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. $\endgroup$– user991Commented Nov 6, 2014 at 17:29
-
1$\begingroup$ @dorafmon, I found this answer and the comments to be interesting and related. $\endgroup$– mikeazoCommented Nov 6, 2014 at 18:52