# Proofs by reduction and times of adversaries

I have some difficulties to understand, when we construct a reduction, how we determine the time for the constructed adversary to break a target security property.

In general these details are not explained in books.

Do you have some examples in which the time $t$ for the adversary $A$ is not equal to $t'$, the time for the constructed adversary $A'$ to break something supposed secure?

Is the time very important?
Why are the resources given to the adversary not sufficient to describe a security reduction?

-

Reductionist security

In a reductionist security proof for some cryptographic protocol $\Pi$ to some alleged hard problem $P$ means, that we can build an algorithm $\cal B$ for solving $P$ if we have access to a hypothetical algorithm $\cal A$ that efficiently breaks the security definition for the protocol $\Pi$.

In general, showing a polynomial time reduction only shows asymptotical equivalence of the problems. In practice-oriented security (or concrete security) for reductionist security proofs, one wants to relate the running times of the hypothetical adversary against a protocol $\Pi$ with the running time of the concrete reduction. This may then be seen as showing "practical equivalence".

Tight vs. non-tight reductions

Let the adversary, i.e., the algorithm $\cal A$, take time $t$ and win with probability $\epsilon$ in the security game of $\Pi$ and say we can use $\cal A$ to build an algorithm $\cal B$ to solve $P$ and $\cal B$ runs in time $t'$ and wins with probability $\epsilon'$.

Then, we are interested in tight reductions, i.e., that $t\approx t'$ and $\epsilon\approx \epsilon'$. If $\cal B$ takes much longer, i.e., $t'>>t$, and has much lower success probability, i.e., $\epsilon'<<\epsilon$, then the reduction is called non-tight (which is not desirable).

Why not?

If the reduction is tight (and we assume that the security definition of $\Pi$ is meaningful - which is important, as otherwise even a tight security proof may be meaningless for practical applications of the protocol), then we know that breaking the protocol $\Pi$ is at least as hard as solving the alleged hard problem $P$. And then, we know that when we take the security parameter for the protocol as the current status indicates, then we are secure.

If on the other hand the reduction is not tight, then we only have the assurance that the protocol $\Pi$ requires at least as much effort as a certain fraction of what we think it requires to break $P$, e.g., breaking RSA, since it takes much less time to break the protocol $\Pi$ than it takes for the reduction to the problem to work. Now, this means that we may have to take a much larger security parameter for the protocol to still achieve reasonable security.

If we increase the security parameter, we consider the gap that is introduced between the adversary and the reduction and we need to choose them in a way that we can guarantee security of the protocol relative to the concrete reduction.

Why is this a problem?

We have to take larger security parameters, which makes the schemes typically more inefficient. Secondly, and that is what the advocates of concrete security criticise is that often a paper may not indicate that the security reduction is non-tight and thus someone implementing the protocol may choose the security parameters as if the reduction were tight. Consequently, the so implemented protocol may be (highly) insecure in practice.

A brief example

For instance, the original reduction for the RSA-FDH (RSA full domain hash) signature scheme is not tight. It bounds the probability $\epsilon$ of breaking RSA-FDH in time $t$ by $\epsilon'\cdot q_H$, where $\epsilon'$ is the probability of inverting RSA in time $t′ \approx t$ and $q_H$ is the number of hash queries made by the adversary $\cal A$. Consequently, the reduction looses a factor of $q_H$. Now, assume that you want to have a security level of 80 bits and you assume that $\cal A$ can make $2^{60}$ queries, then one should use a security parameter for the signature scheme such that inverting the RSA function cannot be achieved in fewer than $2^{60}\cdot 2^{80}=2^{140}$ operations. If one takes the ECRYPT recommendations for key sizes for instance, 80 bit security is equivalent to 1248 bit for the RSA modulus. This would apply if the reduction would be tight. However, the reduction is non-tight and one would actually require a modulus size of about 4000 bits.

Choosing the security parameter for the scheme according to the reduction (in the example 4000 bit) we can be sure that we can cope with an adversary in practice (in the example against 1248 bit RSA). Basically, we have an idea how hard it is to break RSA today and then we need to adjust the security parameter accordingly.

-
There is a tighter reduction for RSA-FDH here: iacr.org/archive/crypto2000/18800229/18800229.pdf –  curious Feb 11 '14 at 22:09
@curious I took the original reduction for RSA-FDH since the OP asked for an example and I wanted to make that point of a non-tight reduction explicit (and I wrote - the original reduction ;) Actually, there is even a newer result from EUROCRYPT 2012. –  DrLecter Feb 11 '14 at 22:12
Thank you very much for this long answer. I have question, in the sentence \texbf{why not ?}, why do you write "at least as much effort \texbf{as a certain fraction} of what we think it requires to break P, e.g., breaking RSA." Why a certain fraction ? Since $t' >> t$, if $t$ and $t'$ are the efforts, it seems that $t'$ is not a fraction of $t$... –  Dingo13 Feb 11 '14 at 22:28
@DrLecter If we increase the security parameter, we obtain $t$ closer to $t'$ and $\epsilon$ closer to $\epsilon'$ ? Is this true ? When you say "the reduction does not work in all cases the adversary works", you speak about better adversaries ? –  Dingo13 Feb 11 '14 at 22:44
@Dingo13 I edited the anwer. I will add more if I find some time to do so. –  DrLecter Feb 12 '14 at 11:27