Alice has a piece of information that is valuable for the next 3
hours. She offers to let Bob know the information if he pays her $100.
 Bob knows the general nature of the information (but not its details)
and, if he could actually see it, he would immediately recognize that
it is indeed valuable (and certainly worth $100 to him).  But Bob has
only $5, and so he suggests to Alice that, in return for paying her
$5, they engage in a protocol in which he has a 5% chance of getting
the information.  Design a protocol that achieves this and is such
that (i) no cheating by Bob is possible, and (ii) after 3 hours have
passed Alice can prove to Bob that she did not cheat when the protocol
was perfomed 3 hours earlier.

Hi eksolutions,

I presume you want a protocol that is capable of being implemented on
a computer. But first, let's consider how we would achieve the same
objective using a manual protocol.

Here's how it could work:

Alice writes the valuable information on a piece of paper, and puts
the piece of paper into an envelope. She puts this envelope together
with 19 empty envelopes, and shuffles them all.

Bob pays $5 to Alice, and chooses one of the envelopes. If he chooses
the one with the piece of paper inside, he gains the information.
Otherwise, he gains nothing.

After three hours, all of the envelopes can be opened, and Alice can
prove to Bob that she did not cheat; that one of the twenty envelopes
(5%) did indeed contain the valuable information.

We can adapt this protocol for a computer by noting that a
cryptographic checksum can be calculated for any message. Although a
checksum can be easily calculated for a given message, it is
computationally infeasible (i.e. takes an impractically long time) to
compute a message that would generate a given checksum. Therefore, if
we are presented with a checksum, and later with a message from which
that checksum can be generated, we can be certain that the checksum
was indeed generated from that message.

Here's how the protocol would work:

Alice types the valuable information into a textfile, and generates
its checksum. She also types 19 dummy messages into textfiles, and
generates the checksum for each of those.

Bob pays $5 to Alice, and receives the 20 checksums. Bob chooses one
of them, and Alice presents him with the textfile from which that
checksum was generated. If Bob is lucky, it's the one with the
valuable information, but there's a 95% chance that Bob receives one
of the dummy messages.

After three hours, Alice presents all of the textfiles to Bob. Bob can
generate their checksums, and verify that one of the checksums he saw
three hours earlier did in fact correspond to the valuable
information. If Bob had chosen that checksum, Alice would have had to
give him the valuable information - because Alice could not have
constructed any other textfile to match that checksum.

An example of a cryptographic checksum algorithm is MD5 - the "Message
Digest Algorithm, Version 5":

RSA MD5 Cryptographic Checksum Using DES
http://www.freesoft.org/CIE/RFC/1510/82.htm


Google search strategy:

"cryptographic checksum"
://www.google.com/search?q=%22cryptographic%20checksum%22


Regards,
eiffel-ga