Complexity leveraging is a technique that is generally used to prove adaptive security of a selectively secure scheme. Eg: We can prove adaptive security of Yao's garbling scheme using complexity leveraging. Many papers mention about complexity leveraging, but does not present in detail. I would be grateful if someone could explain complexity leveraging with a detailed example.


1 Answer 1


Complexity leveraging is a type of reduction where the "reduction algorithm" runs in a complexity class that is greater than the adversary. For example, one may construct a simulator that runs in time $n^{\log n}$ although the adversary is only polynomial time. When considering the simulation paradigm, this is not very satisfactory. For example, in zero-knowledge, the argument is that the adversary learns nothing since it can generate anything it sees by running the simulator itself. However, when using complexity leveraging, the adversary actually cannot run the simulator (since it is in a lower complexity class). Nevertheless, in some cases, it can be meaningful. For example, let's consider a security notion that is "game-based" or indistinguishability based. We then prove that if an adversary running in polynomial-time can break our scheme, then there exists an adversary running in time say $n^{\log n}$ who can break a hash function (or anything else; this is just an example). Now, if the hash function is assumed to be secure for any adversary running in time $n^{\log n}$ then this is enough to guarantee the security of our scheme.

I am personally not a big fan of complexity leveraging. Beyond the definitional disadvantages in some cases (e.g., with simulation), there is also a big disadvantage in that it requires a much stronger assumption (not that a primitive cannot be broken by poly-time adversaries, but by super-poly-time adversaries for some specific function). However, it has been used successfully to achieve things that are otherwise unknown. In addition, in many cases, a first construction used complexity leveraging, and then later constructions succeeded in getting rid of the assumption.


Added later: The reason why stronger assumptions are needed is as follows. Assume that you have a reduction from ZK to OWFs so that any algorithm distinguishing the simulation from a real execution with non-negligible probability can invert the OWF with non-negligible probability. Now, assume that you use quasi-polynomial simulation. In order to argue that the adversary learns nothing, you need to assume that the one-way function is secure against quasi-polynomial inverters. This is because, in order to replace the real proof execution with a simulated one, you need to run in quasi-polynomial time. So, now you have a quasi-polynomial time adversary who is actually running. Then, the reduction to the OWF will only work if the adversary cannot break that OWF. (Of course, this is all handwaving, but this is what happens in proofs.)

  • $\begingroup$ Excellent answer. Can you also please explain how to prove adaptive security of Yao's garbled circuits using complexity leveraging? $\endgroup$
    – satya
    Oct 18, 2016 at 3:33
  • $\begingroup$ Sorry; not really. You will need to read the paper. I assume that the simulator who generates a "fake" garbled circuit (adaptively) runs in time that is superpolynomial... $\endgroup$ Oct 18, 2016 at 7:14
  • 1
    $\begingroup$ In another answer (which has now been deleted), it was stated that complexity leveraging was a technique that turns proofs of selective security into proofs of adaptive security. You dismissed this as being wrong, however, this seems to be exactly how Chatterjee, Koblitz, Menezes and Sarkar use the term in Another look at tightness II (Section 3, page 4). Hence, I am a bit confused. Is there source in the literature that provides a definition closer to your answer? $\endgroup$
    – hakoja
    Oct 18, 2016 at 10:11
  • $\begingroup$ Can you also please explain why stronger assumptions to prove security when complexity leveraging is applied (eg: subexponential one way functions instead of one way functions) $\endgroup$
    – satya
    Oct 18, 2016 at 14:29
  • 1
    $\begingroup$ @satya I did not say that the notion is meaningless, I said that it's weaker. It's true that an adversary running in quasi-polynomial time cannot learn anything, and likewise an adversary running in polynomial-time. However, you also need to assume that the OWF is secure against STRONGER adversaries. Thus, you lose something. There are other bigger problems which can happen if you assume sub-exponential hardness, then all primitives must be this strong and this can be problematic. $\endgroup$ Oct 18, 2016 at 16:33

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.