I'm studying reductions in cryptography and confused about the way people use the word "reduction". My question is almost the same as a past question, but what I want to ask is slightly different.

A lot of papers or articles (e.g. Wikipedia "Reduction (complexity)" or "The Algebraic Group Model and its Applications" by Fuchsbauer et al.) say that a reduction $R$ from a problem $P$ to a problem $Q$ is an algorithm such that for every adversary against $Q$, $R$ uses it as a subroutine to solve $P$ correctly. In other words, if $P$ can be reduced to $Q$, $Q$ is "no less hard" than P.

In a security proof of a protocol $\Pi$, we often assume the hardness of a problem $P$. In this proof, for every adversary $\mathcal{A}$ against $\Pi$, we show that there is an adversary $\mathcal{B}$ against $P$ whose advantage is (essentially) no less than $\mathcal{A}$. I think this is a reduction from $P$ to $\Pi$ and this means $\Pi$ is no less hard than $P$. More formally, breaking $\Pi$ is no less hard than $P$ and since we assume $P$ is hard breaking $\Pi$ is hard.

However, some people say "the security of a protocol $\Pi$ can be reduced to the hardness of $P$" in this case. I think this is the wrong way of using the word "reduction" since we actually reduce $P$ to breaking $\Pi$. Others say "the security of a protocol $\Pi$ is based on the hardness of $P$", and I think this is true.

Am I right or wrong? Thanks in advance.

  • 1
    $\begingroup$ I made a shorter version of what I think the present question is. $\endgroup$ – fgrieu May 26 '20 at 7:12

You are (mostly) right. Reductions are an algorithmic notion — $P$ reduces to $Q$ if the ability to solve $Q$ allows you to solve $P$. There are many ways to formalize this, but the one that you describe (using $Q$ as a subroutine/oracle to solve $P$) is the most common in cryptography (it is known as a Turing reduction). I will notate this $P \leq Q$.

Note that reductions often have a little more detail than what you describe, specifically some bounds on the amount of resources that the reduction $R$ has access to. If $R$ is all powerful then "hard languages" reduce to "easy languages", because $R$ can just ignore the subroutine/oracle it has access to and solve the problem directly. This is seen as a boring formalization, so we generally want to force $R$ to be too weak to solve $P$ directly (having it be polynomial time is generally sufficient). This is mostly interesting when discussing properties of complexity classes under reductions though.

Now I'll quickly highlight that reductions are intrinsically about the existence of algorithms. $P \leq Q$ can be interpreted as saying:

If there exists an algorithm for $Q$, then there exists an algorithm for $P$

i.e. $P \leq Q$ can be parsed as the logical statement:

$$ \exists \text{ algorithm for }Q\implies \exists \text{ algorithm for }P$$

With this in mind, let us look at the sentence you highlight:

The security of a protocol $\Pi$ can be reduced to the hardness of $P$

What does it mean for a protocol to be secure? Normally "There doesn't exist an algorithm to break the protocol" (I will notate the problem of breaking the protocol $\Pi$ as $B_\Pi$. Similarly, what does it mean for a problem to be hard? "There doesn't exist an algorithm to solve the problem". Ignore the word "reduced" in the above sentence quickly. The goal of a reduction in cryptography is to prove "If the problem $P$ is hard, then the protocol $\Pi$ is secure", i.e. a statement of the form:

$$\not\exists\text{ algorithm for } P\implies \not\exists\text{ algorithm for }B_\Pi $$

This doesn't match up with our prior definition of reduction though. We can look at the contrapositive of the above statement to get the equivalent statement:

$$\exists\text{ algorithm for }B_\Pi\implies \exists\text{ algorithm for }P$$

This is then written as $P \leq B_\Pi$.

  1. Solving $P$ (complexity-theoretically) reduces to breaking the protocol $\Pi$

  2. The inability to solve $P$ (i.e. hardness) implies to the inability to break (security) $\Pi$

We could read this later statement as defining a "cryptographic reduction" $B_\Pi \leq_{cr} P$, where this stands for a statement of the form:

$$ \not\exists\text{ algorithm for }P\implies \not\exists\text{ algorithm for }B_\Pi$$

But then this would be fundamentally dual to the complexity-theoretic reduction, i.e. we would have that $P \leq B_\Pi$ and $B_\Pi \leq_{cr} P$. Under this notion of reduction the authors' statement becomes correct, but it is the "reverse" direction that we expect from complexity theory.

This is all to say that for "reduce" in the sense of complexity theory, what they write is technically incorrect (but can be trivially fixed by appealing to the contrapositive). This is such a basic step that it is quite common to do it implicitly, but to formalize things in terms of complexity-theoretic reductions there is an intermediate step which must be made explicit.

  • 1
    $\begingroup$ Thank you for your great explanation. I think I fully understand the point. $\endgroup$ – rapier May 26 '20 at 7:52
  • 1
    $\begingroup$ I am 99% sure that your explanation goes off the rails at the end. When we say "The security of $\Pi$ can be reduced to the hardness of $P$," we absolutely do not mean "Inability to break $\Pi$ implies inability to solve $P$." We absolutely do mean "Inability to solve $P$ implies inability to break $\Pi$." So there's nothing backwards about the notation; it's technically accurate. $\endgroup$ – Quuxplusone May 27 '20 at 6:22
  • 1
    $\begingroup$ @Quuxplusone Reductions (in complexity theory) are typically written as an implication between existentially quantified statements about algorithms. Cryptographers often implicitly view these via the contrapositive form to get universally quantified statements about (the inexistence) of algorithms. These forms are both logically equivalent, but are somehow "dual" to eachother. My point in the above was to clarify how they are different by centering the complexity-theoretic viewpoint (as it is the original notion, and has seen more independent research into itself i.e. structural complexity). $\endgroup$ – Mark May 27 '20 at 7:10
  • 1
    $\begingroup$ @quetzalcoatl This is the point of the answer. "Reduce" in the first case means the statement $\not \exists P\implies \not \exists B_\Pi$. Both "security" and "hardness" are not statements about the existence of algorithms (which is how reductions are defined within complexity theory), but about the inexistence of algorithms. Taking contrapositives, we have this is equivalent to $\exists B_\Pi\implies \exists P$, and therefore $P\leq B_\Pi$. Again, you could choose to define "reduction" to mean implications between universally quantified statements about algorithms, but then the ... $\endgroup$ – Mark May 27 '20 at 7:19
  • 1
    $\begingroup$ complexity-theoretic notion would be "backwards". As either choice leaves the other "backwards", and the complexity theoretic notion both came initially, and is generally fleshed out a bit better (the literature on "the complexity-theoretic notion of reduction" is broader), it seems better to have this be the "initial definition". And sorry, is late here, I flipped things around in my most recent comment. $P \leq B_\Pi$ should be correct, the statement $\exists$ algo to break $B_\Pi\implies \exists$ algo to solve hard problem is correct fundamental notion. $\endgroup$ – Mark May 27 '20 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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