8
$\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$
3
  • $\begingroup$ By "normal function" do you mean the normal mathematical definition of a function or something else? $\endgroup$
    – otus
    Jul 15, 2016 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, 2016 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$
    – sun
    Jul 16, 2016 at 3:36

1 Answer 1

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$
6
  • 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, 2016 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$
    – sun
    Jul 16, 2016 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, 2016 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, 2016 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$
    – sun
    Jul 16, 2016 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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