Complexity leveraging in case of exponentially many hybrids

Question

Complexity leveraging is a proof technique in cryptography where the reduction algorithm runs in super-poly time. (see this). Many papers use complexity leveraging when there are exponentially many hybrids. Here is an example.

Suppose, we need to prove that two experiments $Expt \;0$ and $Expt \;1$ are computationally indistinguishable. Then, we come up with a sequence of hybrids $Hybrid \;1, Hybrid \;2, \ldots Hybrid \;N$ and prove

$Expt \;0 \approx_c Hybrid \;1$ assuming, say, one way functions.

$Hybrid \;i \approx_c Hybrid \;i+1$ assuming one way functions.

$Hybrid \;N \approx_c Expt \;1$ assuming one way functions.

If $N = poly(\lambda)$, then $Expt \;0 \approx_c Expt \;1$ assuming one way functions. How to apply complexity leveraging argument if $N = 2^\lambda$? (Here there are many reduction algorithms each running in poly time).

Answer 1

You would have to be very careful with this. First, complexity leveraging is not an ideal proof technique and requires non standard assumption. But let's put that aside and assume that you are happy with assuming exponentially hard one-way functions. You still have to make sure that you get a meaningful result. The way to do this is to be extremely explicit about the running time of the adversary in Hybrid i as a function of the adversary's running time in Hybrid i-1. Then, you would be able to say at the end what the running time of the final adversary is. You may get: if the original A in Expt0 runs in time $n^c$ then the final adversary runs in time $n^c + n^{\log n}$ (which would be reasonable), but you may get that the final adversary runs in time $2^{n^c}$ (which would be meaningless). So, it depends on the exact reduction and running times.

In addition to the above, you would need to do the same with the distinguishing probability. Here also, you have to be really careful. However, I can't say how much this makes a difference, since it would depend on the proof. One immediate thing is that you would need to assume that the distinguishing probability is not just non-negligible but way below $2^{-\lambda}$ and you have to think about how reasonable this is.