Cryptography Reference
In-Depth Information
Public-key encryption schemes secure against a-posteriori-chosen ciphertext attacks
can also be constructed under the same assumption [64], but this construction is even
more complex.
In fact, both constructions of
public-key
encryption schemes secure against cho-
sen ciphertext attacks are to be considered as plausibility results (which also offer
some useful construction paradigms). Presenting “reasonably efficient” public-key
encryption schemes that are secure against (a posteriori) chosen ciphertext attacks,
under widely believed assumptions, is an important open problem.
5
B.1.4. Some Suggestions
B.1.4.1. Suggestions for Further Reading
Fragments of a preliminary draft for the intended chapter on encryption schemes can
be obtained online [99].
In addition, there are the original papers: There is a good motivating discussion
in [123], but we prefer the definitional treatment of [92, 94], which can be substantially
simplified if one adopts non-uniform complexity measures (as done above).
6
Further
details on the construction of public-key encryption schemes (sketched above) can be
found in [123, 92, 35, 5]. For discussion of non-malleable cryptography, which actually
transcends the domain of encryption, see [64].
B.1.4.2. Suggestions for Teaching
We suggest a focus on the basic notion of security (treated in Sections B.1.1 and B.1.2):
Present both definitions, prove their equivalence, and discuss the need to use
random-
ness
during the encryption process in order to meet these definitions. Next, present all
constructions described in Section B.1.2. We believe that the draft available online [99]
provides sufficient details for all of these.
B.2. Signatures: Brief Summary
Again, there are private-key and public-key versions, both consisting of three efficient
algorithms:
key generation
,
signing
, and
verification
. (Private-key signature schemes
are commonly referred to as
message-authentication schemes
or
codes
(MAC).) The
difference between the two types is again reflected in the definitions of security.
This difference yields different functionalities (even more than in the case of en-
cryption): Public-key signature schemes (hereafter referred to as signature schemes)
can be used to produce signatures that are
universally verifiable
(given access to the
public key of the signer). Private-key signature schemes (hereafter referred to as
message-authentication schemes) typically are used to authenticate messages sent
5
The “reasonably efficient” scheme of [57] is based on a strong assumption regarding the Diffie-Hellman key
exchange. Specifically, it is assumed that for a prime
P
and primitive element
g
, given (
P
,
g
,
(
g
x
(
g
y
mod
P
)
,
mod
P
)
,
(
g
z
mod
P
)), it is infeasible to decide whether or not
z
≡
xy
(mod
P
−
1).
6
We comment that [92] follows [94] in providing a uniform-complexity treatment of the security of encryption
schemes.
