Cryptography Reference
In-Depth Information
Alice works on a top-secret assignment and needs a forged diplomatic passport
in her cover name. Home Secretary Bob has to sign her passport, but must
not learn her valid cover name. Alice sends him ten passports, each issued to
a different name. Bob randomly selects nine and checks whether they are in
order. He signs the tenth by the completely blind signature method. If Alice
submits a passport with illegal authorities, then the chances are 9:1 that she
will get caught.
Intensive research work on blind signatures is being done, and some are
patented by Chaum in the USA. Section 6.6.7 describes a practically relevant
use for blind signatures.
6.6.4 Zero-Knowledge Proofs
Similar mystery-mongering as with blind signatures is involved in a type of
protocol called
zero-knowledge proof
. Alice would prove to Bob that she owns
certain information without telling him what this information is. Naturally, the
protocol depends on the specific problem. Alice could even publish hints about
her secret so that every doubter will eventually be convinced of her knowing
the secret, whereas Alice doesn't disclose a single bit of that secret. This variant
is called
non-interactive zero-knowledge proof
.
As unbelievable as this may sound, you know an example: Alice wants to make
believe she knows the two prime factors of a 1024-bit number. To this end, she
constructs a public - private key pair and uses her private key to decrypt a text
not
selected by her, similar to digital signatures. She publishes the 'plaintext'
thus created together with the public key. Everybody can do reverse ciphering
to convince themselves that Alice knows the private key and with it the two
prime factors, as we saw in Section 4.5.3.
We will see a practical use in Step 5 of the authentication protocol of Secure
Shell SSH in Section 7.3: Bob gives Alice a 256-bit random number he had
encrypted with her private key. Only Alice can reverse-calculate this number.
To prove it, she sends Bob a hash value from this number (and not the number
itself to make sure Mallory won't get a chance).
However, zero-knowledge protocols normally work
interactively
. In a chal-
lenge - reply scenario, the probability that Alice really knows a secret tends
towards 1 as the number of her replies grows.
There are much more sophisticated protocols; you can find some in [SchnCr,
5.1], but you have seen what we are talking about.
