Cryptography Reference
In-Depth Information
him with divorce after
seeing
the car. Unfortunately for Bob (and his family), Alice
has a “no return” policy. Given that she is an experienced car dealer, she knows
too well that it will not be easy to sell a pink and orange car, and she is thus set
on not making any exceptions. Since Bob now claims that he never ordered the
car, she has no other choice but to sue him. In front of the judge, Alice's lawyer
presents Bob's digital car order together with the encrypted version of it. Obviously,
the lawyer argues, Bob must have generated the order since he is in possession of
k
AB
with which the ciphertext was generated. However, if Bob's lawyer is worth his
money, he will patiently explain to the judge that the car dealer, Alice, also knows
k
AB
and that Alice has, in fact, a high incentive to generate faked car orders. The
judge, it turns out, has no way of knowing whether the plaintext-ciphertext pair was
generated by Bob or Alice! Given the laws in most countries, Bob probably gets
away with his dishonesty.
This might sound like a rather specific and somewhat artificially constructed sce-
nario, but in fact it is not. There are many, many situations where it is important
to prove to a neutral third party, i.e., a person acting as a judge, that one of two (or
more) parties generated a message. By
proving
we mean that the judge can conclude
without doubt who has generated the message, even if all parties are potentially dis-
honest. Why can't we use some (complicated) symmetric-key scheme to achieve
this goal? The high-level explanation is simple: Exactly because we have a sym-
metric set-up, Alice and Bob have the same knowledge (namely of keys) and thus
the same capabilities. Everything that Alice can do can be done by Bob, too. Thus,
a neutral third party cannot distinguish whether a certain cryptographic operation
was performed by Alice or by Bob or by both. Generally speaking, the solution to
this problem lies in public-key cryptography. The asymmetric set-up that is inherent
in public-key algorithms might potentially enable a judge to distinguish between
actions that only one person can perform (namely the person in possession of the
private key), and those that can be done by both (namely computations involving
the public key). It turns out that digital signatures are public-key algorithms which
have the properties that are needed to resolve a situation of cheating participants. In
the e-commerce car scenario above, Bob would have been required to digitally sign
his order using his private key.
10.1.2 Principles of Digital Signatures
The property of proving that a certain person generated a message is obviously
also very important outside the digital domain. In the real, “analog” world, this is
achieved by handwritten signatures on paper. For instance, if we sign a contract or
sign a check, the receiver can prove to a judge that we actually signed the message.
(Of course, one can try to forge signatures, but there are legal and social barriers that
prevent most people from even attempting to do so.) As with conventional hand-
written signatures, only the person who creates a digital message must be capable
of generating a valid signature. In order to achieve this with cryptographic primi-
