18 Public-Key Cryptography and Provable Security
The only assumption we make on the distribution of m is that it be stochastically inde-
pendent of the distribution of K. Then for any elements
e
m,
e
c ∈ G, we have
Pr[m =
e
m | c =
e
c] = Pr[m =
e
m | K =
e
c − m] = Pr[m =
e
m]
because K has independent uniform distribution. This means that, if K is kept secret, an
adversary who observes some ciphertext c cannot learn any information whatsoever on m
from it: the Vernam encryption scheme is information-theoretically secure.
A caveat is that this result only holds if keys K are perfectly random. In implementations,
there will usually be some bias. However miniscule it may be, this means that ciphertexts
will reveal at least a tiny amount of information on the corresponding plaintexts. Typically
the bias will be small enough so that it does not really matter at all, and no-one will know
the details about the bias that would be necessary to exploit it; we should just keep in mind
that perfect information-theoretic security remains a mathematical utopia an epsilon away.
2.2 Public-Key Cryptography
In asymmetric or public-key cryptography ([32], [33]), there is no longer a single key shared by
the parties that are involved. Instead, the key generation algorithm produces multiple keys
that are associated with another: usually, there is a secret key that should be known only to
a single entity, and a public key that may be made known to everyone.
One form of public-key cryptography is public-key encryption, where someone’s public
key can be used to encrypt plaintexts such that the resulting ciphertexts can be decrypted
using the corresponding secret key. Another important form of public-key cryptography
are digital signature schemes: the entity holding the secret key can use it to “sign” digital
documents by computing a value, a “signature”, such that anyone who knows the public key
can verify whether the signature is valid for a given message. Also various other scenarios for
cryptographic protocols are known that belong into the area of public-key cryptography. We
will focus on public-key encryption and specific closely related notions and not go into the
details of digital signatures or other protocols.
A concept related to public-key encryption is the notion of a key encapsulation mecha-
nism (KEM; see [80]). As in public-key encryption, someone’s public key is used to create a
ciphertext from which a plaintext can be recovered using the associated secret key. Unlike for
public-key encryption, the sender does not get to specify an arbitrary plaintext when creating
the ciphertext; instead, the randomized “encryption” algorithm outputs both the plaintext
and a corresponding ciphertext. This approach is appropriate for use in cryptographic pro-
tocols where the plaintext is intended as a key for symmetric cryptography – hence the term
key encapsulation.
Note that both symmetric and public-key encryption schemes can be randomized: encrypt-
ing a given plaintext for a constant key does not necessarily yield a unique result. However,
encryption followed by decryption has a deterministic result, namely the original plaintext;
this is in contrast with KEMs. (The variant of public-key encryption that we will consider in
chapter 4 is an unusual exception where decryption yields the original plaintext padded with
some additional data, which is determined while encrypting. In that public-key cryptosystem
with length-expanding decryption, the result of encryption followed by decryption is partially
deterministic and partially pseudo-random.)
我的内容管理
展开
