# Security of Encryption Schemes in Weakened Random Oracle Models

 Security of Encryption Schemes in Weakened Random Oracle Models Security of Encryption Schemes in Weakened Random Oracle Models Authors Akinori Kawachi, Akira Numayama, Keisuke Tanaka and Keita Xagawa Published 2010 г. Web site Public Key Cryptography 2010 Download Original paper
Abstract. Liskov proposed several weakened versions of the random oracle model, called weakened random oracle models (WROMs), to capture the vulnerability of ideal compression functions, which are expected to have the standard security of hash functions, i.e., collision resistance, second-preimage resistance, and onewayness properties. The WROMs offer additional oracles to break such properties of the random oracle. In this paper, we investigate whether public-key encryption schemes in the random oracle model essentially require the standard security of hash functions by the WROMs. In particular, we deal with four WROMs associated with the standard security of hash functions; the standard, collision tractable, second-preimage tractable, first-preimage tractable ones (ROM, CT-ROM, SPT-ROM, and FPT-ROM, respectively), done by Numayama et al. for digital signature schemes in the WROMs. We obtain the following results: The OAEP is secure in all the four models. The encryption schemes obtained by the Fujisaki-Okamoto conversion (FO) are secure in the SPT-ROM. However, some encryption schemes with FO are insecure in the FPT-ROM. We consider two artificial variants wFO and dFO of FO for separation of the WROMs in the context of encryption schemes. The encryption schemes with wFO (dFO, respectively) are secure in the CT-ROM (ROM, respectively). However, some encryption schemes obtained by wFO (dFO, respectively) are insecure in the SPT-ROM (CT-ROM, respectively). These results imply that standard encryption schemes such as the OAEP and FO-based one do not always require the standard security of hash functions. Moreover, in order to make our security proofs complete, we construct an efficient sampling algorithm for the binomial distribution with exponentially large parameters, which was left open in Numayama et al.’s paper.
Keywords: public-key encryption schemes, weakened random oracle models, OAEP, Fujisaki-Okamoto conversion.


## Introduction

Background: In order to design new cryptographic schemes, we often follow the random oracle methodology [1]. First, we analyze the security of cryptographic schemes, by idealizing hash functions as truly random functions called the random oracle. When it comes to implementations of these schemes, we replace the random oracles by cryptographic hash functions such as MD5 [2] and SHA-1 [3]. This replacement is called an instantiation of the random oracle.

The random oracle methodology causes a trade-off between efficiency and provable security. The schemes proven secure in the random oracle model (ROM) are in general more efficient than those proven secure in the standard model. However, the security proofs in the ROM do not directly guarantee the security in the standard model, i.e., an instantiation of the random oracle might make the cryptographic schemes insecure. Even worse, several recent works [4] [5] [6] showed that some schemes secure in the ROM have no secure instantiation.

