Question 1 (5 marks): (Cryptographic Hash Functions) Consider the
following proposal for a hash function h. Let p be a large prime and let g be
a generator mod D. Represent messages as sequences x= I1.22….2. where
the 2; are numbers mod p. We define the hash of such a message I by h(2) =
gitrat…+In mod p.
1. (2 marks) Show that this hash function is good for use as a message digest
for error correction purposes, in the sense that it has a high probability of
detecting errors if messages a are transmitted in the form (I, h(2)), and
a message (2, y) that is received is treated as correct if h(z) = v.
In particular, for concreteness, suppose that the messages Alice will be
sending are all of length two (2 = 21, 22), and are generated uniformly at
Suppose also that we know that communications channel that we are us-
ing contains occasional bursts of random noise (e.g.. from sunspots on
a radio channel) that may potentially damage every bit of the message
(I, h(z), including the hash. When Alice sends a message (2, h(2)), with
probability p, the channel delivers the message to Bob exactly as trans-
mitted. With probability 1
D. the channel delivers to Bob a message
(y,z) selected uniformly at random, where y = y1, 42 and y1, y2, 2 are all
numbers mod p. (The channel never delivers a message to Bob if Alice
Question 2 (5 marks): (Digital Signatures) Suppose that h is a hash
function taking long messages as input and producing 256 bit outputs and that
M is a long message. Consider the following idea for constructing a signature
A private signature key K, is a pair of randomly generated sequences
21, …, 2236 and y1, …, Y256, both of length 256, where each value I; and yi
is a 256 bit message.
• The corresponding public verification key K, is the pair of sequences
h(21), …,h(2256) and h(y1), …, h (4256)
To sign message M, where the hash h(M) is the sequence of bits bj…b256,
define sign(M, Ks) = (M, 21…2256) where z; = 2; if b; = 0 and 2; = y: if
1. Explain how you could verify this signature is correct: what does the ver-
ification function V(K , (M,r, …r256)) do to check that (M, r1 …r256)
is message M signed using the signature key corresponding to Kr
2. Explain why this scheme is secure – why is it hard for an attacker to forge
a signed document that passes the test? Clarify what assumptions on the
hash function are needed for your argument.
Question 3 (5 marks): (Monetary Supply Laws) One of the ways in
which currencies (both standard and crypto.) differ is in their rules concerning
how money is created. Different rules have different economic consequences
and incentivize users and investors in potentially complex ways. One important
economic metric is the inflation rate, which is the annual rate at which the
cost of goods and services increases. As we have experienced in recent years,
the factors impacting inflation are diverse and unpredictable, and may include
pandemics, wars and catastrophic weather events. However, it is clear that one
of the main reasons for the presently high inflation, and its consequences on
people’s lives, is the amount of new money that was created by central banks
during the pandemic. Central bank doctrine in recent decades has been that
deflation (decreasing cost of goods over time) is bad, because people tend to
hoard money rather than spend, since they know they can buy the same goods
cheaper later, and this causes unemployment as the economy grids to a halt.
On the other hand, nobody likes high inflation when wages are fixed. Many
central banks take the view that 2-3% inflation is socially optimal.
In this question, we focus on the monetary inflation rate r as a proxy? for
price inflation. For a given period, this rate is defined as r = (M’
where M is the amount of money in existence at the start of the period and M’
is the amount of money in existence at the end of the period.
Cryptocurrencies use a number of rules to determine how much new money
is created per block. In this question, we calculate the consequences for the
monetary inflation rate. Let It be the amount of new money issued in the k-
th block, so that Io is the amount of money issued in the genesis block of the
cryptocurrency. Write Mr for the total amount of money that has been issued
in the first & blocks. That is, Me = Io
+ It. Thus, the rate of inflation in
the k + 1-th block is Tr+1 = (Mr+!
(a) (A Bitcoin-like supply law, with halving) Suppose that Io = 2N
Write a closed form solution for Mt. in terms of V, and use this to derive
an expression for the rate of inflation **+1 in the k + 1-th block.
(b) (An Ethereuml.O-like supply law) Suppose It+1
= c, where c is a
constant. Write a closed form solution for M;. in terms of Io, and use this
to derive an expression for the rate of inflation *k+1 in the k+ 1-th block
(c) In case (b), what happens to re in the limit, as / + 00?
(d) (A supply law that pays interest to savers/stakers) Suppose that
in each period, a fraction S of the total amount of money is saved, and
new money is created by paying interest at a fixed rate R to the savers.
(The interests is a reward for making available the saved money for som
socially productive purpose. In “proof of stake” cryptocurrencies, the
savers are the stakers, and the socially productive purpose is the work
done by them to secure the currency.) That is /k+1 = M.SR. Write
a closed form solution for Mt in terms of lo, and use this to derive an
expression for the rate of inflation **+1 in the & + 1-th block.
(e) In case (d), what happens to re in the limit, as / + 00?
(Hint: one of the lecture slides shows an approach to finding a closed form, not
involving a summation,
Is it sate to use the same private key to sign more than one message?
not, explain what an attacker could do to attack a user who does this.
(3 marks) Which of the three properties of cryptographic hash functions
(pre-image resistant, second pre-image resistant, and collision-free)
satisfied by the function h? Explain your answers. In case you say that
the property is satisfied, give reasons to believe that it is. In case you say
that the property is not satisfied, give a proof that that it is not satisfied
(i.e., explain how an attacker could efficiently do what the property says
cannot be done efficientlv)