Fundamentalsof Cryptography

Foundations of Cryptography

Assignment - I

Question 1

Alice discovers a very simple chemical compound that preforms an important neurological function. She wants to ensure she is credited with this discovery, but she also wants to keep it secret for some time in order to file patents and commercialize it. She decides that instead of publishing the compound, she will publish y on her website where y = H(m∥r) for secure hash function H, the name of the compound m, and a 128 bit string r where the bits are selected randomly. A few weeks later, Carol discovers the same compound and publishes the name of it. Alice wants to prove she found it first and reveals m and r.

(a) (1 mark) Why does publishing only y protect m from being disclosed?

Answer:

Hash Function is One-Way Function and it is hard to invert. So it is infeasible to find any input “m (compound)” where y = H(m∥r), the name of the compound m, and a 128 bit string r (bits are selected randomly).

(b) (1 mark) Assume Bob sees y on the day it is published. Later, after Carol publishes the compound and Alice published m and r, why is Bob convinced that Alice knew about the existence of this compound first? In other words, why is not possible that Alice pretended to find a compound and then when Carol found one, she just claimed that she was thinking about the same one that Carol found?

Answer:

Alice is already published y on her website; if she released the values of m and r, with the help of hash function we can find the value – y and match with the value which is already published on her website - y, because Hash function will generated the same value for the pre image m.

(c) (1 mark) Assume Alice used only 28 bits of randomness instead 128 in r. Why or why not is this problematic?

Answer:

It is easier to find the pre-image m that is problematic, because of 28 bits of randomness instead of 128 bit as hash function is exhaustive search.

(d) (1 mark) Assume a clever cryptographer found an...