I was reading the definition of Fujisaki-Okamoto transform, and I found this:

enter image description here

What does it mean the "randomness space" of the function Enc in the PKE setting?


In general, if you're asking about a particular definition, it is good to include a link to the definition under question.

Generally though, it is known that PKE requires randomized encryption (or non-repeating nonces, I will ignore this). This is to say that (except for in specialty settings) the function:

$$\mathsf{Enc} : \mathcal{PK}\times\mathcal{M}\to\mathcal{C}$$

is a randomized algorithm (where $\mathcal{PK}$ is the space of all public keys). You can always [1] write a randomized algorithm as a deterministic algorithm that takes as input some random string, i.e. write:

$$\mathsf{Enc}^{det} : \mathcal{PK}\times\mathcal{M}\times\mathcal{R}\to\mathcal{C}$$

where $\mathsf{Enc}^{det}(pk, m;r)$ simulates the algorithm $\mathsf{Enc}(pk,m)$, and when the algorithm requests random bits, it uses the (fixed) string $r$ as a source of the "random" bits.

This is relevant for the FO transform, as it can be "factored" into two steps (the $T$-transform and $U$-transform, see this paper). The $T$-transform modifies $\mathsf{Enc}$ in two ways:

  1. Derandomization: Rather than using randomness $r$, one uses a random oracle $G$ to set $r := G(m)$, i.e. chooses $\mathsf{Enc}^{det}(pk,m) := \mathsf{Enc}(pk,m; G(m))$

  2. Re-encryption: Decryption is also modified, namely one checks that for $m'\gets\mathsf{Dec}(sk, c)$ the relation $c = \mathsf{Enc}^{det}(pk, m')$ holds. For this check to make sense, encryption must (of course) be deterministic.

Anyway, to be able to do the first step of the $T$-transform, one needs to know $\mathcal{R}$, as you need to be able to choose a random oracle $G : \mathcal{M}\to\mathcal{R}$. Typically $\mathcal{R}$ can be written of the form $\{0,1\}^k$ for some $k$ [2].

[1] There might be some pathologies here if the randomized algorithm has "expected polynomially" running time, rather than terminates in some polynomial running time. I'll ignore this, it's not relevant to encryption.

[2] Note that there are schemes for which you might worry that $\mathcal{R} \neq \{0,1\}^k$, or even $\mathcal{R} = \{0,1\}^k$ but the distribution of noise that $\mathsf{Enc}$ needs is not uniform over $\{0,1\}^k$. I am in particular thinking of lattice-based schemes, where the randomness is often "Gaussian like" (or say centered binomial), although this also happens for code-based schemes, where often the randomness has fixed hamming weight iirc. A random oracle will typically have output $G(m)$ that is uniformly random over $\{0,1\}$. This is no real issue though --- one can use a sampling algorithm $\mathsf{Samp} : \{0,1\}^k \to \mathcal{R}$ to convert the output of the random oracle to the desired distribution. This happens even for randomized encryption, where rather than using a RO for randomness the algorithm uses some form of system randomness (which is assumed to be computationally indistinguishable from uniform random bits).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.