New answers tagged


An example: low outcome, or expectation in terms of game theory, can be the reason for a class of adversaries that are neither probabilistic quasi-polynomial nor PPT, and would only go after polynomial-logarithmic-time targets.


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 ...


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 ...

Top 50 recent answers are included