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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Maarten Bodewes May 26 '20 at 9:16
  • $\begingroup$ 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. $\endgroup$ – AleksanderRas May 26 '20 at 12:02
  • 1
    $\begingroup$ "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$. $\endgroup$ – poncho May 26 '20 at 20:05
  • $\begingroup$ @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!! $\endgroup$ – fgrieu May 26 '20 at 21:59
  • 1
    $\begingroup$ @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. $\endgroup$ – 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.)

All this is somewhat a matter of opinion, relating to prescriptivism versus descriptivism in language. The descriptivist argument is that words and phrases take on meanings when enough people say they do, so “security reduces to” is fine. But for precise technical and mathematical language, especially where the intended meaning could be one of two completely different things, I would lean toward prescriptivism, and “reduction”/“reduces to” already have established meanings that were inherited deliberately from complexity theory.

  • $\begingroup$ To clarify: I had initially no position on the question I asked, contrary to the different OP of the other question. Now I'm starting to lean at least towards "let's not use reduced in this way"; and perhaps "incorrect". I'll accept whatever I find the best answer in a few days. $\endgroup$ – fgrieu May 28 '20 at 12:09

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.