Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm reading the paper OAEP 3-round, where they introduce a 3-round version of the OAEP (which originally used only two rounds). However, in their security statement for this construction (Theorem 4 and 5 in their paper) I'm quite confused by the direction of their logical implications.

Let $\operatorname{Succ}^{\mathrm{one-way}}_f(\tau')$ denote the maximal probability over all adversaries $\mathcal{A'}$ trying to break the one-wayness of the trapdoor-permutation $f$. Then the statement that stumps me is the following (I'm leaving out a lot of details which are inessential to my question):

Assume that after $\langle \dots \rangle$ queries to its oracles, the IND-CCA adversary $\mathcal{A}$ has advantage $\operatorname{Adv}^{\mathrm{ind-cca}}_{\mathrm{oaep-3}}(\tau)$ greater than $\epsilon$, then $\operatorname{Succ}^{\text{one-way}}_f(\tau)$ is upper-bounded by $\langle \dots \rangle$.

Shouldn't it be greater than $\Rightarrow$ lower-bounded?

Usually statements like these are written in the contrapositive form so that we bound the advantage of breaking the scheme directly by the advantage of breaking the underlying problem: "If the advantage of breaking this underlying problem is smaller than $\beta$, then the advantage of breaking the encryption scheme is bounded by some expression in $\beta$". But in this form the above statement would equate to something similar to the nonsensical statement: "If $\operatorname{Succ}^{\text{one-way}}_f(\tau)$ is greater than $\epsilon'$, then there exists adversaries against the scheme such that $\operatorname{Adv}^{\mathrm{ind-cca}}_{\mathrm{oaep-3}}(\tau)$ is smaller than $\langle \dots \rangle$".

What am I missing? This formulation is repeated in both Theorem 4 and 5, so is probably not a typo.

share|improve this question
Did you try reading and understanding the proof? –  David Cash Oct 30 '13 at 18:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.