Cryptography Reference
In-Depth Information
every probabilistic polynomial-time algorithm, A , there exists a prob-
abilistic polynomial-time algorithm B so that for every two functions
f,h :
} →{
} such that
{
0 , 1
0 , 1
|
h ( x )
|
=poly(
|
x
|
), and all probabil-
ity ensembles
{
X n } n∈ N ,where X n is a random variable ranging over
n , it holds that
Pr[ A ( e, E e ( x ) ,h ( x ))= f ( x )] < Pr[ B (1 n ,h ( x ))= f ( x )] + µ ( n ) .
{ 0 , 1 }
where the plaintext x is distributed according to X n , the encryption-
key e is distributed according to G (1 n ), and µ is a negligible function.
That is, it is feasible to predict f ( x )from h ( x ) as successfully as it is
to predict f ( x )from h ( x )and( e, E e ( x )), which means that nothing
is gained by obtaining ( e, E e ( x )). Note that no computational restric-
tions are made regarding the functions h and f . We stress that the
above definition (as well as the next one) refers to public-key encryp-
tion schemes, and in the case of private-key schemes algorithm A is not
given the encryption-key e .
A good disguise should not allow a mother
to distinguish her own children.
Shafi Goldwasser and Silvio Micali, 1982
The following technical interpretation of security states that it is infeas-
ible to distinguish the encryptions of two plaintext s (of the same
length).
Definition 5.2. (indistinguishability of encryptions (following (80))):
A public-key encryption scheme ( G, E, D )has indistinguishable encryp-
tions if for every probabilistic polynomial-time algorithm, A ,andall
sequences of triples, ( x n ,y n ,z n ) n∈ N ,where
|
x n |
=
|
y n |
= n and
|z n | =poly( n ),
|
Pr[ A ( e, E e ( x n ) ,z n )=1]
Pr[ A ( e, E e ( y n ) ,z n )=1]
|
= µ ( n ) .
Again, e is distributed according to G (1 n ), and µ is a negligible func-
tion.

Search WWH ::

Custom Search