Cryptography Reference
In-Depth Information
many plaintext s using the same encryption-key. Loosely speaking, an
encryption scheme is secure in the multiple-messages setting if analo-
gous definitions (to Definitions 5.1 and 5.2) hold when polynomially-
many plaintext s are encrypted using the same encryption-key (cf. (67,
Sec. 5.2.4)). It is easy to see that in the public-key model , security in the
single-message setting implies security in the multiple-messages setting.
We stress that this is not necessarily true for the private-key model .
5.2
Constructions
It is common practice to use “pseudorandom generators” as a basis for
private-key encryption schemes. We stress that this is a very dangerous
practice when the “pseudorandom generator” is easy to predict (such as
the linear congruential generator or some modifications of it that output
a constant fraction of the bits of each resulting number). However,
this common practice becomes sound provided one uses pseudorandom
generators (as defined in Section 3.2). An alternative and more flexible
construction follows.
Private-key encryption scheme based on pseudorandom func-
tions: We present a simple construction that uses pseudorandom
functions as defined in Section 3.3. The key generation algorithm con-
sists of selecting a seed, denoted s , for a (pseudorandom) function,
denoted f s . To encrypt a message x
n (using key s ), the encryp-
∈{
0 , 1
}
n
tion algorithm uniformly selects a string r
∈{
0 , 1
}
and produces the
ciphertext ( r, x
denotes the exclusive-or of bit strings.
To decrypt the ciphertext ( r, y )(usingkey s ), the decryption algo-
rithm just computes y
f s ( r )), where
f s ( r ). The proof of security of this encryption
scheme consists of two steps (suggested as a general methodology in
Section 3.3):
(1) Prove that an idealized version of the scheme, in which one
uses a uniformly selected function F :
n
n ,rather
{
0 , 1
}
→{
0 , 1
}
than the pseudorandom function f s ,issecure.
(2) Conclude that the real scheme (as presented above) is secure
(because, otherwise one could distinguish a pseudorandom
function from a truly random one).
 
Search WWH ::




Custom Search