Cryptography Reference
In-Depth Information
•
The
decryption algorithm
Dec
takes as input a private key
sk
and a ciphertext
c
and outputs either a plaintext
m
, or a symbol
⊥
denoting failure. We write
m
:=
Dec
(
sk
,
c
)
.
•
There exists a negligible function
negl
such that, for every
n
,every
(
pk
,
sk
)
←
1
n
Gen
(
)
and every message
m
:
Pr
(
Dec
(
sk
,
Enc
(
pk
,
m
))
=
m
)
≤
negl
(
n
).
Remarks 8.1
1. Observe that the definition of public-key encryption scheme is very similar to
that of private-key encryption scheme, with the important difference that there
are different keys for encryption (the public key) and for decryption (the private
key).
2. For the reasons already explained, it is important for security that the encryption
algorithm be probabilistic which, in practice, means that there can be many dif-
ferent ciphertexts corresponding to the same message. However, for illustrative
purposes, we will also consider some schemes with deterministic encryption
such as plain RSA discussed in
8.3.2
.
3. There is a more general definition that includes the possibility of a probabilis-
tic decryption algorithm but we will not need it. On the other hand, although
a negligible decryption error is allowed by the definition, we will henceforth
tacitly assume that no such error occurs in practice, so that we always have
Dec
(
,
(
,
))
=
m
.
4. We have not specified what the plaintext space is. In practical applications it is
desirable to make it independent of the key but using a key-dependent message
space is also possible provided there are efficient ways to encode and decode bit
strings as elements of the message space.
sk
Enc
pk
m
8.2 Security for Public-Key Encryption
The definition of public-key encryption scheme must be completed with a suitable
definition of security. In the public-key setting there is an important additional con-
cern that did not arise in private-key cryptography, namely how to ensure the secure
distribution of public keys. Indeed, an active adversary tampering with communica-
tion between the honest parties might replace the public key of some user, say Alice,
with her own public key, allowing her later to recover encrypted messages addressed
to Alice. Thus, if Alice and Bob want to prevent such attacks, they will have either to
share some information in advance or to rely on some trusted third party. The latter
solution is clearly more convenient and is the one usually adopted; we will discuss
it when studying digital signatures and for now we will just assume that the users
of a public-key encryption scheme have legitimate copies of the public keys of the
remaining users (or, at least, of the receivers of the messages they send).
