# What does 'a reduction is tight' mean rigorously?

As far as I know, when someone says 'a reduction is tight', it means that given that there is an adversary $$A$$ with advantage $$\epsilon$$ and running time $$t$$ and another adversary $$B$$ utilizing $$A$$ to solve a problem $$P$$, the advantage and running time of $$B$$ are apporximated to those of $$A$$.

But here is my question:

When do we say $$\epsilon ' \approx \epsilon$$ and $$t' \approx t$$ exactly? Is there any specific criterion? (e.g. $$\epsilon' \approx \epsilon \Leftrightarrow |\epsilon ' - \epsilon| \leq negl$$, or something else).

I cannot find rigorous mathematical definitions about reduction tightness.

The usual way to measure the tightness of a reduction (e.g., see [CMS]) is via the tightness gap, defined as $$\frac{t'}{\epsilon'}\big/\frac{t}{\epsilon}=\frac{t'\epsilon}{t\epsilon'}.$$ A reduction is then said to be tight if the tightness gap is $$O(1)$$ (ideally a small explicit constant).$$^*$$

However, as @Mark points out in the comments, [MW] argues that the above may not be the right measure when it comes to reductions involving decision problems/primitives (you can read more about why in the paper).

$$^*$$However, small polynomials are also considered tolerable.

[CMS]: Chatterjee, Menezes and Sarkar, Another Look at Tightness, SAC 2011.

[MW]: Micciancio and Walter, On the Bit Security of Cryptographic Primitives, EC 2018

• Note that if you define the bit security of a (search) problem as $\kappa = \log_2 \frac{t}{\epsilon}$, this condition is simply that the bit securities $\kappa' - \kappa$ are close (within a constant factor). I mention the bit security formulation as the quantity $\frac{t}{\epsilon}$ is arguably the incorrect quantity to investigate for decision problems/primitives, see on the bit security of cryptographic primitives for details.
– Mark
Feb 6 at 9:33
• Fair point, would you like to write up an answer? I'll delete this one. Feb 6 at 11:58
• no your answer is good --- I don't know if what I've suggested can be found in the literature (this notion of tightness is not found in the paper I linked), and this question is asking for a reference request. Still, it might be a good pointer to complement your reference.
– Mark
Feb 6 at 17:56
• The notion you suggested is quite natural. (Amended the answer.) Feb 6 at 18:26