6
$\begingroup$

I've seen the word circuit used in many crypto contexts (for example, regarding FHE in this pdf). I've always thought of a circuit as another word for a program or function. But is there a difference - i.e., is there something that a standard function can do that a circuit can't?

$\endgroup$
  • $\begingroup$ By "normal function" do you mean the normal mathematical definition of a function or something else? $\endgroup$ – otus Jul 15 '16 at 8:30
  • $\begingroup$ Not a mathematical function in the strict sense. I mean a computer program with inputs and outputs $\endgroup$ – Tatiana Jul 15 '16 at 9:00
  • $\begingroup$ I have a sub-question as well: If circuits and computer programs are equivalent, then how can we convert a given program into a circuit? Does there exist an algorithm to do so? $\endgroup$ – Itachi Jul 16 '16 at 3:36
8
$\begingroup$

A circuit is a representation of a (computable) function. There are many other ways to represent a function (mathematical notation, Turing machines, pseudo-code, etc.), but for some purposes it happens that circuits are the most convenient one.

$\endgroup$
  • 5
    $\begingroup$ Another (informal) distinction is that circuits as a representation (as opposed to physical circuits) generally have no loops, and are thus analyzable in simpler ways, e.g. circuit depth. $\endgroup$ – orlp Jul 15 '16 at 11:23
  • $\begingroup$ I have a sub-question as well: If circuits and computer programs are equivalent, then how can we convert a given program into a circuit? Does there exist an algorithm to do so? $\endgroup$ – Itachi Jul 16 '16 at 10:30
  • $\begingroup$ @Itachi How do you define "computer program"? For example a C program is compiled to machine instructions, which are fairly easy to "translate" to a circuit. $\endgroup$ – fkraiem Jul 16 '16 at 10:31
  • $\begingroup$ @Itachi By the way, the source code distribution for the Pinocchio verifiable computing protocol includes a compiler to compile a program written in a subset of C to an arithmetic circuit. vc.codeplex.com $\endgroup$ – fkraiem Jul 16 '16 at 10:59
  • $\begingroup$ I'll ask my doubt as an example: How to convert a C program with a while loop (which loops x number of times, where x an input to the program) into a circuit (whose structure is independent of the input)? $\endgroup$ – Itachi Jul 16 '16 at 12:16

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.