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