2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Chris Peikert May 4 at 20:29
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – securitymensch Apr 4 at 19:10
  • $\begingroup$ 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. $\endgroup$ – kelalaka Apr 4 at 19:21
  • $\begingroup$ 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? $\endgroup$ – securitymensch Apr 4 at 19:24
  • $\begingroup$ 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. $\endgroup$ – kelalaka Apr 4 at 19:47

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.