I have read some papers that give the definition of one-wayness of PKE schemes.

Let $\Pi = (G,E,D)$ be a PKE scheme, and the security game of OW-CPA is defined as follow:

$$\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(k) = \Pr\left[ m = m' \left\vert \begin{gathered} (pk,sk) \gets G(1^k) \\ m \gets \mathcal{M}_{k} \\ c \gets E_{pk}(m) \\ m' \gets \mathcal{A}(pk,c) \\ \end{gathered}\right.\right]$$

We say $\Pi$ is secure in the sense of OW-CPA if $\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(\cdot)$ is nelgibile.

My question is that how does the challenger choose $m$ over $\mathcal{M}_{k}$ randomly? Is $m$ an element picked uniformly from $M_{k}$?

If $\mathcal{M}_{k} = \mathcal{M} = \{0,1\}^*$, $m$ cannot be picked uniformly from $M_{k}$.

If $|\mathcal{M}_{k}| = \mathrm{poly}(k)$, then $\Pi$ cannot be secure in the sense of OW-CPA if $\mathcal{D}_{k}$ is uniform.

Let $F$ be the sample circuit, then $$\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(k) = \Pr\left[ m = m' \left\vert \begin{gathered} (pk,sk) \gets G(1^k) \\ m \gets F(\mathcal{M}_{k}) \\ c \gets E_{pk}(m) \\ m' \gets \mathcal{A}(pk,c) \\ \end{gathered}\right.\right]$$

Assume that the distribution of message is $\mathcal{D}_{k}$, thus $m$ follows $\mathcal{D}_{k}$. We cannot define that $\Pi$ is OW-CPA secure if for every distribution $\mathcal{D}_{k}$, $\mathrm{Adv}_{\Pi,\mathcal{A}}^{\text{ow-cpa}}(\cdot)$ is negligible, because it is not OW-CPA secure if $\mathcal{D}_{k}$ is a one-point distribution.

Perhaps, we may define the PKE scheme as $\Pi = (G,E,D,F)$ where the sample circuit $F$ is given at first. But the notion of IND-CPA or SS-CPA does not need $F$.

[FO99] Secure Integration of Asymmetric and Symmetric Encryption Schemes

[BF03] Identity-Based Encryption from the WeilPairing

[GH05] Security Notions for Identity Based Encryption

  • $\begingroup$ I would suppose that $\mathcal M_k$ is a message sampler, not a set. Usually the text leading up to this formula would introduce $\mathcal M_k$. $\endgroup$
    – SEJPM
    Commented Aug 19, 2019 at 18:10
  • $\begingroup$ @SEJPM, It is $c$, I have corrected it. It is OK if you regard $\mathcal{M}_{k}$ as a message sampler. As I know, IND-CPA implies OW-CPA. But the definition of IND-CPA does not need the message sampler. So, if there is an IND-CPA secure PKE scheme with a strange message sampler (e.g. the distribution is almost a one-point distribution), then it cannot be OW-CPA secure. $\endgroup$
    – Blanco
    Commented Aug 20, 2019 at 1:16
  • $\begingroup$ Are the references at the end papers that have this OW-CPA definition as well? $\endgroup$
    – SEJPM
    Commented Aug 21, 2019 at 15:37
  • $\begingroup$ @SEJPM [GH05] and [BF03] give the definitions of OW-ATK for IBE. The definitions come from [FO99]. The defintions make me confuse. I do not why does IND implie OW, whatever it is IBE or PKE. $\endgroup$
    – Blanco
    Commented Aug 22, 2019 at 4:51

1 Answer 1


Generally in cryptography papers, if a distribution is not specified, either it's uniform, or the results are essentially determined by characteristics of the distribution like its min-entropy.*

  • In the Fujisaki–Okamoto paper, $\mathtt{MSPC}_k$ (corresponding to $\mathcal M_k$) could be taken to be a set of cardinality $2^{\operatorname{poly}(k)}$ sampled uniformly at random, or it could be a more generally distribution itself with min-entropy $H_\infty = \operatorname{poly}(k)$. It's not clear from the paper but the results hold either way.

  • In the Galindo–Hasuo paper, the notation is explicitly defined as such in §2.

Obviously the upper bound on advantage is at least $2^{-H_\infty}$, or $1/\!\left|\mathcal M_k\right|$ in the uniform case.

It is true that OW-CPA (or ‘OW-Passive’ as some authors call it, because there's no oracle involved) does not imply IND-CPA—for example, the RSA trapdoor permutation $x \mapsto x^3 \bmod n$ has OW-CPA security but not IND-CPA security. This is why, e.g., RSAES-OAEP exists: to shoehorn a message $m$ from some nonuniform distribution into a nearly uniform random ‘message representative’ $x$.

(A simpler generic approach, of course, is to choose $x$ uniformly at random and then use $H(x)$ as a secret key for a symmetric authenticated cipher, as RSA-KEM does, and as is the modern paradigm for new cryptosystems like the NIST PQC submissions; this is what the Fujisaki–Okamoto paper is about.)

* This is a rule for readers, not for authors. Authors: Please say ‘uniform’ if that's what you mean!

  • $\begingroup$ I know that OW-CPA does not imply IND-CPA. I want to know why does IND-CPA imply OW-CPA. I have understood your answer. Can I say that $\text{IND-CPA} \Rightarrow \text{OW-CPA}$ means that for every IND-CPA secure PKE scheme, there exists a distribution of message space such it is OW-CPA secure? Actually, it holds true if the distribution is uniform enough. $\endgroup$
    – Blanco
    Commented Sep 9, 2019 at 16:03
  • $\begingroup$ I think (but haven't worked out and formalized and proven) that you can probably say: for every IND-CPA PKE scheme, for all distributions on messages with min-entropy $\varepsilon$, the OW-CPA advantage is bounded by $2^{-\varepsilon} + \mathit{negl}$. $\endgroup$ Commented Sep 10, 2019 at 0:21
  • $\begingroup$ Thanks, this conclusion can be the part of answer of my another question. crypto.stackexchange.com/questions/65905/…. The relation between two security notions depends on the size of plaintext space. $\endgroup$
    – Blanco
    Commented Sep 10, 2019 at 1:20

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.