Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP6451 T1 2021
Submissions: Submit your solutions as a pdf or text file via the course
moodle page. Your submission must be your individual work - UNSW rules
concerning this will apply (see the Course Outline). Turnitin will be used
to perform similarity checks. In general, these are short answer questions —
aim to keep your answers brief but precise. Answer all parts, and show your
working.
Question 1 (Money, debt, and a reason some people worry about
fiat money and prefer Bitcoin):
In Australia, the Reserve Bank of Australia (RBA) is responsible for
creating fiat money, in a number of forms that include coins and (plastic)
notes. Similar organisations play this role in money other countries, e.g.,
the Federal Reserve in the USA. However, private banks (e.g., in Australia,
the Commonwealth Bank, ANZ, Westpac and NAB) also play a role in the
creation of fiat money. This works as follows.
For the purposes of the exercise, we assume that there are just two private
banks, creatively called “bank A” and “bank B”. Suppose an initial state
where just one rich person (Uncle Scrooge) has all the money (coins and
notes) that has been issued by the RBA: $1 billion. There are other rich
1
people, of course, but they are holding their wealth in forms other than
money: gold mines, development sites, buildings, houses, etc. The two banks
have also just opened for business, so they don’t have any money yet, but as
we will see, they are in a nice profitable line of business. Everyone else has
to survive by working for a rich person, or by borrowing from a bank.
Luckily, bank A soon has plenty of money to lend: Scrooge has everything
he needs already, and is afraid of robbers, so he deposits his money in bank
A. The bank credits Scrooge’s account for $1B, and everyone else has $0 in
their account at their chosen bank. From from the bank’s perspective, the
$1B coins and notes now in its vaults is an asset, but it is balanced by a
liability : in effect, the bank owes Scrooge this money, and he can request a
withdrawal of his money any time he likes. Using the equation
Equity (net worth) = Assets− Liabilities
we see that bank A’s equity is $1B - $1B = 0. The bank didn’t get rich all
of a sudden because of Scrooge’s deposit!
In practice, rich people prefer to collect interest on their deposits, and
don’t spend much, so they tend to leave their money in the bank, and with-
draw only small amounts. The bank exploits this fact to start making profits
by lending some of the deposits out, and collecting interest as a result as
the money is paid back. (Some of that covers interest due to be paid to
Scrooge, but the bank charges borrowers a higher interest rate than they pay
to Scrooge, so they make a nice profit along the way.)
The RBA regulates banks based on this behaviour. It would be a disaster
if the bank had lent out all of Scrooge’s money and then Scrooge came to
make a withdrawal because he wants to buy a maxi-yacht. The bank wouldn’t
have the cash, and go out of business from this default on its obligations. So
the RBA requires that banks hold enough cash “in reserve” in their vaults so
that they can pay out the expected amount of withdrawal requests. Suppose
that this “reseverve ratio” is r ∈ (0, 1): if a bank has $X cash it is permitted
to lend out up to $(1− r) ·X, but must keep at least $r ·X in its vaults to
cover potential withdrawals.
Let’s say that bank A lends out the $(1 − r) · 1B to Alice for her gold
mining project, and Alice uses it to buy a gold mine and equipment from
Bob, who deposits this money in bank B. How much “money” is there now
in the economy? One way to answer this is to ask how much money people
have in their bank accounts. Well, Scrooge has $1B in his account at bank A,
2
and Bob has (1− r) · $1B in his at bank B, so there is now (1 + (1− r)) · $1B
total in people’s bank accounts. (Of course, some of them have to pay it
back over time, but for the moment, this is money that could potentially be
spent on goods and services.) The total amount of notes and coins in the
economy is still the same. Bank A has $r · 1B worth, and $(1− r) · 1B has
just been transferred to bank B, for a total of $1B.
(a) Of course, the story does not end here. Bank B would like to make
some money by collecting interest from loans as well, so it lends out
some of the cash it now has in its vaults to Carol for her project to
build student apartment towers. If it follows the RBA’s rules about
keeping money in reserve, what is the maximum it can lend to Carol?
(b) Carol takes her maximum size loan and uses the money to buy a de-
velopment site from Arthur, who deposits the money in bank A. What
is the total amount of deposits now in the banking system?
(c) After receiving Arthur’s deposit, how much money is bank A able to
issue in new loans? (Don’t count the loan already made to Alice!)
(d) Suppose this story is continued ad infinitum, with a bank making max-
imum size loans at each step, and the money lent being deposited in
the other bank. How much money in total is in people’s accounts in
the limit? Express this as simply as you can, and explain your answer.
(Hint: there is an equation somewhere in the slides for weeks 1-2 that
helps with this question.)
(e) Suppose this story has been proceeding for a few years. What would
happen if there was suddenly a pandemic, and Scrooge and the other
rich people who had sold their gold mines and development sites and
houses etc., started to worry that there would be mass unemployment
and many of the people who had borrowed money would not be able
to repay their loans? What might this have to do with the following
diagram from the RBA?
3
Question 2: (Public Key Encryption) Both RSA and Elliptic Curve
encryption require us to compute exponentials in some group G. Let ∗ be
the operation in this group, and write 1 for the unit of the group. For m
an element of the group, and e a natural number, the most obvious way to
compute me = m ∗m ∗ ... ∗m (e copies of m) is the following:
r = 1;
for i = 1..e do r := r*m
return r
(a) When e is a number of 2048 bits, as is typical with RSA keys, what
is the maximum number of group operations (∗) required by this algo-
rithm?
A more efficient way to compute me is the following
1. Write e in binary, as bk, . . . , b0, where b0 is the least significant bit.
2. Let p be an array of group elements of length k + 1;
4
3. p[0] := m ;
4. for i = 0..k − 1 do p[i + 1] := p[i] ∗ p[i];
5. r := 1 ;
6. for i = 0..k do { if bi then r := r ∗ p[i] }
7. return r
Explain how this algorithm works as follows:
(b) Give the loop invariant for the loop in step 4, in the form of a general
statement about p[0]...p[i] that holds while the loop is running. Explain
why the body of the loop maintains this invariant.
(c) Give the loop invariant for the loop in step 6, in the form of a general
statement about p, r, i and the bj that holds while the loop is running.
Explain why the body of the loop maintains this invariant.
(d) Use the answer to (c) to show that the algorithm returns the correct
answer me.
(e) What is the maximum number of group operations performed by this
algorithm when e is a number of 2048 bits?
Question 3 (Hash Functions): Suppose that we have a list of files f1, f2, . . . , fn
that have been timestamped using the Haber and Stornetta scheme discussed
in lectures. That is, for a cryptographic hash function h, and a value v0 from
the previous period, we compute a sequence of values
w1 = h(f1) v1 = h(v0||w1)
w2 = h(f2) v2 = h(v1||w2)
...
wn = h(fn) vn = h(vn−1||wn)
Assume that only the values v0 and vn have been published in the paper, on
days d0, d1, respectively. The number of files included in any period may be
arbitrary, it is not required to be equal to n. To prove existence of a file fi
in the interval [d0, dn], we can present the following information: the file fi,
the index i, and the sequence of hash values w1, . . . , wn.
5
(a) (2 marks) What computation should a verifier of the claim that the file
existed in the interval perform? Assume that the verifier is able to look
up the values v0 and vn in the newspaper.
(b) (3 marks) Suppose that Mallory has a file f that is not in the set
{f1, . . . , fn}. In an attempt to cheat, and fraudulently convince the
verifier that file f existed in period [d0, d1], Mallory needs to present
data of the form f, i, w′1, . . . , w
′
m for some m, which passes the test
from part (a). Prove that it is difficult for Mallory to do this. Explain
carefully what properties of the hash function you rely upon for the
proof.
Question 4: (Signatures and Digital Notes) Alice has an account at
Bob’s bank. Alice would like to withdraw $10 from her account to use for her
internet shopping. Alice would like to get Bob to sign a message m that says,
intuitively, “Bob will pay $10 to the first person to present this message.” Of
course, if Bob issues many such messages, then there is no way to tell them
apart, and people might start presenting such messages to the bank multiple
times, losing the bank a lot of money. To fix this, we can include a serial
number N in the message, so that it says
“This is note number N . Bob will pay $10 to the first person to
present this message.”
Let m(N) be the above message. The idea is that before Bob signs this
message, and gives it to Alice, he will record N in his database of notes
issued. If someone presents the message to Bob, he pays the $10, but updates
the database to record that this note has already been presented, and is no
longer valid.
This, however, presents a risk to Alice’s privacy. If she spends the note
on goods being sold by Victor, the vendor of “Very naughty products”, and
Victor then presents the note to the bank, then Bob will learn that Alice has
shopped with Victor. (Victor, if he is wise, will rush the note to the bank,
to make sure that Alice has not sent a copy to someone else already, and will
not ship the goods to Alice before he has been paid by the bank.)
To get around this risk to her privacy, Alice invents a way to obtain a
note signed by the bank, that contains a random serial number created by
Alice, without Bob learning what the serial number is. (As above, Bob, will
6
keep a record of which serial numbers he has paid out, to prevent people
claiming payment twice on the same note.) Let KB = (e, n) be Bob’s RSA
signature verification key, known to Alice, and let K−1B = (d, n) be Bob’s
private signature key, known only to Bob. Bob signs a message m using the
function SK−1B
(m) = (m,md mod n).
Suppose that messages are represented as a number mod n, where n is
the modulus in Bob’s signature verification key. Alice generates a random
number r mod n, and a random serial number N , and asks Bob to sign the
message mr = r
e × m(N) mod n. Note that Bob cannot tell what m(N)
is, since it has been mixed up with some random noise re. Bob signs this
message mr, and returns the result SK−1B
(mr) = (mr, (mr)
d mod n) to Alice.
(a) Show that Alice is now able to efficiently compute SK−1B
(m(N)), even
though she does not have Bob’s signature key K−1B . This means that
Alice then has the signed message that she wanted, without Bob learn-
ing the number N that allows him to trace the note back to Alice. (It
may be necessary to add some constraints to the definitions above. If
so, say what these are.)
(b) Bob starts to get worried, and has second thoughts. He does not know
what he is signing. For all he knows, Alice could be sending him the
message “Bob promises to pay Alice $1,000,000” to sign using the above
technique. To protect himself from being cheated like this by Alice, he
decides to “audit” Alice to keep her honest. Rather than signing every
message sent to him by Alice, he requires Alice to send him multiple
versions
re1 ×m(N1) mod n
re2 ×m(N2) mod n
- 经济Economics
- 金融Finance
- 会计Accounting
- 工商管理Business Management
- 计算机computer science
- 商业分析business analysis
- 法律Law
- 管理Management
- 市场营销Marketing
- 哲学Philosophy
- 心理学Psychology
- 物理Physical
- 统计学statistics
- 电气工程electric engineering
- 化学chemistry
- 生物biology
- 数学mathematics
- 语言学linguistics
- 土木工程civil engineering
- 工程力学engineering mechanics
- 艺术art
PROFESSIONAL HELP!
在线咨询
立即下单
Wechat：THEend8_ 
Email：