# “Reduced to” vs “deduced from”

Assume it's proven: "Security of protocol $$\Pi$$ can be deduced from hardness of problem $$P$$".

Is it correct to state: "Security of protocol $$\Pi$$ can be reduced to (hardness of) problem $$P$$" ?

My question is about accepted VOCABULARY in the field of cryptography with provable security.

This is a simplified version of this question, where the first of the above assertions is (I assume, rigorously) established by exhibiting an algorithm that would solve problem $$P$$ from an algorithm that would break protocol $$\Pi$$. I read two interesting answers (which I thus upvoted) concluding for one that that reduced "cannot (technically)" be used in this way but remains understandable in the context, for the other that it's "appropriate".

For a non-native speaker like me, that's far from trivial.

• I have the feeling that they are the same but for the fact that you work upwards from $P$ to $\Pi$ in for deduction and downwards from $\Pi$ to $P$ for reduction. But that's not enough of a mathematical definition to be useful as an answer. – Maarten Bodewes May 26 '20 at 9:16
• I think it means that the security of $\Pi$ (which could be a broad protocol) is based on the hardness of problem $P$ and thus the entire security of the protocol can be reduced to the key aspect which is the problem $P$. Solve $P$ and $\Pi$ falls. – AleksanderRas May 26 '20 at 12:02
• "by exhibiting an algorithm that would break protocol $\Pi$ from an algorithm that would solve problem $P$"; actually, it's the other way around; you show that if you have a method to break protocol $\Pi$, you can use that as a blackbox to solve instances of problem $P$ (hence, if you believe problem $P$ is hard, so is protocol $\Pi$). The way you stated doesn't exclude the possibility of breaking protocol $\Pi$ without solving problem $P$. – poncho May 26 '20 at 20:05
• @poncho: oh! Huge mistake of mine, that is not in the original question!! Fixed,hopefully. At least I can pretend it was clear in my head. Thanks for the correction!! – fgrieu May 26 '20 at 21:59
• @fgrieu I've updated my answer to the prior question. I think there are two competing notion of reduction --- complexity theoretic reductions (about implications $\exists A\implies \exists B$, written $B \leq A$) and cryptographic reductions (about implications $\not\exists A\implies \not \exists B$, written $B \leq_{cr} A$). One then gets that $B \leq A\iff A \leq_{cr} B$ by contrapositive. If one disambiguates between these then everything seems fine, which is what all authors do implicitly. So it is mostly a stumbling block if people read "reduce" without this implicit understanding. – Mark May 27 '20 at 7:54

I think you are right (in the other question): “security of protocol $$P$$ reduces to assumption $$X$$” is incorrect (or at best too sloppy) language, and has too much potential for confusion. This is both because the intended “direction” of the reduction is not completely clear (does breaking $$P$$ imply breaking $$X$$, or the other way around?), and a reduction is supposed to be from one computational problem to another (but “security of $$P$$” is not a problem).
Saying “security of $$P$$ is based on assumption $$X$$” is fine, and is more naturally phrased than “breaking $$X$$ reduces to breaking $$P$$.” Though it is perhaps not entirely explicit that there is a formal reduction, because a few authors might say this even without a reduction. (But I think they would be wrong to do so.)