11
$\begingroup$

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.

Thank you in advance.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Mark
    Feb 6 at 9:33
  • $\begingroup$ Fair point, would you like to write up an answer? I'll delete this one. $\endgroup$
    – ckamath
    Feb 6 at 11:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark
    Feb 6 at 17:56
  • 1
    $\begingroup$ The notion you suggested is quite natural. (Amended the answer.) $\endgroup$
    – ckamath
    Feb 6 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.