# How does the challenger choose the message randomly in the one-wayness security game of PKE?

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

• 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$. – SEJPM Aug 19 '19 at 18:10
• @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. – TeamBright Aug 20 '19 at 1:16
• Are the references at the end papers that have this OW-CPA definition as well? – SEJPM Aug 21 '19 at 15:37
• @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. – TeamBright Aug 22 '19 at 4:51

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!

• 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. – TeamBright Sep 9 '19 at 16:03
• 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}$. – Squeamish Ossifrage Sep 10 '19 at 0:21
• 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. – TeamBright Sep 10 '19 at 1:20