There are several properties of the ROM to prove the security of cryptographic properties. In particular, the ROM is expected to satisfy the one-wayness, second-preimage resistance, and collision resistance properties. We call these properties as the standard security of hash functions. These properties are indeed critical in many schemes for their security proofs. For example, the security of the Full-Domain-Hash (FDH) signature schemes (e.g., [7]), which are secure in the ROM, relies on the collision-resistance property of the ROM. That is, if we can obtain two distinct messages ${\displaystyle m,m^{'}}$ such that ${\displaystyle H(m)=H(m^{'})}$ and the signature ${\displaystyle \sigma =Sig(H(m))}$, then we can obtain a valid forgery ${\displaystyle (m^{'},\sigma )}$, where ${\displaystyle H}$ is a hash function and ${\displaystyle Sig}$ is a signing algorithm. Leurent and Nguyen also presented the attacks extracting the secret keys on several hash-then-sign type signature schemes and identity-based encryption schemes if the underlying hash functions are not collision resistant [8].

Recent progress on the attacks against cryptographic hash functions such as MD5 and SHA-1 raises the question on the assumption that hash functions are collision resistant and one-way (e.g.,[9] [10] [11]). Therefore, it is significant to investigate whether the collision resistance property (as well as the one-wayness and second-preimage resistance properties, which are weaker notions than the collision resistance one) of the ROM is essential to prove the security of the schemes or not. More generally, it is worth classifying the schemes by the first-preimage, second-preimage, and collision resistance properties of the ROM that their security essentially requires.

Weak versions of random oracle models: Several works recently highlighted some specific properties of the ROM for secure cryptographic constructions in the ROM.

Nielsen proposed the non-programmable random oracle model where the random oracle is not programmable [12]. In this model, one cannot set the values that the random oracle answers to some convenient values. It was showed in [12] that a noninteractive non-committing encryption scheme exists in the ROM (assuming that trapdoor permutations exists), but not in the non-programmable random oracle model.

Unruh proposed a ROM with oracle-dependent auxiliary inputs [13]. In this setting, adversaries obtain an auxiliary input that contains information with respect to the random oracle (e.g. collisions). He showed that the RSA-OAEP encryption scheme [14] is secure in the ROM even under the presence of oracle-dependent auxiliary inputs.

Liskov proposed several weakened versions of the random oracle model, called weakened random oracle models (WROMs), which offer additional oracles to break some properties of the random oracle [15]. These model captures the situation that adversaries are given an attack algorithm for breaking some specific property of the functions. For example, the first-preimage tractable random oracle model offers the random oracle and the first-preimage oracle associated with the random oracle, which returns a first-preimage of the random oracle to adversaries. This first-preimage oracle then corresponds to the attack to the first preimage property of a hash function. We can replace the additional oracle to others such as the second-preimage and collision ones that correspond to the attack to the properties. Thus, the WROMs can capture vulnerability of hash functions even if the parties are allowed to utilize ideal ones as in the ROM. By using WROMs, Liskov constructed hash functions based on weak ideal compression functions and proved it is indifferentiable from the random oracle.

Several results already analyzed the security in the WROMs. Hoch and Shamir applied Liskov’s idea to prove the indifferentiability of another hash construction [16]. Pasini and Vaudenay also applied Liskov’s idea to the security analysis of digital signature schemes [17]. They considered the security of hash-then-sign type signature schemes in the first-preimage tractable random oracle model. Numayama, Isshiki, and Tanaka formalized the WROMs, which allows us to formally analyze the security of the schemes [18]. By using these models, they classified several digital signature schemes by the properties of the ROM. Fischlin and Lehmann also proposed a weakened random oracle model in a similar way to Liskov’s one in the context of secure combiners [19].

Our contributions: In this paper, we investigate whether public-key encryption schemes constructed in the ROM essentially require the standard security of hash functions by further extending the direction originated from Liskov. In particular, we consider their security in the standard, collision tractable, second-preimage tractable, and firstpreimage tractable random oracle models (ROM, CT-ROM, SPT-ROM, and FPT-ROM, respectively for short). Note that they are ordered according to their strengths, i.e., the security of encryption schemes in the FPT-ROM implies that in the SPT-ROM and such implications hold between each adjacent two models.

We demonstrate that the security notions in the four WROMs can be strictly separated in the context of encryption schemes. For the separation, we focus on the security of the encryption schemes obtained by the Fujisaki-Okamoto conversion (FO) [20], its two artificial variants (dFO and wFO), and the OAEP [14]. Precisely, we prove the following four statements:

1. OAEP is IND-CCA2 secure in the FPT-ROM.
2. FO is IND-CCA2 secure in the SPT-ROM, but not IND-CPA secure in the FPT-ROM.
3. wFO is IND-CCA2 secure in the CT-ROM, but not IND-CCA2 secure in the SPT-ROM.
4. dFO is IND-CCA2 secure in the ROM, but not IND-CCA2 secure in the CT-ROM.


We summarize the security of four schemes in Table 1.

Table 1. Security of four schemes
scheme/model
ROM CT-ROM SPT-ROM FPT-ROM
OAEP secure
FO secure insecure
wFO secure insecure
dFO secure insecure

This separation suggests that some public-key encryption schemes essentially require the standard security of hash functions. These notions were also separated in the context of digital signature schemes in [18]. We stress that the role of the collision and second-preimage oracles in encryption schemes is not as clear as that in digital signature schemes. For example, it is easy to see that the collision oracle, breaking the collision resistance property of the random oracle, directly makes a simple scheme vulnerable, but not so easy for the case of encryption schemes. Actually, we need to develop new proof techniques for the (in)security of encryption schemes under additional oracles.

It also suggests that standard encryption schemes such as the OAEP and FO-based ones do not always require the standard security of hash functions for the random oracle. We believe that our results do not only give an example of the first application of the WROMs to encryption schemes, but they are also of independent interest. As far as we know, our results give the first evidence that the OAEP encryption scheme can be used in a practical application even without the first-preimage resistance property, i.e., the one-wayness property. In other words, the OAEP remains secure even if we remove the first-preimage resistance property. This can also be said on FO-based encryption schemes on the second-preimage resistance property.

On the security of the OAEP, Kiltz and Pietrzak recently showed that there is no construction for padding-based encryption schemes including the OAEP that has a black-box reduction from ideal trapdoor permutations to its IND-CCA2 security in [21]. However, they wrote in the paper that the security proof in the ROM can be still a valid argument in practice. We believe so is our security proof in the WROMs.

For the security proof, we explicitly show how to sample approximately in polynomial time from binomial distributions with exponentially large parameters, that is, a polynomial-time sampling algorithm whose output distribution is statistically close to the binomial distribution. For this algorithm, we arrange and combine sampling algorithms that run over real numbers proposed in the field of statistics [22] [23] [24] [25], and give a precise analysis for discretization.

It should be noted that on the security proofs of the digital signature schemes in the WROMs [18], Numayama et al. assumed such an efficient sampling algorithm and thus gave no explicit construction. They left the construction of the sampling algorithm as an open problem. By the sampling algorithm we explicitly show, it is no longer necessary to assume the sampling algorithm in their security proofs of the digital signature schemes [18] as well as those of the public-key encryption scheme in this paper.

The sampling algorithm shown in this paper is adapted for cryptographic use since the statistical closeness to the original distribution is measured by the total variation distance, which is standard in cryptography but not usually required in statistics. The sampling algorithm is useful for other cryptographic tasks as in Numayama et al.’s and this paper.

Comparisons with other models: As mentioned above, a few models that weaken the power of the random oracle were already proposed such as the non-programmable model [12] and the oracle-dependent auxiliary input model [13].

The non-programmable model is not simply comparable with WROMs since the programmability does not imply the collision resistance and vice versa. The target of the oracle-dependent auxiliary input model partially overlaps that of the WROMs.

For a simple comparison, we now focus on the security of the OAEP in both models. Unruh showed a similar result as ours for the OAEP encryption scheme [13]. He proposed a random oracle model where oracle-dependent auxiliary inputs are allowed. In his setting, the adversary of some cryptographic protocol obtains an auxiliary input that contains the information (e.g., collisions) on the random oracle. He showed that the OAEP encryption scheme [14] is still secure in the random oracle model even in his model. This result indicates an important fact that the security of the OAEP encryption scheme does not depend on the collision resistance property since the oracle-dependent auxiliary input can contain a sufficiently long list of collisions.

Our results also present the security of the OAEP in a weak version of the random oracle. However, there are at least two differences between Unruh’s result and ours. First, the random oracle model with the oracle-dependent auxiliary input does not completely capture the adaptive security of hash functions, and this model still has the second-preimage resistance and the first-preimage resistance properties. Hence, only by his result, we cannot say whether these two properties are necessary or not in order to prove the security of the OAEP encryption scheme. In contrast to Unruh’s result, our result clearly shows that the two adaptive securities of hash functions such as the firstpreimage resistance and the second-preimage resistance are not necessary to prove the security of the OAEP encryption scheme.

Second, Unruh constructed the reduction algorithm which breaks the partial-domain one-wayness of the underlying trapdoor permutation using the adversary which breaks the IND-CCA2 security of the OAEP encryption scheme. The running time of the reduction algorithm is not bounded by any polynomial. Therefore, he use the security amplification technique for the partial-domain one-wayness. By using this technique, he can avoid employing a stronger assumption that even quasi-polynomial time adversary cannot break the partial-domain one-wayness, and can prove the security under the standard partial-domain one-wayness against polynomial-time adversary.

In contrast to Unruh’s result, we construct the polynomial-time reduction algorithm using the adversary, and hence we do not require the security amplification technique for the partial-domain one-wayness, which can be considered as a simplification of Unruh’s proof.

Organization: In Section 2, we describe the details of the WROMs and their properties. We also discuss the simulation methods that are applicable to these models. In Section 3, after reviewing the encryption schemes we consider, we show their (in)security in the WROMs. Many technical details will be omitted from this extended abstract. We will describe them in the full version [26].

Notation: Before starting technical parts of this paper, we introduce our notation used in the rest of the paper. For a table ${\displaystyle \mathbb {T} ={(x,y)}}$, we define ${\displaystyle \mathbb {T} (y)={(x^{'},y^{'})\in \mathbb {T} \mid y^{'}=y}}$. For a distribution ${\displaystyle D,x\leftarrow D}$ denotes that ${\displaystyle x}$ is sampled according to ${\displaystyle D}$. The function ${\displaystyle D(x)}$ stands for the probability function of the distribution ${\displaystyle D}$.

Let ${\displaystyle s\leftarrow S}$ denote that s is sampled from the uniform distribution over a finite set ${\displaystyle S}$ . ${\displaystyle \#S}$ denotes the number of elements in ${\displaystyle S}$. For a probabilistic Turing machine ${\displaystyle {\mathcal {A}}}$ and its input ${\displaystyle x}$, let ${\displaystyle {\mathcal {A}}(x)}$ denote the output distribution of ${\displaystyle {\mathcal {A}}}$ on input ${\displaystyle x}$.

We usually denote by ${\displaystyle k}$ a security parameter of a cryptographic scheme in this paper. We also denote by ${\displaystyle k^{'}}$ length of plaintexts unless it is specified. ${\displaystyle k^{'}}$ is implicitly assumed to be polynomially related to the security parameter ${\displaystyle k}$ , that is, ${\displaystyle k^{'}=k^{\Theta }}$ . We say a function ${\displaystyle f(k)}$ is negligible in ${\displaystyle k}$ if ${\displaystyle f(k)\leq 2^{-\omega (\log k)}}$ . For two distributions ${\displaystyle D_{1}}$ and ${\displaystyle D_{2}}$ over a finte set ${\displaystyle S}$ , we denote the statistical distance (the total variation distance) between them by ${\displaystyle \vartriangle (D_{1},D_{2})}$ , defined by ${\displaystyle {\frac {1}{2}}\Sigma _{s\in S}\mid D_{1}(s)-D_{2}(s)\mid }$ . We say two distributions ${\displaystyle D_{1}}$ and ${\displaystyle D_{2}}$ are statistically close if ${\displaystyle \vartriangle (D_{1},D_{2})\leq 2^{-\omega (\log k)}}$ .

## The Weakened Random Oracle Models

In this section, we first review the definitions of the WROMs. Next, we present an important property called weak uniformity of the WROMs, which is useful for security proofs of encryption schemes. We also discuss the simulation methods of [18] used for the security proofs in the WROMs.

### Definitions of the Weakened Random Oracle Models

To give formal definitions of the WROMs, we define some notation. Let ${\displaystyle X}$ and ${\displaystyle Y}$ be finite sets. Let ${\displaystyle H}$ be a hash function chosen randomly from all of the functions from ${\displaystyle X}$ to ${\displaystyle Y}$ . We denote by ${\displaystyle \mathbb {T} _{H}}$ the table ${\displaystyle \{(x,H(x)\mid x\in X\}}$ . We identify the hash function ${\displaystyle H}$ with the table ${\displaystyle \mathbb {T} _{H}}$ .

We next define the random oracle and the additional oracles associated with ${\displaystyle H\colon X\rightarrow Y}$ as follows. (For more details, see [18].)

Random oracle ${\displaystyle {\mathcal {R}}{\mathcal {O}}^{H}}$: Given ${\displaystyle x}$ , return ${\displaystyle y}$ such that ${\displaystyle (x,y)\in \mathbb {T} _{H}}$ .

Collision oracle ${\displaystyle {\mathcal {C}}{\mathcal {O}}^{H}}$: On the query, first pick one entry ${\displaystyle (x,y)\in \mathbb {T} _{H}}$ uniformly at random. If there is no other entry ${\displaystyle (x^{'},y)\in \mathbb {T} _{H}}$ , then answer ${\displaystyle \bot }$ .
Otherwise, pick one entry ${\displaystyle (x^{'},y)\in \mathbb {T} _{H}}$ satisfying ${\displaystyle x\neq x^{'}}$ uniformly at random and answer ${\displaystyle (x,x^{'})}$ .

Second-preimage oracle ${\displaystyle {\mathcal {S}}{\mathcal {P}}{\mathcal {O}}^{H}}$: Given ${\displaystyle (x,y)}$ , if ${\displaystyle (x,y)\notin \mathbb {T} _{H}}$ answer ${\displaystyle \bot }$ . If there is no other entry ${\displaystyle (x^{'},y)\in \mathbb {T} _{H}}$ , then answer ${\displaystyle \bot }$ .
Otherwise, pick one entry ${\displaystyle (x^{'},y)\in \mathbb {T} _{H}}$ satisfying ${\displaystyle x\neq x^{'}}$ uniformly at random and answer ${\displaystyle x^{'}}$ .

First-preimage oracle ${\displaystyle {\mathcal {F}}{\mathcal {P}}{\mathcal {O}}^{H}}$: Given  ${\displaystyle y}$ , if there is any entry ${\displaystyle (x,y)\in \mathbb {T} _{H}}$ then return such an  ${\displaystyle x}$ uniformly at random. Otherwise return ${\displaystyle \bot }$.

Remark 1. We usually identify the random oracle and the underlying hash function.
However, in this paper as in [18], we explicitly distinguish them by regarding the random oracle as an interface to the underlying hash function.
This setting helps us to make the WROMs with an additional oracle well-defined.


The formal definitions of the WROMs are given as follows. The WROMs consist of three components, a hash function ${\displaystyle h}$ chosen randomly from all of the functions from ${\displaystyle X}$ to ${\displaystyle Y}$ , the random oracle, and the additional oracle associated with ${\displaystyle h}$ . The models are called the CT-ROM, SPT-ROM, and FPT-ROM, if the additional oracle is the collision, second-preimage, and first-preimage oracle, respectively.

Remark 2. The collision oracle may output ${\displaystyle \bot }$ even if there exists a collision ${\displaystyle (x,x^{'})}$ in the table.
This stems from the simulation method of Numayama et al. [18], and causes no serious problems.
Note that the collision oracle outputs ${\displaystyle \bot }$ with probability ${\displaystyle (1-1/\#Y)^{\#X-1}}$ . In the case where ${\displaystyle \#X\geq \#Y}$ ,
we can find a collision with polynomially many queries since since ${\displaystyle (1-1/\#Y)^{\#X-1}\leq exp(-(\#X-1)/\#Y)}$.
In the case where ${\displaystyle \#Y=k^{O(1)}*\#X}$ , we can again find a collision with polynomially many queries ${\displaystyle (1-1/\#Y)^{\#X-1}\leq 1-1/k^{O(1)}}$ .
Finally, in the case where ${\displaystyle \#Y=k^{\omega (1)}*\#X}$ , the following lemma shows that there are no collisions with overwhelming probability.

Lemma 1. Let ${\displaystyle H\colon X\rightarrow Y}$ be the hash function, and ${\displaystyle n_{y}}$ the number of preimages of ${\displaystyle y}$ under the function ${\displaystyle H}$ , that is, ${\displaystyle n_{y}=\#\mathbb {T} _{H}(y)}$ .
Let BAD denote the event that there is some ${\displaystyle y}$ such that ${\displaystyle n_{y}>L}$ . Then for all sufficiently large ${\displaystyle Y}$, we have ${\displaystyle Pr_{H}[BAD]<{\dfrac {1}{(\#Y)^{2}}}}$ ,
where ${\displaystyle L={\dfrac {5\ln {\#Y\#X}}{\ln {\ln {\#Y\#Y}}}}}$ if ${\displaystyle \#X\geq \#Y}$ , or ${\displaystyle L={\dfrac {5\ln {\#Y}}{\ln {\ln {\#Y}}}}}$ otherwise.


The proof is obtained by the standard argument on the balls and bins game by regarding ${\displaystyle X}$ and ${\displaystyle Y}$ as sets of balls and bins, respectively. For the details on the game, see a standard textbook (e.g., [27]).

### Difference from the Random Oracle Model

We observe an important difference between the ROM and WROMs by considering the ROM and FPT-ROM. In the both models, the function ${\displaystyle H}$ , i.e., the table ${\displaystyle \mathbb {T} _{H}}$ is uniformly distributed. In the ROM, if one queries some ${\displaystyle x}$ that has never been queried to the random oracle, the value of ${\displaystyle H(x)}$ is uniformly distributed regardless of the past queries. That is, the knowledge of the past queries does not affect the entries not queried in the table. This property of the ROM is called uniformity. In contrast to the situation in the ROM, when it comes to the FPT-ROM, this property is not attained. Recall that the first-preimage oracle uniformly returns one of the preimages, say ${\displaystyle x}$ , of queried value ${\displaystyle y}$ . If the firstpreimage oracle leaks a number of preimages of ${\displaystyle y}$ , the value of ${\displaystyle H(x)}$ is not uniformly distributed for an ${\displaystyle x}$ not queried yet.

In order to observe this situation, let us consider the following extreme case. Let ${\displaystyle y^{*}=H(x^{*})}$ for some ${\displaystyle x^{*}\in X}$ and suppose that ${\displaystyle y^{*}}$ has the unique preimage ${\displaystyle x^{*}}$ . Then the first-preimage oracle always returns the same ${\displaystyle x^{*}}$ on the input ${\displaystyle y^{*}}$ , which convinces us that the number of the preimages of ${\displaystyle y^{*}}$ is exactly ${\displaystyle 1}$. This implies that the other ${\displaystyle x\neq x^{*}}$ does not take a value ${\displaystyle y^{*}}$ under ${\displaystyle H}$. Therefore, the random oracle no longer has the uniformity in the FPT-ROM. This is a critical difference between the ROM and FPT-ROM since we often make use of the uniformity in the security proofs of the public-key encryption schemes.

We prove the following lemma to overcome this barrier in the WROMs, which states that the WROMs still has weak uniformity instead of the uniformity. The weak uniformity is still useful for the security proofs of the public-key encryption schemes in the WROMs.

Lemma 2 (Weak Uniformity). In the WROMs, the output distribution of the random oracle is statistically close to the uniform distribution.
More formally, it is stated as follows. Let ${\displaystyle H\colon X\rightarrow Y}$ be the hash function in the WROMs.
Let  ${\displaystyle {\mathcal {A}}}$ be a probabilistic oracle Turing machine that makes at most ${\displaystyle q}$ queries to the random oracle ${\displaystyle {\mathcal {R}}{\mathcal {O}}^{H}}$ and the additional oracle ${\displaystyle {\mathcal {O}}^{H}}$,
where ${\displaystyle {\mathcal {O}}^{H}}$ represents one of the additional oracles ${\displaystyle {\mathcal {C}}{\mathcal {O}}^{H}}$ , ${\displaystyle {\mathcal {S}}{\mathcal {P}}{\mathcal {O}}^{H}}$ , and ${\displaystyle {\mathcal {F}}{\mathcal {P}}{\mathcal {O}}^{H}}$ . ${\displaystyle {\mathcal {V}}_{{\mathcal {A}},{\mathcal {H}}}(x)}$ denotes the random variable that represents the hash value ${\displaystyle {\mathcal {R}}{\mathcal {O}}^{H}(x)}$ ,
where ${\displaystyle x\leftarrow {\mathcal {A}}^{{\mathcal {R}}{\mathcal {O}}^{H},{\mathcal {O}}^{H}}}$ and the correspondence ${\displaystyle (x,H(x))\in \mathbb {T} _{H}}$ is not answered by the two oracles.
Then, for any ${\displaystyle {\mathcal {A}}}$ , the following holds:


${\displaystyle \vartriangle (V_{{\mathcal {A}},{\mathcal {H}}}(x),U_{Y})\leq {\begin{cases}{\frac {1}{\#Y}}(5q+1+{\frac {4q^{2}}{\#Y}}+20q{\frac {ln{\#Y}}{ln{ln{\#Y}}}}),&{\mbox{if }}\#X\geq \#Y\\{\frac {1}{\#X}}(5q+1+{\frac {4q^{2}}{\#X}}+20q{\frac {ln{\#Y}}{ln{ln{\#Y}}}}),&{\mbox{if }}\#X<\#Y\end{cases}}}$

Here, the probability is taken over random choices of the hash function ${\displaystyle H}$ and therandom coin of ${\displaystyle {\mathcal {A}}}$ .


### Simulation Methods

In almost all the security proofs in the ROM, the reduction algorithms simulate the random oracles. When it comes to the security proofs in the WROMs, the reduction algorithms have to simulate both the random and the additional oracle, which makes differences of the simulation methods in the WROMs from those in the ROM.

Numayama et al.’s methods: Numayama et al. proposed the simulation methods for WROMs, but they required an unproven assumption. Let ${\displaystyle B_{N,p}}$ denote the binomial distribution with parameters ${\displaystyle N}$ and ${\displaystyle p}$ whose probability function is ${\displaystyle B_{N,p}(x)={\binom {N}{x}}p^{x}(1-p)^{N-x}}$ for ${\displaystyle x=0,...,N}$ , where the parameters ${\displaystyle N}$ and ${\displaystyle p}$ take values approximately ${\displaystyle \#X}$ and ${\displaystyle 1/\#Y}$ for a hash function ${\displaystyle H\colon X\rightarrow Y}$ , say, ${\displaystyle (N,p)=(2^{128},2^{-128})}$ . Their simulation methods required the efficient sampler for ${\displaystyle B_{N,p}}$ with exponentially large ${\displaystyle N}$ and small ${\displaystyle p}$, and they assumed its existence.

Assumption 1. There is a probabilistic Turing machine ${\displaystyle B_{N}}$ such that the output distribution ${\displaystyle B_{N}(N,p)}$ on inputs ${\displaystyle N}$ and ${\displaystyle p}$ is equal to the
binomial distribution ${\displaystyle B_{N,p}}$ and it runs in polynomial time in ${\displaystyle \log N}$ and ${\displaystyle \log p^{-1}}$ , where ${\displaystyle N}$ is a positive integer and ${\displaystyle 0\leq p\leq 1}$ is a rational number.


Under this assumption, they constructed the simulation algorithms, RO, CO, SPO, and FPO, for the security proofs in the WROMs as given in the following proposition. See [18] for the details of the algorithms.

Proposition 1 (Simulation Method [18]). We can perfectly simulate the random oracle, the collision oracle, second-preimage oracle,
and first-preimage oracle in the WROMs under Assumption 1. That is, the output distributions of the random oracle, collision oracle, second-preimage oracle,
and first-preimage oracle in the WROMs are identical to the output distributions of the algorithms RO, CO, SPO, and FPO, under Assumption 1.


Removing the assumption: For the security proof in the WROMs of digital signature schemes in [18] and encryption schemes in this paper, it is sufficient to utilize a weaker sampling algorithm that generates a distribution not equal but statistically close to the binomial distribution ${\displaystyle B_{N,p}}$. Then, their security proofs can work by just adding negligibly small errors induced by the statistical distance in their analyses.

There are quite many papers (e.g., [25]) on the efficient sampling methods from the binomial distribution in the field of statistics. However, their basic computation model is totally different from the model in the cryptography. As far as the authors’ knowledge, all these results are based on the computation model that directly manipulates real numbers without errors. If we translate them to those in the bit computation model used in the cryptography, we have to bound the statistical distance between the real distribution and the output distribution generated by the sampling algorithms in the bit computation model rather than the real-number one. Numayama et al. mentioned that they could neither find precise analyses of the statistical distance, nor construct the sampling algorithms by themselves in [18]. Therefore, they had to put the above assumption.

In fact, there is an efficient sampling algorithm appropriate for our purpose in the real-number computation model [25]. We modify the algorithm and rigorously analyze the error bound in the bit computation model. We can finally obtain the following theorem on the sampling algorithm.

Theorem 1. There is a probabilistic Turing machine ${\displaystyle B_{N}}$ such that, for the output distribution ${\displaystyle B_{N}(N,p,\epsilon )}$ on inputs ${\displaystyle N,p}$ and ${\displaystyle \epsilon }$ ,
the statistical distance between ${\displaystyle B_{N}(N,p,\epsilon )}$ and ${\displaystyle B_{N,p}}$  is at most ${\displaystyle \epsilon }$ and it runs in polynomial time in ${\displaystyle \log N,\log p^{-1}}$ and ${\displaystyle \log \epsilon ^{-1}}$ ,
where ${\displaystyle N}$ is a positive integer and ${\displaystyle 0\leq p\leq 1,0\leq \epsilon \leq 1}$ are rational numbers.


Note that the algorithm can control the error parameter ${\displaystyle \epsilon }$ . This property is useful in cryptographic applications for the security proofs even if the other parameters ${\displaystyle N}$ and ${\displaystyle p}$ are not sufficiently large. We will put the details of the algorithm and its analysis in the full version.

As a result, we can remove the above assumption and obtain the following theorem.

Theorem 2 (Simulation Method without Assumption 1). We can statistically simulate the random oracle, collision oracle, second-preimage oracle,
and first-preimage oracle in the WROMs. That is, the output distributions of the oracles in the WROMs are statistically close to the output distributions
of the algorithms RO, CO, SPO, and FPO, respectively.


## The Encryption Schemes and Their Security in the Weakened Random Oracle Models

In this section, we examine the security in the WROMs of the public-key encryption schemes.We particularly discuss separations for notions of ROM, CT-ROM, SPT-ROM, and FPT-ROM by showing (in)security of public-key encryption schemes obtained by the Fujisaki-Okamoto conversion (FO) and its two variants (dFO and wFO), and OAEP.

Public-key encryption schemes: We first give notation and notions for public-key encryption schemes briefly. For details, see standard textbooks, e.g., [28].

A public-key encryption scheme ${\displaystyle PKE=(Gen,Enc,Dec)}$ over a plaintext space ${\displaystyle M}$ and a random coin space ${\displaystyle R}$ is defined by the following three algorithms. Let ${\displaystyle k}$ denote the security parameter.

Key Generation: On input ${\displaystyle 1^{k}}$, the key generation algorithm ${\displaystyle Gen(1^{k})}$ produces a public/secret key pair ${\displaystyle (pk,sk)}$ .

Encryption: Given a public key ${\displaystyle pk}$ , a plaintext ${\displaystyle m\in M}$, and a random string ${\displaystyle r\in R}$ , the encryption algorithm ${\displaystyle Enc_{pk}(m;r)}$
outputs a ciphertext c corresponding to the plaintext ${\displaystyle m}$.

Decryption: Given a secret key ${\displaystyle sk}$ and ciphertext ${\displaystyle c}$ , the decryption algorithm ${\displaystyle Dec_{sk}(c)}$ outputs the plaintext ${\displaystyle m\in M}$ or
the special symbol ${\displaystyle \bot \notin M}$ corresponding to the ciphertext ${\displaystyle c}$.


We require the perfect completeness, that is, for every ${\displaystyle (pk,sk)}$ generated by ${\displaystyle Gen(1^{k})}$ , every plaintext ${\displaystyle m\in M}$ , and every random string ${\displaystyle r\in R}$ , it should be satisfied that ${\displaystyle Dec_{sk}(Enc_{pk}(m;r))=m}$

We only consider three standard security notions for public-key encryption schemes, the one-wayness against chosen-plaintext attack (OW-CPA), the indistinguishability against chosen-plaintext attack (IND-CPA), and the indistinguishability against adaptive chosen-ciphertext attack (IND-CCA2).

For ${\displaystyle \gamma =\gamma (k)}$ , we say ${\displaystyle PKE}$ is ${\displaystyle \gamma }$-uniform if for any key pair ${\displaystyle (pk,sk)}$ generated by ${\displaystyle Gen(1^{k})}$ , any ${\displaystyle m\in M}$ , and ${\displaystyle c\in \{0,1\}^{*}}$ , we have ${\displaystyle Pr_{r\leftarrow R}[c=Enc_{pk}(m;r)]\leq \gamma }$ . There exists a OW-CPA public-key encryption scheme with ${\displaystyle \gamma }$-uniformity (e.g., the ElGamal encryption scheme).

Brief review for FO: Fujisaki and Okamoto proposed a conversion, called the Fujisaki-Okamoto (FO) conversion, to obtain highly secure public-key encryption schemes in the ROM [20]. Since the standard one-time pad satisfies the requirement of the FO conversion, we fix the one-time pad as the symmetric-key encryption scheme used in the FO conversion for simplicity.

Let ${\displaystyle PKE}$ be a OW-CPA secure and ${\displaystyle \gamma }$-uniform public-key encryption scheme over a plaintext space ${\displaystyle M}$ and a randomness space ${\displaystyle R}$ . Then the FO conversion converts ${\displaystyle PKE}$ to an IND-CCA2 secure one ${\displaystyle PKE^{'}=FO(PKE)}$ over a plaintext space ${\displaystyle M^{'}=\{0,1\}^{k^{'}}}$ and a randomness space ${\displaystyle R^{'}=M}$ , where ${\displaystyle k^{'}}$ denotes the length of plaintexts, which is polynomially related to the security parameter ${\displaystyle k}$ . The encryption procedure of ${\displaystyle PKE^{'}}$ is given as follows: For a plaintext ${\displaystyle m\in M^{'}=\{0,1\}^{k^{'}}}$ and a random string ${\displaystyle r\in R^{'}=M}$ , the ciphertext is

${\displaystyle (c_{1},c_{2})=(Enc_{pk}(r;H(m,r)),G(r)\oplus m)}$ ,

where ${\displaystyle H\colon \{0,1\}^{k^{'}}\times M\rightarrow R}$ and ${\displaystyle G\colon M\rightarrow \{0,1\}^{k^{'}}}$ are hash functions modeled as the random oracles. The decryption procedure is given as follows: For a given ciphertext ${\displaystyle (c_{1},c_{2})}$ , decrypt ${\displaystyle c_{1}}$ by ${\displaystyle sk}$ and obtain ${\displaystyle r}$ . Then, extract ${\displaystyle m}$ by ${\displaystyle c_{2}\oplus G(r)}$ and verify ${\displaystyle c_{1}=Enc_{pk}(r;H(m,r))}$ . If not output ${\displaystyle \perp }$ . Roughly speaking, ${\displaystyle H(m,r)}$ ensures that if a ciphertext ${\displaystyle (c_{1},c_{2})}$ is valid then the encryptor producing ${\displaystyle (c_{1},c_{2})}$ knows corresponding ${\displaystyle m}$ and ${\displaystyle r}$ .

### The First Variant dFO

We introduce the first artificial variant dFO and show that dFO is secure in the ROM, but not secure in general in the CT-ROM.

The variant dFO converts a public-key encryption scheme ${\displaystyle PKE}$ (with the one-time pad) to another public-key encryption scheme ${\displaystyle PKE^{'}=dFO(PKE)}$ similarly to FO. The encryption procedure of ${\displaystyle PKE^{'}}$ is defined as follows. For a plaintext ${\displaystyle m\in M^{'}=\{0,1\}^{k^{'}}}$ and a random string ${\displaystyle r\in R^{'}=M}$ , the ciphertext of ${\displaystyle PKE^{'}}$ is

${\displaystyle (c_{1},c_{2})=(Enc_{pk}(r;H(F(m),r)),G(r)\oplus m)}$ ,

where ${\displaystyle F\colon \{0,1\}^{k^{'}}\rightarrow P,G\colon M\rightarrow \{0,1\}^{k^{'}}}$ , and ${\displaystyle H\colon P\times \rightarrow R}$ , for an appropriate set ${\displaystyle P}$ , are hash functions modeled as the random oracle.

The idea to weaken the conversion is summarized as follows: Recall that ${\displaystyle H(m,r)}$ in the FO conversion can be considered as encryptor’s signature (or a proof of knowledge) on ${\displaystyle m}$ and ${\displaystyle r}$. To make it vulnerable by a collision, we introduce a new random oracle ${\displaystyle F}$ and replace ${\displaystyle H(m,r)}$ with ${\displaystyle H(F(m),r)}$ . The replacement does not harm the security in the random oracle model, while it can be exploited by the presence of the collision oracle COF.

Formally, we have following theorems on the (in)security. We omit the proof of Theorem 3, which is similar to the original one.

Theorem 3. Assume that ${\displaystyle PKE}$ is a OW-CPA secure and ${\displaystyle \gamma }$-uniform public-key encryption scheme for some negligible ${\displaystyle \gamma }$.
Then, ${\displaystyle PKE^{'}=dFO(PKE)}$ is IND-CCA2 secure in the ROM if ${\displaystyle \#P=2^{\omega (\log k)}}$.

Theorem 4. Let ${\displaystyle PKE}$ be a public-key encryption scheme. If ${\displaystyle \#P\leq 2^{k^{'}}}$ then ${\displaystyle PKE^{'}=dFO(PKE)}$ is not IND-CCA2 secure in the CT-ROM.


Proof. We construct the adversary ${\displaystyle {\mathcal {A}}=(A_{1},A_{2})}$ that breaks the IND-CCA2 security of ${\displaystyle PKE^{'}}$ , which exploits the collision oracle ${\displaystyle {\mathcal {C}}{\mathcal {O}}^{F}}$ of ${\displaystyle F}$ .

The adversary ${\displaystyle A_{1}}$, on input ${\displaystyle pk}$ , first queries to ${\displaystyle {\mathcal {C}}{\mathcal {O}}^{F}}$ . If the answer is ${\displaystyle \perp }$ , then the adversary flips a random fair coin ${\displaystyle b^{'}}$ , outputs ${\displaystyle b^{'}}$ , and halts. Otherwise, it obtains a collision ${\displaystyle (m_{1},m_{2})}$ of ${\displaystyle F}$ and outputs it as a challenge. The adversary ${\displaystyle A_{2}}$ receives the target ciphertext ${\displaystyle (c_{1}^{*},c_{2}^{*})=(Enc_{pk}(r;H(F(m_{b}),r)),G(r)\oplus m_{b})}$ for some ${\displaystyle r\in {\mathcal {R}}^{'}}$ . It queries ${\displaystyle (c_{1}^{'},c_{2}^{'})=(c_{1}^{*},c_{2}^{*}\oplus m_{0}\oplus m_{1})}$ to the decryption oracle and obtains ${\displaystyle m_{1-b}}$ , since

${\displaystyle c_{1}^{'}=Enc_{pk}(r;H(F(m_{0}),r))=Enc_{pk}(r;H(F(m_{1}),r))}$ ,

${\displaystyle c_{2}^{'}=G(r)\oplus m_{b}\oplus m_{0}\oplus m_{1}=G(r)\oplus m_{1-b}}$ .

Hence, the adversary can answer ${\displaystyle b^{'}=b}$ correctly.

Finally, we upper-bound the probability that the collision oracle outputs ${\displaystyle \perp }$ , which stems from the definition of the collision oracle. The probability is bounded by ${\displaystyle (1-1/\#P)^{2^{k^{'}}-1}\leq exp(-(2^{k^{'}}-1)/\#P)\leq 1/{\sqrt {e}}}$ . This completes the proof.

### The Second Variant wFO

We next introduce the second artificial variant wFO and show that the obtained scheme by wFO is secure in the CT-ROM, however not generally secure in the SPT-ROM.

The encryption procedure of ${\displaystyle PKE^{'}=wFO(PKE)}$ is given as follows. For a plaintext ${\displaystyle m\in M^{'}=\{0,1\}^{k^{'}}}$ and random strings ${\displaystyle (r,s)\in R^{'}=M\times S}$ , the ciphertext of ${\displaystyle PKE^{'}}$ is

${\displaystyle (c_{1},c_{2},c_{3})=(Enc_{pk}(r;H(F(m,s),r)),G(r)\oplus m,s)}$ ,

where ${\displaystyle F\colon \{0,1\}^{k^{'}}\times S\rightarrow P,G\colon M\rightarrow \{0,1\}^{k^{'}}}$, and ${\displaystyle H\colon P\times M\rightarrow R}$ are hash functions modeled as the random oracles.

Notice that ${\displaystyle (H(F(m,s),r),s)}$ is a proof of knowledge on ${\displaystyle (m,r,s)}$ which resists a collision on ${\displaystyle F}$ however is vulnerable by a second-preimage attack against ${\displaystyle F}$ as in Numayama et al. [18].

We can show that the obtained scheme is IND-CCA2 secure in the CT-ROM by using Lemma 2.

Theorem 5. Suppose that ${\displaystyle PKE}$ is a OW-CPA secure and ${\displaystyle \gamma }$-uniform public-key encryption scheme for some negligible ${\displaystyle \gamma }$.
Then, ${\displaystyle PKE^{'}=wFO(PKE)}$ is IND-CCA2 secure in the CT-ROM if ${\displaystyle \#P^{-1}}$ and ${\displaystyle \#S^{-1}}$ are negligible in ${\displaystyle k}$.


However, its security is broken under the presence of the second-preimage oracle for ${\displaystyle F}$.

Theorem 6. Let ${\displaystyle PKE}$ be a public-key encryption. If ${\displaystyle \#P\leq 2^{k^{'}}\cdot \#S}$, then the scheme
${\displaystyle PKE^{'}=wFO(PKE)}$ is not IND-CCA2 secure in the SPT-ROM.


Proof. We construct the adversary ${\displaystyle A=(A_{1},A_{2})}$ that exploits the second-preimage oracle ${\displaystyle SPO^{F}}$ associated to ${\displaystyle F}$ . The adversary ${\displaystyle A_{1}}$ chooses random distinct plaintexts ${\displaystyle m_{0}}$ and ${\displaystyle m_{1}}$ and queries them to the challenger. The challenger responses

${\displaystyle (c_{1}^{*},c_{2}^{*},c_{3}^{*})=(Enc_{pk}(r;H(F(m_{b},s),r)),G(r)\oplus m_{b},s)}$ .

Receiving ${\displaystyle (c_{1}^{*},c_{2}^{*},c_{3}^{*})}$ , the adversary ${\displaystyle A_{2}}$ queries ${\displaystyle (m_{0},s)}$ to the second-preimage oracle ${\displaystyle SPO^{F}}$. If it receives ${\displaystyle \perp }$ from the second-preimage oracle, then it flips a random fair coin ${\displaystyle b^{'}}$ , outputs ${\displaystyle b^{'}}$ , and halts. Otherwise, it obtains ${\displaystyle (m^{'},s^{'})\neq (m_{0},s)}$ such that ${\displaystyle F(m_{0},s)=F(m^{'},s^{'})}$ . So, the adversary queries

${\displaystyle (c_{1}^{'},c_{2}^{'},c_{3}^{'})=(c_{1}^{*},c_{2}^{*}\oplus m_{0}\oplus m^{'},s^{'})}$

to the decryption oracle. Notice that, if ${\displaystyle (c_{1}^{*},c_{2}^{*},c_{3}^{*})}$ is the valid ciphertext of ${\displaystyle m_{0}}$ , then we have

${\displaystyle c_{1}^{'}=Enc_{pk}(r;H(F(m_{0},s),r))=Enc_{pk}(r;H(F(m^{'},s^{'}),r))}$,

${\displaystyle c_{2}^{'}=G(r)\oplus m_{0}\oplus m_{0}\oplus m^{'}=G(r)\oplus m^{'}}$ ,

${\displaystyle c_{3}^{'}=s^{'}}$ ,

and ${\displaystyle (c_{1}^{'},c_{2}^{'},c_{3}^{'})}$ is a valid ciphertext for ${\displaystyle m^{'}}$. On the other hand, if the ciphertext is the encryption of ${\displaystyle m_{1}}$ , we have

${\displaystyle (c_{1}^{'},c_{2}^{'},c_{3}^{'})=(Enc_{pk}(r;H(F(m_{1},s),r)),G(r)\oplus m_{1}\oplus m_{0}\oplus m^{'},s^{'})}$ .

Thus, if ${\displaystyle f=F(m_{1},s)}$ is equal to ${\displaystyle F(m_{1}\oplus m_{0}\oplus m^{'},s^{'})}$ the decryption oracle returns ${\displaystyle m_{1}\oplus m_{0}\oplus m^{'}(\neq m^{'})}$. Otherwise, the decryption oracle returns ${\displaystyle \perp }$ .

Thus, if the answer is ${\displaystyle m^{'}}$ , then the adversary concludes that ${\displaystyle (c_{1}^{*},c_{2}^{*},c_{3}^{*})}$ is the ciphertext of ${\displaystyle m_{0}}$, that is, it outputs ${\displaystyle b^{'}=0}$ . Otherwise, the adversary concludes that it is the ciphertext of ${\displaystyle m_{1}}$ , that is, it outputs ${\displaystyle b^{'}=1}$ . Therefore, ${\displaystyle A}$ can output the correct answer unless ${\displaystyle A}$ receives ${\displaystyle \perp }$ from the second-preimage oracle.

We finally bound the probability that the oracle outputs ${\displaystyle \perp }$ . It is bounded by ${\displaystyle (1-1/\#P)^{2^{k^{'}}*\#S-1}\leq exp(-(2^{k^{'}}*\#S-1)/\#P)\leq 1/{\sqrt {e}}}$ as required. This completes the proof.

### The Original Fujisaki-Okamoto Conversion

We next show that the obtained scheme by the conversion FO with the one-time pad is secure in the SPT-ROM, but not secure in the FPT-ROM in some parameter setting.

Let ${\displaystyle G\colon M\rightarrow \{0,1\}^{k^{'}}}$ and ${\displaystyle H\colon \{0,1\}^{k^{'}}\times M\rightarrow R}$ be hash functions modeled as the random oracles. Recall the encryption procedure of ${\displaystyle PKE^{'}=FO(PKE)}$. For a plaintext ${\displaystyle m\in M^{'}=\{0,1\}^{k^{'}}}$ and a random string ${\displaystyle r\in R^{'}=\{0,1\}^{k^{'}}=M}$, the ciphertext is ${\displaystyle (Enc_{pk}(r;H(m,r)),G(r)\oplus m)}$.

Modifying the existing proofs, we can show the scheme is secure in the SPT-ROM using Lemma 2.

Theorem 7. Suppose that ${\displaystyle PKE}$ is OW-CPA secure and ${\displaystyle \gamma }$-uniform for some negligible ${\displaystyle \gamma }$.
Then, ${\displaystyle PKE^{'}=FO(PKE)}$ is IND-CCA2 secure in the SPT-ROM.


However, the presence of the first-preimage oracle for ${\displaystyle G}$ violates the IND-CPA security of ${\displaystyle PKE^{'}}$ in some parameter settings. Note that if ${\displaystyle m}$ is ${\displaystyle 0^{k^{'}}}$, the second component of the ciphertext is ${\displaystyle G(r)}$ , which is vulnerable the first-preimage oracle of ${\displaystyle G}$.

Theorem 8. Let ${\displaystyle C=\#M/2^{k^{'}}}$. Assume that ${\displaystyle C=k^{O(1)}}$ . Then, ${\displaystyle PKE^{'}=FO(PKE)}$ is not IND-CPA secure in the FPT-ROM.


Proof. We prove the theorem by constructing the adversary ${\displaystyle A=(A_{1},A_{2})}$ which exploits the first-preimage oracle of ${\displaystyle G,FPO^{G}}$. The adversary ${\displaystyle A_{1}}$, on input ${\displaystyle pk}$, queries ${\displaystyle m_{0}=0^{k^{'}}}$ and ${\displaystyle m_{1}=1^{k^{'}}}$ to the challenger. The adversary ${\displaystyle A_{2}}$, on input the target ciphertext ${\displaystyle (c_{1}^{*},c_{2}^{*})}$, queries ${\displaystyle c_{2}^{*}}$ to the first-preimage oracle of ${\displaystyle G}$ . If it obtains ${\displaystyle {\stackrel {\sim }{r}}}$ , it checks that ${\displaystyle c_{1}=Enc_{pk}({\stackrel {\sim }{r}};H(0^{k^{'}},{\stackrel {\sim }{r}}))}$ . If the check passes, the adversary outputs ${\displaystyle b^{'}=0}$. Otherwise, it flips a random fair coin ${\displaystyle b^{'}}$ , outputs ${\displaystyle b^{'}}$ , and halts.

It is obvious that if ${\displaystyle b=0}$ and ${\displaystyle {\stackrel {\sim }{r}}=r}$ , the adversary answers correctly, that is, it outputs ${\displaystyle b^{'}=b}$ . If ${\displaystyle b=1}$, the preimage of the query ${\displaystyle G(r)\oplus 1^{k^{'}}}$ never equals to ${\displaystyle r}$ since ${\displaystyle G(r),G(r)\oplus 1^{k^{'}}}$ . Hence, the adversary’s check fails if ${\displaystyle b=1}$ .

We estimate the probability that the adversary wins. By Lemma 1, with probability at least ${\displaystyle 1-2^{-2k^{'}}}$ , there is no preimage of size larger than ${\displaystyle L}$ , where if ${\displaystyle C\geq 1}$ then ${\displaystyle L=5Ck^{'}\ln 2/(\ln {k^{'}}+ln{ln2})\leq 4Ck^{'}/\ln {k^{'}}}$ and otherwise ${\displaystyle L=5k^{'}\ln 2/(\ln {k^{'}}+ln{ln2})\leq 4k^{'}/\ln {k^{'}}}$ for all sufficiently large ${\displaystyle k^{'}}$.

As shown above, the FO conversion is not secure in the FPT-ROM, but there is a way to modify it so as to maintain the security in the FPT-ROM. Naito,Wang, and Ohta proposed the conversion method that converts a cryptosystem secure in the ROM to that secure even in the FPT-ROM [29]. In the case of the FO conversion, the public key is ${\displaystyle (pk,c)}$ , where ${\displaystyle c\leftarrow \{0,1\}^{k}}$, and the ciphertext is

${\displaystyle (c_{1},c_{2})=(Enc_{pk}(r;H(c,m,r)),G(c,r)\oplus m)}$ ,

where the domains of ${\displaystyle H}$ and ${\displaystyle G}$ are modified. Intuitively, this change makes the firstpreimage oracles, ${\displaystyle FPO^{H}}$ and ${\displaystyle FPO^{G}}$ , useless.

### OAEP

We finally focus on the OAEP and present its IND-CCA2 security in the FPT-ROM. For the security parameter ${\displaystyle k}$, let ${\displaystyle k_{0}}$ and ${\displaystyle k_{1}}$ be functions in ${\displaystyle k}$ , where ${\displaystyle k_{0}. Let ${\displaystyle F}$ be a family of partial-domain one-way trapdoor permutations of a domain ${\displaystyle \{0,1\}^{k-k_{0}}\times \{0,1\}^{k_{0}}}$ . (See [30] for the definition of the partial-domain one-wayness.) Furthermore, let ${\displaystyle G}$ and ${\displaystyle H}$ be hash functions such that ${\displaystyle G\colon \{0,1\}^{k_{0}}\rightarrow \{0,1\}^{k-k_{0}}}$ and ${\displaystyle H\colon \{0,1\}^{k-k_{0}}\rightarrow \{0,1\}^{k_{0}}}$ .

We obtain the following theorem that states the security of the OAEP encryption scheme in the FPT-ROM.

Theorem 9. Let ${\displaystyle F}$ be a family of partial-domain one-way trapdoor permutations.
Then, the OAEP encryption scheme based on ${\displaystyle F}$ is IND-CCA2 secure in the FPT-ROM.


We here only give the sketch of the security proof.

Proof (Sketch). As in the proof of Fujisaki et al. [30], we prove the security by defining a sequence of games and bounding the advantages of the adversary among the games. The games are the almost same as the original ones in [30]. However, we need to pay attention to the following two points. First, as mentioned, we no longer have the uniformity of the ROM because of the first-preimage oracle. Second, the adversary can make use of the first-preimage oracle. These points make the security proofs difficult.

In order to observe the difference between the security proofs in the FPT-ROM and ROM, let us consider the following two games. We will describe the sequence of the games in the full version.

– Game1: The challenger generates a pair of keys ( fpk, gsk) by using the key-generation
algorithm. It next produces r+ ← {0, 1}k0 and obtains g+ ← ROG(r+). In generation
of the target ciphertext, the challenger generates the random string r+. The target
ciphertext y∗ is generated as follows:
r∗ ← r+, s∗ ← (mb ∥ 0k1 ) ⊕ g+, t∗ ← r∗ ⊕ ROH(s∗),
x∗ ← (s∗, t∗), y∗ ← fpk(x∗).
The ciphertext y∗ is given to A. Finally, the adversary A outputs a bit b′.

– Game2: We modify the above game, by changing the rule for generation of g+.
That is, g+ is not obtained by the query of the random oracle, but obtained by choosing
from {0, 1}k−k0 uniformly at random. Notice that (r+, g+) is not contained in the table TG.


Let AskG be the event that r+ is queried to ROG. The original proof in the ROM showed that, if the value r+ is not queried to ROG, the Game1 and Game2 are identical.

By carefully applying similar arguments, we can show the IND-CCA2 security for the OAEP encryption scheme in FPT-ROM.

## Future Work

It should be noted that our WROMs are based on a simplified variant, which Numayama et al. [18] and Pasini and Vaudenay [17] also adopted, of the original WROMs of Liskov [15].

The original WROMs consists of the ideal compression function h : {0, 1}k+k′ → {0, 1}k of fixed input length and the first-preimage oracle. Then, he discussed the security of the flexible input-length hash functions Hh : {0, 1}∗ → {0, 1}k employing h as the component in the context of indifferentiability [31]. A random oracle H is often instantiated by employing a compression h. (See, e.g., the survey in [8].) Therefore, his work reflects the attacks against the compression function of MD5 and SHA-1 rather than the construction H.

On the contrary, we (and similarly [18] [17]) discussed the monolithic random oracle H and the additional oracles associated with H. Hence, our model has a gap from such a realistic instantiation of the random oracle in some sense. We leave filling this gap as future work.

Except for the FO conversion, there are several conversion methods in the ROM, such as REACT [32] and GEM [33]. It would also be interesting as future work to examine the security of these conversion methods in the WROMs.

## Acknowledgements

We thank anonymous reviewers for their helpful comments. This research was supported in part by NTT Information Sharing Platform Laboratories, JSPS Global COE program “Computationalism as Foundation for the Sciences,” KAKENHI 18300002, KAKENHI 19-55201, and the Japan Science and Technology Agency, Strategic Japanese-French Cooperative Program “Quantum Computer: Theory and Feasibility.”

## References

Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />
1. Bellare, M., Rogaway, P.: Random oracle are practical: A paradigm for designing efficient protocols. In: CCS ’93, ACM (1993) 62–73
2. Rivest, R.L.: The MD5 message-digest algorithm. Internet Request for Comments (April 1992) RFC 1321.
3. National Institute of Standards and Technology: Secure hash standard. FIPS 180-2 (August 2002)
4. Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. Journal of the ACM 51(4) (2004) 557–594 Preliminary version in STOC ’98, 1998.
5. Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: FOCS 2003, IEEE Computer Society (2003) 102–113
6. Bellare, M., Boldyreva, A., Palacio, A.: An uninstantiable random-oracle-model scheme for a hybrid-encryption problem. In Franklin, M.K., ed.: CRYPTO 2004. Volume 3152 of LNCS., Springer, Heidelberg (2004) 171–188
7. Bellare, M., Rogaway, P.: The exact security of digital signatures – how to sign with RSA and Rabin. In Maurer, U.M., ed.: EUROCRYPT ’96. Volume 1070 of LNCS., Springer, Heidelberg (1996) 399–416
8. Leurent, G., Nguyen, P.Q.: How risky is the random-oracle model? In Halevi, S., ed.: CRYPTO 2009. Volume 5677 of LNCS., Springer, Heidelberg (2009) 445–464 The full version is available at http://eprint.iacr.org/2008/441.
9. Wang, X., Yu, H.: How to break MD5 and other hash functions. In Cramer, R., ed.: EUROCRYPT 2005. Volume 3494 of LNCS., Springer, Heidelberg (2005) 19–35
10. Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In Shoup, V., ed.: CRYPTO 2005. Volume 3621 of LNCS., Springer, Heidelberg (2005) 17–36
11. Aoki, K., Sasaki, Y.: Preimage attacks on one-block MD4, 63-step MD5 and more. In Jacobson, Jr., M.J., Rijmen, V., Safavi-Naini, R., eds.: SAC 2009. Volume 5867 of LNCS., Springer, Heidelberg (2009) 103–119
12. Nielsen, J.B.N.: Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case. In Yung, M., ed.: CRYPTO 2002. Volume 2442 of LNCS., Springer, Heidelberg (2002) 111–126
13. Unruh, D.: Random oracles and auxiliary input. 205–223
14. Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In De Santis, A., ed.: EUROCRYPT ’94. Volume 950 of LNCS., Springer, Heidelberg (1995) 92–111
15. Liskov, M.: Constructing an ideal hash function from weak ideal compression functions. In Biham, E., Youssef, A.M., eds.: SAC 2006. Volume 4356 of LNCS., Springer, Heidelberg (2007) 358–375
16. Hoch, J.J., Shamir, A.: On the strength of the concatenated hash combiner when all the hash functions are weak. In Aceto, L., Damgård, I., Goldberg, L.A., Halld´orsson, M.M., Ing´olfsd´ottir, A., Walukiewicz, I., eds.: ICALP 2008, Part II. Volume 5126 of LNCS., Springer, Heidelberg (2008) 616–630
17. Pasini, S., Vaudenay, S.: Hash-and-sign with weak hashing made secure. In Pieprzyk, J., Ghodosi, H., Dawson, E., eds.: ACISP 2007. Volume 4586 of LNCS., Springer, Heidelberg (2007) 338–354
18. Numayama, A., Isshiki, T., Tanaka, K.: Security of digital signature schemes in weakened random oracle models. In Cramer, R., ed.: PKC 2008. Volume 4939 of LNCS., Springer, Heidelberg (2008) 268–287
19. Fischlin, M., Lehmann, A.: Security-amplifying combiners for collision-resistant hash functions. 224–243
20. Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In Wiener, M.J., ed.: CRYPTO ’99. Volume 1666 of LNCS., Springer, Heidelberg (1999) 537–554
21. Kiltz, E., Pietrzak, K.: On the security of padding-based encryption schemes (or: Why we cannot prove OAEP secure in the standard model). In Joux, A., ed.: EUROCRYPT 2009. Volume 5479 of LNCS., Springer, Heidelberg (2009) 389–406
22. Devroye, L.D.: Non-Uniform Random Variate Generation. Springer-Verlag (1986)
23. Ahrens, J.H., Dieter, U.: Computer methods for sampling from Gamma, Beta, Poisson and Binomial distributions. Computing 12(3) (1974) 223–246
24. Ahrens, J.H., Dieter, U.: Sampling from Binomial and Poisson distributions: A method with bounded computation times. Computing 25(3) (1980) 193–208
25. Relles, D.A.: A simple algorithm for generating Binomial random variables when N is large. American Statistical Association 67(339) (1972) 612–613
26. Kawachi, A., Numayama, A., Tanaka, K., Xagawa, K.: Security of encryption schemes in weakened random oracle models. Cryptology ePrint Archive, Report 2010/122 (2010)
27. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press (1995)
28. Katz, J., Lindell, Y.: Introduction to Modern Cryptography. Chapman & Hall/CRC (2007)
29. Naito, Y., Wang, L., Ohta, K.: How to construct cryptosystems and hash functions in weakenend random oracle models. Cryptology ePrint Archive, Report 2009/550 (2009)
30. Fujisaki, E., Okamoto, T., Pointcheval, D., Stern, J.: RSA-OAEP is secure under the RSA assumption. Journal of Cryptology 17(2) (2004) 81–104
31. Maurer, U.M., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In Naor, M., ed.: TCC 2004. Volume 2951 of LNCS., Springer, Heidelberg (2004) 21–39
32. Okamoto, T., Pointcheval, D.: REACT: Rapid enhanced-security asymmetric cryptosystem transform. In Naccache, D., ed.: CT-RSA 2001. Volume 2020 of LNCS., Springer, Heidelberg (2001) 159–175
33. Coron, J.S., Handschuh, H., Joye, M., Paillier, P., Pointcheval, D., Tymen, C.: Gem: A Generic chosen-ciphertext secure Encryption Method. In Preneel, B., ed.: CT-RSA 2002. Volume 2271 of LNCS., Springer, Heidelberg (2002) 175–184