# Proof by reduction definition in “Serious Cryptography”: Cipher reduced to hardness problem or other way around?

In Serious Cryptography by Jean-Philippe Aumasson on p. 46, paragraph "Provable Security", it says:

Provable security is about proving that breaking your crypto scheme is at least as hard as solving another problem known to be hard. [...] This type of proof is called a reduction [...]. We say that breaking some cipher is reducible to problem $$X$$ if any method to solve problem $$X$$ also yields a method to break the cipher.

I am wondering if this is the right direction. Assume we reduce the problem of breaking a cipher $$P$$ to some problem $$X$$, $$P \leq_m^p X$$, as suggested by the book (if I understand correctly). Then if we have a polynomial-time algorithm for $$X$$, we also have a polynomial algorithm for $$P$$. But this does not guarantee that if no polynomial algorithm for $$X$$ exists, there should be no polynomial-time algorithm for breaking $$P$$. In fact, there could still be a polynomial-time algorithm breaking $$P$$ in some way unrelated to problem $$X$$.

So shouldn't the reduction be the other way around $$X \leq_m^p P$$. That is, if we can break $$P$$ in polynomial time, we can also solve $$X$$ in polynomial time? This way, if $$X$$ is hard (not polynomial-time solvable), then by contraposition $$P$$ must also be hard, thus $$P$$ is at least as hard as X?

What am I missing here?

• In brief, your understanding of all this is correct; you aren’t missing anything. To show that “breaking your crypto scheme P is at least as hard as solving some other problem X,” you would need to give a reduction from X to P, i.e., show $X \leq P$. In words, show that any algorithm for solving P can be used (efficiently) to solve X. – Chris Peikert May 4 at 20:29

The definitions come from Turing Reduction of Wikipedia

In computability theory, a Turing reduction (also known as a Cook reduction) from a problem A to a problem B, is a reduction which solves A, assuming the solution to B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B. More formally, a Turing reduction is a function computable by an oracle machine with an oracle for B. Turing reductions can be applied to both decision problems and function problems.

which can be simplified as $$A$$ is reduced to $$B$$;

• If $$A \leq B$$ then, if you were given a subroutine for $$B$$ you could solve $$A$$.
• This can be also mean that $$A$$ is no harder than $$B$$.

I am wondering if this is the right direction. Assume we reduce the problem of breaking a cipher $$P$$ to some problem $$X$$, $$P \leq_m^p X$$, as suggested by the book (if I understand correctly). Then if we have a polynomial-time algorithm for $$X$$, we also have a polynomial algorithm for $$P$$. But this does not guarantee that if no polynomial algorithm for $$X$$ exists, there should be no polynomial-time algorithm for breaking $$P$$. In fact, there could still be a polynomial-time algorithm breaking $$P$$ in some way unrelated to problem $$X$$.

So we have $$P \leq X$$, which means we use $$X$$ as a subroutine and $$P$$ is not harder than $$X$$.

Yes, the reduction doesn't say about a polynomial-time algorithm exists or not. If one can prove that there is no polynomial-time algorithm for $$X$$ than this doesn't mean that there is no for $$P$$. Because the reduction is just a useful upper bound.

If there is a polynomial-time algorithm for $$P$$ this can be used to solve $$X$$ if one can show that $$X \leq P$$. Otherwise, as stated in the second bullet, the reduction provides only the upper bound.

So shouldn't the reduction be the other way around $$X \leq_m^p P$$. That is, if we can break $$P$$ in polynomial time, we can also solve $$X$$ in polynomial time?

Not exactly, the reduction gives the upper bound. To use a polynomial-time algorithm for $$P$$ to solve $$X$$ one needs to show that $$X \leq P$$.

This way, if $$X$$ is hard (not polynomial-time solvable), then by contraposition $$P$$ must also be hard, thus $$P$$ is at least as hard as X? What am I missing here?

Assuming that one showed a reduction of $$X \leq P$$, then the information we have $$X$$ is no harder than $$P$$ with $$P$$ is solvable in polynomial-time. If you show that $$X$$ is hard ( assuming NP-hard here) then one must look at either the reduction or the hardness of solving $$P$$ again.

• Could you elaborate on the upper bound? So after showing $P \leq X$, we have shown an upper bound for what? About $X \leq P$: I thought that if we show $X \leq P$ and $X$ is say, NP-hard, then $P$ is also NP-hard (by contraposition). Therefore, if we want to show that $P$ is at least as hard as $X$, we need to show $X \leq P$? – securitymensch Apr 4 at 19:10
• With the reduction $P \leq X$, $X$ stands for an upper bound for $P$. $P$ cannot be harder than $X$. One can always use $X$ to solve $P$. If you one show that $X \leq P$ then $P$ is upper bound for $X$, i.e. $X$ cannot be harder than $P$. If you consider the $P$ as polynomial time than there is problem with the reducetion or the NP-hardness or the polynomial-timeness of P. – kelalaka Apr 4 at 19:21
• So if we assume $X$ is a hard problem (discrete logarithm for example) and we create a new cipher on that and let $P$ be the problem of breaking that cipher. Than to show "breaking your crypto scheme (=P) is at least as hard as solving another problem known to be hard (=X)" we need to reduce $X \leq P$, right? – securitymensch Apr 4 at 19:24
• If you provide a reduction for $X \leq P$ then you showed that if you can break $P$ then you can break $X$. If you also show that $P \leq X$ we can consider them like equal complexity classes. – kelalaka Apr 4 at 19:47