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.

$\endgroup$

1 Answer 1

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

$\endgroup$
5
  • $\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 Schultz-Wu
    Feb 6, 2023 at 9:33
  • $\begingroup$ Fair point, would you like to write up an answer? I'll delete this one. $\endgroup$
    – ckamath
    Feb 6, 2023 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 Schultz-Wu
    Feb 6, 2023 at 17:56
  • 1
    $\begingroup$ The notion you suggested is quite natural. (Amended the answer.) $\endgroup$
    – ckamath
    Feb 6, 2023 at 18:26
  • $\begingroup$ Maybe these papers be useful:[ Hofheinz-Jia-Pan-Asiacrypt2018], [ Langrehr-Pan-PKC2020] which they also emphasize on considering multi-challenge security definition rather than single challenge when dealing with tight security reductions. $\endgroup$ Mar 31 at 13:16

Your Answer

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

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