What does 'a reduction is tight' mean rigorously?

Lee Seungwoo

2/6/24, 6:03 AM

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.

419

1 + 0

security-definition

reduction

Score:4

Crypto

ckamath

2/6/24, 7:43 AM

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

+ 4

Mark

2/6/24, 9:33 AM

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](https://eprint.iacr.org/2018/077) for details.

ckamath

2/6/24, 11:58 AM

Fair point, would you like to write up an answer? I'll delete this one.

Mark

2/6/24, 5:56 PM

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.

ckamath

2/6/24, 6:26 PM

The notion you suggested is quite natural. (Amended the answer.)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: What does 'a reduction is tight' mean rigorously?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.