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