Practical differences between circuits and turing machines for cryptography

Question

In formal cryptography, we model algorithms (mostly our adversaries) as (Probabilistic) Turing Machines or as boolean circuits. In our lecture on formal cryptography, we learned that circuits are more powerful than turing machines, in the sense that every polynomial-time (probabilistic) turing machine can be represented by a polynomial-size circuit, but not every circuit can be represented as a polynomial-time turing machine.

As circuits are more powerful, it would intuitively make sense to use them instead of turing machines when modeling algorithms, as proving our system secure against a PPT turing machine does technically not imply security against polynomial-size circuits. However, since people are still using turing machines, I assume that this distinction is mostly irrelevant in practice.

Are there any practical differences between circuits and turing machines for cryptographic research (i.e. are there systems that are secure against PPT turing machines, but not polynomial-size circuits?) or does it exclusively come down to personal preference / convenience which one you use for your proofs?

Remark: I considered posting this to the computer science stack exchange, but decided against it as it is directly related to cryptography. If you disagree, feel free to migrate.

Answer 1

Just looking for a Turing machine vs circuit is a bit misleading. The important distinction is uniform (complexity class BPP) vs non-uniform (complexity class P/poly) adversaries. You can characterize P/poly in terms of circuit families, but also in terms of Turing machines with arbitrary "advice strings." In fact, the latter is the more traditional complexity-theoretic way to define P/poly. So just the fact that a definition mentions Turing machines doesn't mean it only applies for uniform adversaries.

If the authors are being careful, then their definitions will explicitly consider a TM adversary to take some advice string as input, and security must hold for all such inputs. Hence, security holds for P/poly adversaries. Even when the authors are not so careful with the definition, the results almost always carry over for non-uniform adversaries as well.

In general, I think it's safest to just assume non-uniform adversaries unless the paper explicitly says otherwise.

---

Of course, there are times when the distinction is important, and I can mention one way it might manifest itself. We generally have an asymmetry between wanting the "good guys" to be described by uniform algorithms, while protecting against "bad guys" who are non-uniform algorithms. Occasionally this becomes a problem when you want to convert an attack into a construction. For example, you can have a result like "an attack against scheme $X$ implies an improved construction for task $Y$." In these cases you often have to relax one of the definitions to bring them into alignment. For example, either:

• "a [uniform] attack against scheme $X$ implies an improved construction for task $Y$."
• "an attack against scheme $X$ implies an improved [non-uniform] construction for task $Y$."

Some examples:

• Completeness for Symmetric Two-Party Functionalities - Revisited by Lindell, Omri, Zarosim: They show that certain protocols have some round at which Alice can distinguish some information about Bob's input. Then this distinguishing strategy can be used to construct an oblivious transfer protocol. But to incorporate this distinguishing strategy into another protocol, the strategy must be uniform, and the paper has to use a uniform definition of distinguishability. Alternatively, you could allow protocol constructions to be non-uniform.

• In my own paper Universal Composability from Essentially Any Trusted Setup, I define a 2-player game between Alice & Bob. If Alice has a winning strategy in this game, then I create a protocol of one kind. If Bob has a winning strategy, then I create a protocol of a different kind. But in both cases I need the "winning" party's strategy to be uniform (they are the person whose strategy gets incorporated into a protocol), while the "losing" party's strategy can be non-uniform (the losing party corresponds to the adversary in the protocol I construct). So the result leaves a gap (what if non-uniform strategies can always beat uniform strategies)? As above, you could close the gap by allowing protocol constructions to be non-uniform.

Answer 2

I will answer this part specifically:

Are there any practical differences between circuits and turing machines for cryptographic research (i.e. are there systems that are secure against PPT turing machines, but not polynomial-size circuits?) or does it exclusively come down to personal preference / convenience which one you use for your proofs?

In fact, one does not need to go very far to see that non-uniform machines as traditionally defined (deterministic with advice) are not strictly more powerful than probabilistic ones: no non-uniform machine can "throw a coin", i.e., output 0 or 1 each with some specified non-zero probability, obliviously of its input. This is because, even with an advice string, a deterministic machine is still deterministic: given the same input, it will always produce the same output.

For this reason, we often consider probabilistic non-uniform machines, with both an advice tape (as in the traditional definition of non-uniform machines) and a random tape (as in the definition of probabilistic machines), so that we get "the best of both worlds".

However, for many tasks it can indeed be shown that security against deterministic non-uniform adversaries is equivalent to security against probabilistic uniform ones. One-way functions are one example.