Meaning of "Security can be reduced to a problem"

Question

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.

Answer 1

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.