Security of Encryption Schemes in Weakened Random Oracle Models
This page was last modified on 21 December 2015, at 23:00.

Contents
 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, secondpreimage resistance, and onewayness properties. The WROMs offer additional oracles to break such properties of the random oracle. In this paper, we investigate whether publickey 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, secondpreimage tractable, firstpreimage tractable ones (ROM, CTROM, SPTROM, and FPTROM, 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 FujisakiOkamoto conversion (FO) are secure in the SPTROM. However, some encryption schemes with FO are insecure in the FPTROM. 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 CTROM (ROM, respectively). However, some encryption schemes obtained by wFO (dFO, respectively) are insecure in the SPTROM (CTROM, respectively). These results imply that standard encryption schemes such as the OAEP and FObased 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: publickey encryption schemes, weakened random oracle models, OAEP, FujisakiOkamoto 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 SHA1 ^{[3]}. This replacement is called an instantiation of the random oracle.
The random oracle methodology causes a tradeoff 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 onewayness, secondpreimage 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 FullDomainHash (FDH) signature schemes (e.g., ^{[7]}), which are secure in the ROM, relies on the collisionresistance property of the ROM. That is, if we can obtain two distinct messages such that and the signature , then we can obtain a valid forgery , where is a hash function and is a signing algorithm. Leurent and Nguyen also presented the attacks extracting the secret keys on several hashthensign type signature schemes and identitybased 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 SHA1 raises the question on the assumption that hash functions are collision resistant and oneway (e.g.,^{[9]} ^{[10]} ^{[11]}). Therefore, it is significant to investigate whether the collision resistance property (as well as the onewayness and secondpreimage 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 firstpreimage, secondpreimage, 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 nonprogrammable 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 noncommitting encryption scheme exists in the ROM (assuming that trapdoor permutations exists), but not in the nonprogrammable random oracle model.
Unruh proposed a ROM with oracledependent 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 RSAOAEP encryption scheme ^{[14]} is secure in the ROM even under the presence of oracledependent 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 firstpreimage tractable random oracle model offers the random oracle and the firstpreimage oracle associated with the random oracle, which returns a firstpreimage of the random oracle to adversaries. This firstpreimage 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 secondpreimage 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 hashthensign type signature schemes in the firstpreimage 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 publickey 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, secondpreimage tractable, and firstpreimage tractable random oracle models (ROM, CTROM, SPTROM, and FPTROM, respectively for short). Note that they are ordered according to their strengths, i.e., the security of encryption schemes in the FPTROM implies that in the SPTROM 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 FujisakiOkamoto conversion (FO) ^{[20]}, its two artificial variants (dFO and wFO), and the OAEP ^{[14]}. Precisely, we prove the following four statements:
1. OAEP is INDCCA2 secure in the FPTROM. 2. FO is INDCCA2 secure in the SPTROM, but not INDCPA secure in the FPTROM. 3. wFO is INDCCA2 secure in the CTROM, but not INDCCA2 secure in the SPTROM. 4. dFO is INDCCA2 secure in the ROM, but not INDCCA2 secure in the CTROM.
We summarize the security of four schemes in Table 1.

This separation suggests that some publickey 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 secondpreimage 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 FObased 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 firstpreimage resistance property, i.e., the onewayness property. In other words, the OAEP remains secure even if we remove the firstpreimage resistance property. This can also be said on FObased encryption schemes on the secondpreimage resistance property.
On the security of the OAEP, Kiltz and Pietrzak recently showed that there is no construction for paddingbased encryption schemes including the OAEP that has a blackbox reduction from ideal trapdoor permutations to its INDCCA2 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 polynomialtime 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 publickey 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 nonprogrammable model ^{[12]} and the oracledependent auxiliary input model ^{[13]}.
The nonprogrammable model is not simply comparable with WROMs since the programmability does not imply the collision resistance and vice versa. The target of the oracledependent 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 oracledependent 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 oracledependent 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 oracledependent auxiliary input does not completely capture the adaptive security of hash functions, and this model still has the secondpreimage resistance and the firstpreimage 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 secondpreimage resistance are not necessary to prove the security of the OAEP encryption scheme.
Second, Unruh constructed the reduction algorithm which breaks the partialdomain onewayness of the underlying trapdoor permutation using the adversary which breaks the INDCCA2 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 partialdomain onewayness. By using this technique, he can avoid employing a stronger assumption that even quasipolynomial time adversary cannot break the partialdomain onewayness, and can prove the security under the standard partialdomain onewayness against polynomialtime adversary.
In contrast to Unruh’s result, we construct the polynomialtime reduction algorithm using the adversary, and hence we do not require the security amplification technique for the partialdomain onewayness, 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 , we define . For a distribution denotes that is sampled according to . The function stands for the probability function of the distribution .
Let denote that s is sampled from the uniform distribution over a finite set . denotes the number of elements in . For a probabilistic Turing machine and its input , let denote the output distribution of on input .
We usually denote by a security parameter of a cryptographic scheme in this paper. We also denote by length of plaintexts unless it is specified. is implicitly assumed to be polynomially related to the security parameter , that is, . We say a function is negligible in if . For two distributions and over a finte set , we denote the statistical distance (the total variation distance) between them by , defined by . We say two distributions and are statistically close if .
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 and be finite sets. Let be a hash function chosen randomly from all of the functions from to . We denote by the table . We identify the hash function with the table .
We next define the random oracle and the additional oracles associated with as follows. (For more details, see ^{[18]}.)
Random oracle : Given , return such that . Collision oracle : On the query, first pick one entry uniformly at random. If there is no other entry , then answer . Otherwise, pick one entry satisfying uniformly at random and answer . Secondpreimage oracle : Given , if answer . If there is no other entry , then answer . Otherwise, pick one entry satisfying uniformly at random and answer . Firstpreimage oracle : Given , if there is any entry then return such an uniformly at random. Otherwise return .
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 welldefined.
The formal definitions of the WROMs are given as follows. The WROMs consist of three components, a hash function chosen randomly from all of the functions from to , the random oracle, and the additional oracle associated with . The models are called the CTROM, SPTROM, and FPTROM, if the additional oracle is the collision, secondpreimage, and firstpreimage oracle, respectively.
Remark 2. The collision oracle may output even if there exists a collision 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 with probability . In the case where , we can find a collision with polynomially many queries since since . In the case where , we can again find a collision with polynomially many queries . Finally, in the case where , the following lemma shows that there are no collisions with overwhelming probability.
Lemma 1. Let be the hash function, and the number of preimages of under the function , that is, . Let BAD denote the event that there is some such that . Then for all sufficiently large , we have , where if , or otherwise.
The proof is obtained by the standard argument on the balls and bins game by regarding and 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 FPTROM. In the both models, the function , i.e., the table is uniformly distributed. In the ROM, if one queries some that has never been queried to the random oracle, the value of 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 FPTROM, this property is not attained. Recall that the firstpreimage oracle uniformly returns one of the preimages, say , of queried value . If the firstpreimage oracle leaks a number of preimages of , the value of is not uniformly distributed for an not queried yet.
In order to observe this situation, let us consider the following extreme case. Let for some and suppose that has the unique preimage . Then the firstpreimage oracle always returns the same on the input , which convinces us that the number of the preimages of is exactly . This implies that the other does not take a value under . Therefore, the random oracle no longer has the uniformity in the FPTROM. This is a critical difference between the ROM and FPTROM since we often make use of the uniformity in the security proofs of the publickey 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 publickey 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 be the hash function in the WROMs. Let be a probabilistic oracle Turing machine that makes at most queries to the random oracle and the additional oracle , where represents one of the additional oracles , , and . denotes the random variable that represents the hash value , where and the correspondence is not answered by the two oracles. Then, for any , the following holds:
Here, the probability is taken over random choices of the hash function and therandom coin of .
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 denote the binomial distribution with parameters and whose probability function is for , where the parameters and take values approximately and for a hash function , say, . Their simulation methods required the efficient sampler for with exponentially large and small , and they assumed its existence.
Assumption 1. There is a probabilistic Turing machine such that the output distribution on inputs and is equal to the binomial distribution and it runs in polynomial time in and , where is a positive integer and 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, secondpreimage oracle, and firstpreimage oracle in the WROMs under Assumption 1. That is, the output distributions of the random oracle, collision oracle, secondpreimage oracle, and firstpreimage 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 . 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 realnumber 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 realnumber 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 such that, for the output distribution on inputs and , the statistical distance between and is at most and it runs in polynomial time in and , where is a positive integer and are rational numbers.
Note that the algorithm can control the error parameter . This property is useful in cryptographic applications for the security proofs even if the other parameters and 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, secondpreimage oracle, and firstpreimage 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 publickey encryption schemes.We particularly discuss separations for notions of ROM, CTROM, SPTROM, and FPTROM by showing (in)security of publickey encryption schemes obtained by the FujisakiOkamoto conversion (FO) and its two variants (dFO and wFO), and OAEP.
Publickey encryption schemes: We first give notation and notions for publickey encryption schemes briefly. For details, see standard textbooks, e.g., ^{[28]}.
A publickey encryption scheme over a plaintext space and a random coin space is defined by the following three algorithms. Let denote the security parameter.
Key Generation: On input , the key generation algorithm produces a public/secret key pair .
Encryption: Given a public key , a plaintext , and a random string , the encryption algorithm outputs a ciphertext c corresponding to the plaintext .
Decryption: Given a secret key and ciphertext , the decryption algorithm outputs the plaintext or the special symbol corresponding to the ciphertext .
We require the perfect completeness, that is, for every generated by , every plaintext , and every random string , it should be satisfied that
We only consider three standard security notions for publickey encryption schemes, the onewayness against chosenplaintext attack (OWCPA), the indistinguishability against chosenplaintext attack (INDCPA), and the indistinguishability against adaptive chosenciphertext attack (INDCCA2).
For , we say is uniform if for any key pair generated by , any , and , we have . There exists a OWCPA publickey encryption scheme with uniformity (e.g., the ElGamal encryption scheme).
Brief review for FO: Fujisaki and Okamoto proposed a conversion, called the FujisakiOkamoto (FO) conversion, to obtain highly secure publickey encryption schemes in the ROM ^{[20]}. Since the standard onetime pad satisfies the requirement of the FO conversion, we fix the onetime pad as the symmetrickey encryption scheme used in the FO conversion for simplicity.
Let be a OWCPA secure and uniform publickey encryption scheme over a plaintext space and a randomness space . Then the FO conversion converts to an INDCCA2 secure one over a plaintext space and a randomness space , where denotes the length of plaintexts, which is polynomially related to the security parameter . The encryption procedure of is given as follows: For a plaintext and a random string , the ciphertext is
,
where and are hash functions modeled as the random oracles. The decryption procedure is given as follows: For a given ciphertext , decrypt by and obtain . Then, extract by and verify . If not output . Roughly speaking, ensures that if a ciphertext is valid then the encryptor producing knows corresponding and .
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 CTROM.
The variant dFO converts a publickey encryption scheme (with the onetime pad) to another publickey encryption scheme similarly to FO. The encryption procedure of is defined as follows. For a plaintext and a random string , the ciphertext of is
,
where , and , for an appropriate set , are hash functions modeled as the random oracle.
The idea to weaken the conversion is summarized as follows: Recall that in the FO conversion can be considered as encryptor’s signature (or a proof of knowledge) on and . To make it vulnerable by a collision, we introduce a new random oracle and replace with . 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 is a OWCPA secure and uniform publickey encryption scheme for some negligible . Then, is INDCCA2 secure in the ROM if .
Theorem 4. Let be a publickey encryption scheme. If then is not INDCCA2 secure in the CTROM.
Proof. We construct the adversary that breaks the INDCCA2 security of , which exploits the collision oracle of .
The adversary , on input , first queries to . If the answer is , then the adversary flips a random fair coin , outputs , and halts. Otherwise, it obtains a collision of and outputs it as a challenge. The adversary receives the target ciphertext for some . It queries to the decryption oracle and obtains , since
,
.
Hence, the adversary can answer correctly.
Finally, we upperbound the probability that the collision oracle outputs , which stems from the definition of the collision oracle. The probability is bounded by . 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 CTROM, however not generally secure in the SPTROM.
The encryption procedure of is given as follows. For a plaintext and random strings , the ciphertext of is
,
where , and are hash functions modeled as the random oracles.
Notice that is a proof of knowledge on which resists a collision on however is vulnerable by a secondpreimage attack against as in Numayama et al. ^{[18]}.
We can show that the obtained scheme is INDCCA2 secure in the CTROM by using Lemma 2.
Theorem 5. Suppose that is a OWCPA secure and uniform publickey encryption scheme for some negligible . Then, is INDCCA2 secure in the CTROM if and are negligible in .
However, its security is broken under the presence of the secondpreimage oracle for .
Theorem 6. Let be a publickey encryption. If , then the scheme is not INDCCA2 secure in the SPTROM.
Proof. We construct the adversary that exploits the secondpreimage oracle associated to . The adversary chooses random distinct plaintexts and and queries them to the challenger. The challenger responses
.
Receiving , the adversary queries to the secondpreimage oracle . If it receives from the secondpreimage oracle, then it flips a random fair coin , outputs , and halts. Otherwise, it obtains such that . So, the adversary queries
to the decryption oracle. Notice that, if is the valid ciphertext of , then we have
,
,
,
and is a valid ciphertext for . On the other hand, if the ciphertext is the encryption of , we have
.
Thus, if is equal to the decryption oracle returns . Otherwise, the decryption oracle returns .
Thus, if the answer is , then the adversary concludes that is the ciphertext of , that is, it outputs . Otherwise, the adversary concludes that it is the ciphertext of , that is, it outputs . Therefore, can output the correct answer unless receives from the secondpreimage oracle.
We finally bound the probability that the oracle outputs . It is bounded by as required. This completes the proof.
The Original FujisakiOkamoto Conversion
We next show that the obtained scheme by the conversion FO with the onetime pad is secure in the SPTROM, but not secure in the FPTROM in some parameter setting.
Let and be hash functions modeled as the random oracles. Recall the encryption procedure of . For a plaintext and a random string , the ciphertext is .
Modifying the existing proofs, we can show the scheme is secure in the SPTROM using Lemma 2.
Theorem 7. Suppose that is OWCPA secure and uniform for some negligible . Then, is INDCCA2 secure in the SPTROM.
However, the presence of the firstpreimage oracle for violates the INDCPA security of in some parameter settings. Note that if is , the second component of the ciphertext is , which is vulnerable the firstpreimage oracle of .
Theorem 8. Let . Assume that . Then, is not INDCPA secure in the FPTROM.
Proof. We prove the theorem by constructing the adversary which exploits the firstpreimage oracle of . The adversary , on input , queries and to the challenger. The adversary , on input the target ciphertext , queries to the firstpreimage oracle of . If it obtains , it checks that . If the check passes, the adversary outputs . Otherwise, it flips a random fair coin , outputs , and halts.
It is obvious that if and , the adversary answers correctly, that is, it outputs . If , the preimage of the query never equals to since . Hence, the adversary’s check fails if .
We estimate the probability that the adversary wins. By Lemma 1, with probability at least , there is no preimage of size larger than , where if then and otherwise for all sufficiently large .
As shown above, the FO conversion is not secure in the FPTROM, but there is a way to modify it so as to maintain the security in the FPTROM. Naito,Wang, and Ohta proposed the conversion method that converts a cryptosystem secure in the ROM to that secure even in the FPTROM ^{[29]}. In the case of the FO conversion, the public key is , where , and the ciphertext is
,
where the domains of and are modified. Intuitively, this change makes the firstpreimage oracles, and , useless.
OAEP
We finally focus on the OAEP and present its INDCCA2 security in the FPTROM. For the security parameter , let and be functions in , where . Let be a family of partialdomain oneway trapdoor permutations of a domain . (See ^{[30]} for the definition of the partialdomain onewayness.) Furthermore, let and be hash functions such that and .
We obtain the following theorem that states the security of the OAEP encryption scheme in the FPTROM.
Theorem 9. Let be a family of partialdomain oneway trapdoor permutations. Then, the OAEP encryption scheme based on is INDCCA2 secure in the FPTROM.
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 firstpreimage oracle. Second, the adversary can make use of the firstpreimage oracle. These points make the security proofs difficult.
In order to observe the difference between the security proofs in the FPTROM 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 keygeneration 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.
On the other hand, in our case in the FPTROM, even if the event AskG does not occur, that is, the value r+ is not queried, we cannot say that Game1 and Game2 are identical. Notice that the adversary would distinguish the games by querying g+ to FPOG, which leads to a contradiction to the partialdomain onewayness in the final game. The value g+ must have the preimage r+ in Game1 since (r+, g+) is contained in the table TG. In contrast, the value g+ has no preimages in Game2 with high probability if k − k0 is much larger than k0 since (r+, g+) is not inserted in the table TG and ⊥ ← FPOG(g+) with high probability. We must take care of this event AskG−. Additionally, it would distinguish between Game1 and Game2 by querying (m1−b∥0k1 )⊕s∗ to FPOG, which also leads to contradiction to the partialdomain onewayness in the final game. This event is denoted by AskG⋄. Notice that, conditioned on the above events, AskG, AskG−, and AskG⋄, do not occur, g+ is almost perfectly uniform in Game1 by Lemma 2. Hence, we can show two games Game1 and Game2 are statistically close if the events do not occur.
By carefully applying similar arguments, we can show the INDCCA2 security for the OAEP encryption scheme in FPTROM.
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 firstpreimage oracle. Then, he discussed the security of the flexible inputlength 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 SHA1 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 1955201, and the Japan Science and Technology Agency, Strategic JapaneseFrench Cooperative Program “Quantum Computer: Theory and Feasibility.”
References
Cite error: Invalid <references>
tag;
parameter "group" is allowed only.
<references />
, or <references group="..." />
 ↑ Bellare, M., Rogaway, P.: Random oracle are practical: A paradigm for designing efficient protocols. In: CCS ’93, ACM (1993) 62–73
 ↑ Rivest, R.L.: The MD5 messagedigest algorithm. Internet Request for Comments (April 1992) RFC 1321.
 ↑ National Institute of Standards and Technology: Secure hash standard. FIPS 1802 (August 2002)
 ↑ 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.
 ↑ Goldwasser, S., Kalai, Y.T.: On the (in)security of the FiatShamir paradigm. In: FOCS 2003, IEEE Computer Society (2003) 102–113
 ↑ Bellare, M., Boldyreva, A., Palacio, A.: An uninstantiable randomoraclemodel scheme for a hybridencryption problem. In Franklin, M.K., ed.: CRYPTO 2004. Volume 3152 of LNCS., Springer, Heidelberg (2004) 171–188
 ↑ 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.0} ^{8.1} Leurent, G., Nguyen, P.Q.: How risky is the randomoracle 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.
 ↑ 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
 ↑ Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA1. In Shoup, V., ed.: CRYPTO 2005. Volume 3621 of LNCS., Springer, Heidelberg (2005) 17–36
 ↑ Aoki, K., Sasaki, Y.: Preimage attacks on oneblock MD4, 63step MD5 and more. In Jacobson, Jr., M.J., Rijmen, V., SafaviNaini, R., eds.: SAC 2009. Volume 5867 of LNCS., Springer, Heidelberg (2009) 103–119
 ↑ ^{12.0} ^{12.1} ^{12.2} Nielsen, J.B.N.: Separating random oracle proofs from complexity theoretic proofs: The noncommitting encryption case. In Yung, M., ed.: CRYPTO 2002. Volume 2442 of LNCS., Springer, Heidelberg (2002) 111–126
 ↑ ^{13.0} ^{13.1} ^{13.2} Unruh, D.: Random oracles and auxiliary input. 205–223
 ↑ ^{14.0} ^{14.1} ^{14.2} Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In De Santis, A., ed.: EUROCRYPT ’94. Volume 950 of LNCS., Springer, Heidelberg (1995) 92–111
 ↑ ^{15.0} ^{15.1} 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
 ↑ 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.0} ^{17.1} ^{17.2} Pasini, S., Vaudenay, S.: Hashandsign 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.00} ^{18.01} ^{18.02} ^{18.03} ^{18.04} ^{18.05} ^{18.06} ^{18.07} ^{18.08} ^{18.09} ^{18.10} ^{18.11} ^{18.12} ^{18.13} ^{18.14} 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
 ↑ Fischlin, M., Lehmann, A.: Securityamplifying combiners for collisionresistant hash functions. 224–243
 ↑ ^{20.0} ^{20.1} 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
 ↑ Kiltz, E., Pietrzak, K.: On the security of paddingbased 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
 ↑ Devroye, L.D.: NonUniform Random Variate Generation. SpringerVerlag (1986)
 ↑ Ahrens, J.H., Dieter, U.: Computer methods for sampling from Gamma, Beta, Poisson and Binomial distributions. Computing 12(3) (1974) 223–246
 ↑ Ahrens, J.H., Dieter, U.: Sampling from Binomial and Poisson distributions: A method with bounded computation times. Computing 25(3) (1980) 193–208
 ↑ ^{25.0} ^{25.1} ^{25.2} Relles, D.A.: A simple algorithm for generating Binomial random variables when N is large. American Statistical Association 67(339) (1972) 612–613
 ↑ Kawachi, A., Numayama, A., Tanaka, K., Xagawa, K.: Security of encryption schemes in weakened random oracle models. Cryptology ePrint Archive, Report 2010/122 (2010)
 ↑ Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press (1995)
 ↑ Katz, J., Lindell, Y.: Introduction to Modern Cryptography. Chapman & Hall/CRC (2007)
 ↑ 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.0} ^{30.1} ^{30.2} Fujisaki, E., Okamoto, T., Pointcheval, D., Stern, J.: RSAOAEP is secure under the RSA assumption. Journal of Cryptology 17(2) (2004) 81–104
 ↑ 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
 ↑ Okamoto, T., Pointcheval, D.: REACT: Rapid enhancedsecurity asymmetric cryptosystem transform. In Naccache, D., ed.: CTRSA 2001. Volume 2020 of LNCS., Springer, Heidelberg (2001) 159–175
 ↑ Coron, J.S., Handschuh, H., Joye, M., Paillier, P., Pointcheval, D., Tymen, C.: Gem: A Generic chosenciphertext secure Encryption Method. In Preneel, B., ed.: CTRSA 2002. Volume 2271 of LNCS., Springer, Heidelberg (2002) 175–184
Присоединяйся к команде
ISSN:
Следуй за Полисом
Оставайся в курсе последних событий
License
Except as otherwise noted, the content of this page is licensed under the Creative Commons Creative Commons «AttributionNonCommercialNoDerivatives» 4.0 License, and code samples are licensed under the Apache 2.0 License. See Terms of Use for details.