6
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 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, 2020 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$
    – AleksanderCH
    May 26, 2020 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, 2020 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, 2020 at 21:59
  • 2
    $\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 Schultz-Wu ♦
    May 27, 2020 at 7:54

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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, 2020 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.