RSA-OAEP Is Secure under the RSA Assumption.
Recently Victor Shoup noted that there is a gap in the widely believed security result of OAEP against adaptive chosen-ciphertext attacks. Moreover, he showed that, presumably, OAEP cannot be proven secure from the one-wayness of the underlying trapdoor permutation. This paper establishes another result on the security of OAEP. It proves that OAEP offers semantic security against adaptive chosen-ciphertext attacks, in the random oracle model, under the partial-domain one-wayness of the underlying permutation. Therefore, this uses a formally stronger assumption. Nevertheless, since partial-domain one-wayness of the RSA function is equivalent to its (full-domain) onewayness, it follows that the security of RSA-OAEP can actually be proven under the sole RSA assumption, although the reduction is not tight.
Introduction
The OAEP conversion method [3] was introduced by Bellare and Rogaway in
1994 and was believed to provide semantic security against adaptive chosen-ciphertext
attacks [7, 12], based on the one-wayness of a trapdoor permutation,
using the (corrected) definition of plaintext-awareness [1].
Victor Shoup [15] recently showed that it is quite unlikely that such a security
proof exists - at least for non-malleability - under the one-wayness of
the permutation. He also proposed a slightly modified version of OAEP, called
OAEP+, which can be proven secure, under the one-wayness of the permutation.
Does Shoup's result mean that OAEP is insecure or that it is impossible to
prove the security of OAEP? This is a totally misleading view: the result only
states that it is highly unlikely to find any proof, under just the one-wayness
assumption. In other words, Shoup's result does not preclude the possibility of
proving the security of OAEP from stronger assumptions.
This paper uses such a stronger assumption. More precisely, in our reduc-
tion, a new computational assumption is introduced to prove the existence of
a simulator of the decryption oracle. Based on this idea, we prove that OAEP
is semantically secure against adaptive chosen-ciphertext attack in the random
oracle model [3], under the partial-domain one-wayness of the underlying per-
mutation, which is stronger than the original assumption.
Since partial-domain one-wayness of the RSA function [13] is equivalent
to the (full-domain) one-wayness, the security of RSA-OAEP can actually be
proven under the one-wayness of the RSA function.
The rest of this paper is organized as follows. Section 2 recalls the basic
notions of asymmetric encryption and the various security notions. Section 3
reviews the OAEP conversion [3]. Sections 4 and 5 present our new security
result together with a formal proof for general OAEP applications. In Section 6,
we focus on the RSA application of OAEP, RSA-OAEP.
Public-Key Encryption
The aim of public-key encryption is to allow anybody who knows the public key
of Alice to send her a message that only she will be able to recover it through
her private key.
2.1 Definitions
A public-key encryption scheme is defined by the three following algorithms:
- The key generation algorithm K. On input 1 k , where k is the security pa-
rameter, the algorithm K produces a pair (pk; sk) of matching public and
secret keys. Algorithm K is probabilistic.
- The encryption algorithm E . Given a message m and a public key pk, E
produces a ciphertext c of m. This algorithm may be probabilistic.
- The decryption algorithm D. Given a ciphertext c and the secret key sk, D
returns the plaintext m. This algorithm is deterministic.
2.2 Security Notions
The first security notion that one would like for an encryption scheme is one-
wayness: starting with just public data, an attacker cannot recover the complete
plaintext of a given ciphertext. More formally, this means that for any adversary
her success in inverting E without the secret key should be negligible over
the probability space M
\Theta\Omega , where M is the message space
and\Omega is the space
of the random coins r used for the encryption scheme, and the internal random
coins of the adversary:
ow
m;r
However, many applications require more from an encryption scheme, namely
semantic security (a.k.a. polynomial security or indistinguishability of encryptions
denoted IND): if the attacker has some information about the plain-
text, for example that it is either "yes" or "no" to a crucial query, no adversary
should learn more with the view of the ciphertext. This security notion requires
computational impossibility to distinguish between two messages, chosen by the
adversary, one of which has been encrypted, with a probability significantly
better than one half: her advantage Adv ind (A), where the adversary A is seen
as a 2-stage Turing machine should be negligible, where Adv ind (A) is
formally defined as.
2 \Theta Pr
b;r
Another notion was defined thereafter, the so-called non-malleability [6], in
which the adversary tries to produce a new ciphertext such that the plaintexts
are meaningfully related. This notion is stronger than the above one, but it is
equivalent to semantic security in the most interesting scenario [1].
On the other hand, an attacker can use many kinds of attacks: since we
are considering asymmetric encryption, the adversary can encrypt any plain-text
of her choice with the public key, hence chosen-plaintext attack. She may,
furthermore, have access to more information, modeled by partial or full access
to some oracles: a plaintext-checking oracle which, on input of a pair (m; c),
answers whether c encrypts the message m. This attack has been named the
Plaintext-Checking Attack [11]; a validity-checking oracle which, on input of a
ciphertext c, just answers whether it is a valid ciphertext. This weak oracle
(involved in the reaction attacks [8]) had been enough to break some famous
encryption schemes [4, 9], namely PKCS #1 v1.5; or the decryption oracle itself,
which on the input of any ciphertext, except the challenge ciphertext, responds
with the corresponding plaintext (non-adaptive/adaptive chosen-ciphertext attacks
[10, 12]). The latter, the adaptive chosen-ciphertext attack denoted CCA2,
is clearly the strongest one.
A general study of these security notions and attacks was given in [1], we
therefore refer the reader to this paper for more details. However, the by now
expected security level for public-key encryption schemes is semantic security
against adaptive chosen-ciphertext attacks (IND-CCA2) - where the adversary
just wants to distinguish which plaintext, between two messages of her choice,
had been encrypted; she can ask any query she wants to a decryption oracle
(except the challenge ciphertext). This is the strongest scenario one can define.
3 Review of OAEP
3.1 The Underlying Problems
Consider permutation f : f0; 1g k \Gamma! f0; 1g k , which can also be seen as
with In the original description of OAEP from [3], it is only
required that f is a trapdoor one-way permutation. However, in the following,
we consider two additional related problems: the partial-domain one-wayness
and the set partial-domain one-wayness of permutation f :
-One-Wayness of f , means that for any adversary A whose running
time is bounded by - , the success probability Succ ow (A) is upper-bounded
by ", where
ow
-Partial-Domain One-Wayness of f , means that for any adversary A
whose running time is bounded by - , the success probability Succ pd\Gammaow (A)
is upper-bounded by ", where
-Set Partial-Domain One-Wayness of f , means that for any adversary
A that outputs a set of ' elements within time bound - , the success
probability Succ s\Gammapd\Gammaow (A) is upper-bounded by ", where
We denote by Succ ow (- ), (resp. Succ pd\Gammaow (-) and Succ s\Gammapd\Gammaow ('; -)) the maximal
success probability Succ ow (A) (resp. Succ pd\Gammaow (A) and Succ s\Gammapd\Gammaow (A)).
The maximum ranges over all adversaries whose running time is bounded by - .
In the third case, there is an obvious additional restriction on this range from
the fact that A outputs sets with ' elements. It is clear that for any - and ' - 1,
Succ s\Gammapd\Gammaow ('; - Succ pd\Gammaow (- Succ ow (-):
Note that, by randomly selecting an element in the set returned by an adversary
to the Set Partial-Domain One-Wayness, one breaks Partial-Domain
One-Wayness with probability Succ s\Gammapd\Gammaow (A)='. This provides the following inequality
Succ pd\Gammaow (- Succ s\Gammapd\Gammaow ('; -)='. However, for specific choices of f ,
more efficient reductions may exist. Also, in some cases, all three problems are
polynomially equivalent. This is the case for the RSA permutation [13], hence
the results in section 6.
3.2 The OAEP Cryptosystem
We briefly describe the OAEP cryptosystem (K; D) obtained from a permutation
f , whose inverse is denoted by g. We need two hash functions G and
H:
Then,
specifies an instance of the function f , and of its inverse g. The public
key pk is therefore f and the secret key sk is g.
given a message m 2 f0; 1g n , and a random value r R
the encryption algorithm E pk computes
and outputs the ciphertext
thanks to the secret key, the decryption algorithm D sk extracts
k1 , the algorithm returns [M returns "Reject".
In the above description, [M
denotes the k 1 least significant bits of M , while
denotes the n most significant bits of M .
In their paper [3], Bellare and Rogaway provided a security analysis, which
proved that the OAEP construction together with any trapdoor one-way permutation
is semantically security and (weakly) plaintext-aware. Unfortunately,
this just proves semantic security against non-adaptive chosen-ciphertext attacks
(a.k.a. lunchtime attacks [10] or IND-CCA1). Even if the achieved security was
believed to be stronger (namely IND-CCA2), it had never been proven. Thus,
Shoup [15] recently showed that it is quite unlikely that such a security proof
exists, for any trapdoor one-way permutation. However, he provided a specific
proof for RSA with public exponent 3.
In the following, we provide a general security analysis, but under a stronger
assumption about the underlying permutation. Indeed, we prove that the scheme
is IND-CCA2 in the random oracle model [2], relative to the partial-domain one-wayness
of function f . More precisely, the following exact security result holds.
Theorem 1. Let A be a CCA2-adversary against the "semantic security" of the
making q D ,
q G and q H queries to the decryption oracle, and the hash functions G and H
respectively. Then, Succ pd\Gammaow (t 0 ) is greater thanq H
denotes the time complexity of function
f .
In order to prove this theorem relative to the partial-domain one-wayness of the
permutation, one can use the related notion of set partial-domain one-wayness.
The theorem follows from the inequalities of the previous section together with
the lemma stated below.
Lemma 2. Let A be a CCA2-adversary against the "semantic security" of the
making q D ,
q G and q H queries to the decryption oracle, and the hash functions G and H
respectively. Then, Succ s\Gammapd\Gammaow (q
denotes the time complexity of function
f .
The next section is devoted to proving this lemma. Hereafter, we will repeatedly
use the following simple result:
Lemma 3. For any probability events E, F and G
ae
5 Proof of Lemma 2
We prove lemma 2 in three stages. The first presents the reduction of IND-
adversary A to algorithm B for breaking the partial-domain one-wayness
of f . Note that, in the present proof, we are just interested in security under the
partial-domain one-wayness of f , and not under the full-domain one-wayness
of f as in the original paper [3]. The second shows that the decryption oracle
simulation employed in this reduction works correctly with overwhelming probability
under the partial-domain one-wayness of f . This latter part differs from
the original proof [3], and corrects the recently spotted flaw [15]. Finally, we analyze
the success probability of our reduction in total, through the incorporation
of the above-mentioned analysis of the decryption oracle simulation.
5.1 Description of the Reduction
In this first part, we recall how reduction operates. Let be an
adversary against the semantic security of (K;
attacks. Within time bound t, A asks q D , q G and q H queries to the decryption
oracle and the random oracles G and H respectively, and distinguishes the right
plaintext with an advantage greater than ". Let us describe the reduction B.
5.1.1 Top Level Description of the Reduction.
1. B is given a function f (defined by the public key) and c ?
. The aim of B is to recover the partial
pre-image s ? of c ? .
2. B runs A 1 on the public data, and gets a pair of messages fm as well
as state information st. It chooses a random bit b, and then gives c ? to A 1 ,
as the ciphertext of m b . B simulates the answers to the queries of A 1 to
the decryption oracle and random oracles G and H respectively. See the
description of these simulations below.
3. B runs A 2 finally gets answer b 0 . B simulates the answers to
the queries of A 2 to the decryption oracle and random oracles G and H
respectively. See the description of these simulations below. B then outputs
the partial pre-image s ? of c ? , if one has been found among the queries asked
to H (see below), or the list of queries asked to H.
5.1.2 Simulation of Random Oracles G and H. The random oracle
simulation has to simulate the random oracle answers, managing query/answer
lists G-List and H-List for the oracles G and H respectively, both are initially set
to empty lists:
- for a fresh query fl to G, one looks at the H-List, and for any query ffi asked to
H with answer H ffi , one builds checks whether c
If for some ffi, that relation holds, function f has been inverted, and we can
still correctly simulate G, by answering G Note that G fl is
then a uniformly distributed value since and the latter is uniformly
distributed. Otherwise, one outputs a random value G fl . In both cases, the
concatenated to the G-List.
- for a fresh query ffi to H, one outputs a random value H ffi , and the pair
is concatenated to the H-List. Note that, once again, for any (fl; G
one may build
that relation holds, we have inverted the function f .
5.1.3 Simulation of the Decryption Oracle. On query to the
decryption oracle, decryption oracle simulation DS looks at each query-answer
G-List and (ffi; H H-List. For each pair taken from both lists, it
defines
and checks whether
As soon as both equalities hold, DS outputs [-] n . If no such pair is found,
"Reject" is returned.
5.1.4 Remarks. When we have found the pre-image of c ? , and thus inverted
f , we could output the expected result s ? and stop the reduction. But for this
analysis, we assume the reduction goes on and that B only outputs it, or the list
of queries asked to H, once A 2 has answered b 0 (or after a time limit).
Even if no answer is explicitly specified, except by a random value for new
queries, some are implicitly defined. Indeed, c ? is defined to be a ciphertext of
randomly defined, r ? can be seen as a random variable. Let us
denote by AskG the event that query r ? has been asked to G, and by AskH
the event that query s ? has been asked to H. Let us furthermore denote by
GBad the event that r ? has been asked to G, but the answer is something other
is fixed in the reduction scenario). Note that the
event GBad implies AskG. As seen above, GBad is the only event that makes
the random oracle simulation imperfect, in the chosen-plaintext attack scenario.
In the chosen-ciphertext attack scenario, we described a decryption simulator
that may sometimes fail. Such an event of decryption failure will be denoted by
DBad. We thus denote
5.2 Notations
In order to proceed to the analysis of the success probability of the above-mentioned
reduction, one needs to set up notations. First, we still denote with
a star ( ? ) all variables related to the challenge ciphertext c ? , obtained from the
encryption oracle. Indeed, this ciphertext, of either m 0 or m 1 , implicitly defines
hash values, but the corresponding pairs may not appear in the G or H lists.
All other variables refer to the decryption query c, asked by the adversary to
the decryption oracle, and thus to be decrypted by this simulation. We consider
several further events about a ciphertext queried to the decryption oracle:
- CBad denotes the union of the bad events,
ffl SBad denotes the event that
ffl RBad denotes the event that
- AskRS denotes the intersection of both events about the oracle queries,
which means that both r and s have been asked
to G and H respectively, since
ffl AskR denotes the event that r (= H(s) \Phi t) has been asked to G;
ffl AskS denotes the event that s has been asked to H;
- Fail denotes the event that the above decryption oracle simulator outputs a
wrong decryption answer to query c. (More precisely, we may denote Fail i for
event Fail on the i-th query c i our analysis, however, we
can evaluate probabilities regarding event Fail i in a uniform manner for any
i. Hence, we just employ notation Fail.) Therefore, in the global reduction,
the event DBad will be set to true as soon as one decryption simulation fails.
Note that the Fail event is limited to the situation in which the plaintext-
extractor rejects a ciphertext whereas it would be accepted by the actual decryption
oracle. Indeed, as soon as it accepts, we see that the ciphertext is actually
valid and corresponds to the output plaintext.
5.3 Analysis of the Decryption Oracle Simulation
We analyze the success probability of decryption oracle simulator DS.
5.3.1 Security Claim. We claim the following, which repairs the previous
proof [3], based on the new computational assumption. More precisely, we show
that additional cases to consider, due to the corrected definition of plaintext-
awareness [1], are very unlikely under the partial-domain one-wayness of the
permutation
Lemma 4. When at most one ciphertext c directly obtained
from the encryption oracle, but s ? has not been asked to H, the decryption
oracle simulation DS can correctly produce the decryption oracle's output
on query (ciphertext) c (6= c ? ) with probability greater than " 0 , within time bound
Before we start the analysis, we recall that the decryption oracle simulator
is given the ciphertext c to be decrypted, as well as the ciphertext c ? obtained
from the encryption oracle and both the G-List and H-List resulting from the interactions
with the random oracles G and H. Let us first see that the simulation
uniquely defines a possible plaintext, and thus can output the first one it finds.
Indeed, with the above definition, several pairs could satisfy the equalities. How-
ever, since function f is a permutation, and thus one-to-one, the value of
is uniquely defined, and thus ffi and H ffi . Similarly, uniquely defined, and
thus fl and G fl : at most one - may be selected. Then either [-] k 1
not.
In the above, one should keep in mind that the G-List and H-List correspond
to input-output pairs for the functions G and H. Thus, at most one output is
related to a given input.
If the ciphertext has been correctly built by the adversary (r has been asked
to G and s to H), the simulation will output the correct answer. However, it will
output "Reject" in any other situation, whereas the adversary may have built a
valid ciphertext without asking both queries to the random oracles G and H.
5.3.2 Success Probability. Since our goal is to prove the security relative
to the partial-domain one-wayness of f , we are only interested in the probability
of the event Fail, while :AskH occurred, which may be split according to other
events. Granted :CBad-AskRS, the simulation is perfect, and cannot fail. Thus,
we have to consider the complementary events:
Concerning the latter contribution to the right hand side, we first note that both
Forgetting :AskH for a while, using lemma 3, one gets that Pr[Fail - :CBad -
:AskRS] is less than
But without having asked r to G, taking into account the further event :RBad,
G(r) is unpredictable, and thus the probability that [s \Phi G(r)] k 1
than 2 \Gammak 1 . On the other hand, the probability of having asked r to G, without
any information about H(s) and thus about r (H(s) not asked, and s
which both come from the conditioning :AskS - :SBad), is less than q G \Delta 2 \Gammak 0 .
Furthermore, this event is independent of AskH, which yields
We now focus on the former term, Fail - CBad, while :AskH, which was
missing in the original proof [3] based on a weaker notion of plaintext-awareness.
It can be split according to the disjoint sub-cases of CBad, which are SBad and
:SBad - RBad. Then again using lemma 3,
The latter event means that RBad occurs provided s and the adversary has
not queried s ? from H. When s ? has not been asked to H and s
unpredictable and independent of H(s) as well as t and t ? . Then, event RBad,
occurs with probability at most 2 \Gammak 0 .
The former event can be further split according to AskR, and, using once
again lemma 3, it is upper-bounded by
The former event means that r is asked to G whereas
unpredictable, thus H(s) is unpredictable. Since r is unpredictable, the probability
of this event is at most q G \Delta 2 \Gammak 0 (the probability of asking r to G). On
the other hand, the latter event means that the simulator rejects the valid ciphertext
c whereas H(s) is unpredictable and r is not asked to G. From the
one-to-one property of the Feistel network, it follows from
and thus G(r) is unpredictable. Then the redundancy cannot hold with probability
greater than 2 \Gammak 1 . To sum up, Pr[Fail
thus Pr[Fail - CBad
As a consequence,
The running time of this simulator includes just the computation of f(oe; -) for
all possible pairs and is thus bounded by q G \Delta q H \Delta (T f +O(1)).
5.4 Success Probability of the Reduction
This subsection analyzes the success probability of our reduction with respect
to the advantage of the IND-CCA2 adversary. The goal of the reduction is, given
Therefore, the success probability is obtained by
the probability that event AskH occurs during the reduction (i.e., Pr[AskH] -
is the running time of the reduction).
We thus evaluate Pr[AskH] by splitting event AskH according to event Bad.
First let us evaluate the first term.
'2 k1
Here, Pr[DBad j :AskH] - q D
is directly obtained
from lemma 4, and Pr[GBad j :AskH] - Pr[AskG j :AskH] is obtained from the
fact that event GBad implies AskG. When :AskH occurs, H(s ? ) is unpredictable,
Hence Pr[AskG j :AskH] - q G \Delta 2 \Gammak 0 .
We then evaluate the second term.
Here, when :AskH occurs, H(s ? ) is unpredictable, thus r
predictable, and so is b as well. This fact is independent from event :Bad. Hence
"+2
Therefore,
"+2
Combining the evaluation for the first and second terms, and from the fact that
5.5 Complexity Analysis.
Note that during the execution of B, for any new G-query fl, one has to look at
all query-answer pairs (ffi; H ffi ) in the H-List, and to compute
as well as f(s; t).
Apparently, one should perform this computation again to simulate the decryption
of any ciphertext. Proper bookkeeping allows the computation to be
done once for each pair, when the query is asked to the hash functions. Thus,
the time complexity of the overall reduction is t
where T f denotes the time complexity for evaluating function f .
6 Application to RSA-OAEP
The main application of OAEP is certainly the famous RSA-OAEP, which has
been used to update the PKCS #1 standard [14]. In his paper [15], Shoup was
able to repair the security result for a small exponent, using Coppersmith's
algorithm from [5]. However, our result can be applied to repair RSA-OAEP,
regardless of the exponent; thanks to the random self-reducibility of RSA, the
partial-domain one-wayness of RSA is equivalent to that of the whole RSA
problem, as soon as a constant fraction of the most significant bits (or the least
significant bits) of the pre-image can be recovered.
We note that, in the original RSA-OAEP [3], the most significant bits are
involved in the H function, but in PKCS #1 standards v2.0 and v2.1 [14] and
RFC2437, the least significant bits are used: the value maskedSeedkmaskedDB
is the input to f , the RSA function, where maskedSeed plays the role of t, and
maskedDB the role of s. But we insist on the fact that the following result holds
in both situations (and can be further extended).
One may also remark that the following argument can be applied to any
random (multiplicatively) self-reducible problem, such as the Rabin function.
Before presenting the final reduction, let us consider the problem of finding
small solutions for a linear modular equation.
Lemma 5. Consider an equation t which has solutions t and
. For all values of ff, except a fraction 2 2k0 +6 =N of them, (t; u)
is unique and can be computed within time bound O((log N) 3 ).
Proof. Consider the lattice
We say that L(ff) is an '-good lattice (and that ff is an '-good value) if there
is no non-zero vector of length at most ' (with respect to the Euclidean norm).
Otherwise, we use the wording '-bad lattices (and '-bad values respectively). It
is clear that there are approximately less than -' 2 such '-bad lattices, which we
bound by 4' 2 . Indeed, each bad value for ff corresponds to a point with integer
coordinates in the disk of radius '. Thus, the proportion of bad values for ff is
less than 4' 2 =N .
Given an '-good lattice, one applies the Gaussian reduction algorithm. One
gets within time O((log N) 3 ) a basis of L(ff) consisting of two non-zero vectors
U and V such that
Let T be the point (t; u), where (t; u) is a solution of the equation t
c mod N , with both t and u less than 2
real -:
Since furthermore we have
by symmetry.
Assuming that we have set from the beginning
2=3, then
Choose any integer solution T of the equation simply by picking a
random integer u 0 and setting t Write it in the basis (U; V
using real numbers ae and oe. These coordinates can be found, so
is a solution to the homogeneous equation, and thus indicate a lattice
unknown integers a and b. But,
with \Gamma1=2 - 1=2. As a conclusion, a and b are the closest integers to
\Gammaae and \Gammaoe respectively. With a, b, ae and oe, one can easily recover - and - and
thus t and u, which are necessarily unique. ut
Lemma 6. Let A be an algorithm that outputs a q-set containing of the
most significant bits of the e-th root of its input (partial-domain RSA, for any
t, with probability ". There
exists an algorithm B that solves the RSA problem (N; e) with success probability
Proof. Thanks to the random self-reducibility of RSA, with part of the bits of
the e-th root of and the e-th root of
(y randomly chosen ff, one gets both x and y. Thus,
(y
which is a linear modular equation with two unknowns r and s which is known
to have small solutions (smaller than 2 k 0 ). It can be solved using lemma 5.
Algorithm B just runs twice A, on inputs X and Xff e and next runs the
Gaussian reduction on all the q 2 pairs of elements coming from both sets. If the
partial pre-images are in the sets, they will be found, unless the random ff is
bad (cf. the Gaussian reduction in lemma 5.) ut
Remark 7. The above lemma can be extended to the case where a constant fraction
\Theta of the leading or trailing bits of the e-th root is found. The reduction
runs 1=\Theta times the adversary A, and the success probability decreases to approximately
" 1=\Theta . Extensions to any constant fraction of consecutive bits are
also possible. Anyway, in PKCS #1 v2.0, k 0 is much smaller than k=2.
Theorem 8. Let A be a CCA2-adversary against the "semantic security" of
RSA-OAEP (with a k-bit long modulus, with k ? 2k 0 ), with running time
bounded by t and advantage ", making q D , q G and q H queries to the decryption
oracle, and the hash functions G and H respectively. Then, the RSA problem
can be solved with probability " 0 greater than
within time bound t 0 - 2t
Proof. Lemma 2 states that
with Using the previous results
relating q H -set partial-domain-RSA and RSA, we easily conclude. ut
7 Conclusion
Our conclusion is that one can still trust the security of RSA-OAEP, but the
reduction is more costly than the original one. However, for other OAEP ap-
plications, more care is needed, since the security does not actually rely on the
one-wayness of the permutation, only on its partial-domain one-wayness.

Acknowledgments

We thank Victor Shoup, Don Coppersmith and Dan Boneh for fruitful comments



--R

Relations among Notions of Security for Public-Key Encryption Schemes
Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols.
Optimal Asymmetric Encryption - How to Encrypt with RSA
A Chosen Ciphertext Attack against Protocols based on the RSA Encryption Standard PKCS
Finding a Small Root of a Univariate Modular Equation.

Probabilistic Encryption.
Reaction Attacks Against Several Public-Key Cryptosystems
On the Power of Misbehaving Adversaries and Security Analysis of the Original EPOC.

REACT: Rapid Enhanced-security Asymmetric Cryptosystem Transform

A Method for Obtaining Digital Signatures and Public Key Cryptosystems.
RSA Data Security
OAEP Reconsidered.
--TR
provable security;public-key encryption;OAEP;RSA