Induction is problematic in computational cryptography - Why? In Dr. Lindell's lecture The Yao Construction and its Proof Of Security, in briefly explaining the hybrid argument, he makes the statement that mathematical induction is a problem in computational cryptography. He is explaining that a hybrid argument is "like" mathematical induction, but not the same.

As far as I know, mathematical induction and hybrid arguments are not the same because for a hybrid argument, you need a finite ($k$) sequence of distributions for the proof to work (that is, eventually bounding the sum of the $k$ negligible differences by the max difference * $k$, which is negligible). For an infinite sequence, this doesn't work.

Does anyone know what Dr. Lindell means? I have a suspicion that it's a deeper point related to computability, but I'm not sure.

Thanks!
The problem with induction is what it typically hides. I'll give an example. Assume that I want to prove that $n$ samples of $X$ is indistinguishable to $n$ samples of $Y$, assuming that a single sample is indistinguishable. Instead of doing a hybrid argument, I prove by induction. The base case is immediate, since a single sample is indistinguishable by assumption. Next, I assume for $i$ and prove for $i+1$. In this claim, I prove that for every PPT adversary $\cal A_{i+1}$ who can distinguish $i+1$ samples with non-negligible probability, there exists a PPT adversary $\cal A_i$ who can distinguish $i$ samples with non-negligible probability (or a distinguisher who can distinguish a single sample, but let's leave that for now). It seems that this suffices for the proof to go through.

However, what happens if $\cal A_i$ runs in twice the time than $\cal A_{i+1}$ (this is of course fine since they are both polynomial time)? Then, when I "unwind" the induction, I will get the following. Assume that there exists a probabilistic polynomial-time adversary $\cal A_n$ who distinguishes $n$ samples with non-negligible probability; let $p(n)$ be its running time. Then, by applying the inductive argument repeatedly, I obtain that there exists an adversary $\cal A_1$ who distinguishes a single sample, but runs in time $2^n\cdot p(n)$, thereby contradicting nothing.

Another problem that can happen is as follows. Assume that our proof of the inductive step is such that $\cal A_{i+1}$ distinguishes with non-negligible probability $\epsilon(n)$ and as a result $\cal A_i$ distinguishes with non-negligible probability $\epsilon(n)/2$. This is of course fine since both probabilities are still non-negligible. However, when we unwind the induction, if $\cal A_n$ distinguishes with non-negligible probability $\epsilon$, we will have that $\cal A_1$ distinguishes with probability $\epsilon/2^n$ which is negligible. Thus, no contradiction is achieved.

In order to overcome this, one can prove explicitly in the inductive step that the running time difference between $\cal A_{i+1}$ and $\cal A_i$ is additive, meaning that there is an additional polynomial factor only. Then, over $n$ (or any polynomial) steps of the induction, the additional running time overall is still polynomial. Likewise, if there is a reduction in the distinguishing probability, then the result at the end is still non-negligible.

I have used induction once in a paper; see pages 22-23 of http://u.cs.biu.ac.il/~lindell/PAPERS/session-key.ps, so it can be done. But one must be careful.

(A note: all of the above I learned from Oded Goldreich.)