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

Question

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

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!}