COMP3632 Assignment 3

$30.00

Category: You will Instantly receive a download link for .zip solution file upon Payment

Description

5/5 - (5 votes)

Written assignment
1. We have four data privacy techniques:
1. k-anonymity
2. Differential privacy
3. Secure multiparty computation
4. Private information retrieval
For each scenario below, discuss whether each of the four data privacy techniques would
be suitable to resolve the challenge, and explain why.
(a) [4 points] You want to buy a new smart device to encourage a healthy lifestyle by
measuring your calorie intake. Specifically, you want to be able to look up the
nutritional information of any food using your device at any time. However, you
are reluctant to reveal your personal eating habits to the company that owns the
device. A new company making these smart devices is willing to use a data privacy
technique to protect your privacy.
(b) [4 points] You are curious to know if your friend is earning more money than you
are, but both of you are too embarrassed to reveal your salary to anyone. You know
he is willing to cooperate with you in finding out an answer, though.
(c) [4 points] You are about to start a new company, and you would like to purchase
its web domain as the company’s website. However, you are aware of the practice of
cybersquatting; people may purchase the domain first if they know it is in demand,
and sell it to you at an elevated price. You want to know if the domain is still
available, but you are worried that attempting a DNS query for the domain will
lead to some DNS servers purchasing it immediately for cybersquatting. Some DNS
servers recognize your need and will cooperate with you if you can identify a useful
data privacy technique.
(d) [4 points] A social media company is offering a monetary reward for a challenge:
design the best algorithm that can identify which people should be friends, based
on their real-life habits, online usage patterns, interests, and other personal data.
They want to use the algorithm to improve their friend recommendation service.
However, they are aware that simply releasing everyone’s raw data is a violation of
their privacy.
Assignment 3 Due: 30th Nov, 2018 (Fri)
2. A certain company backs up its data every day, at 11:59 PM. Every Sunday, a full
backup is performed; partial backups are performed on the other weekdays. Every
Monday, Wednesday, and Friday, there will be a differential backup. Every Tuesday,
Thursday and Saturday, there will be an incremental backup.
For simplicity, assume that the data consists of D files of the same size. On each day, a
small percentage p of the files is changed. If a file is changed, the entire file will need to
be stored in the backup (it will not be subdivided into chunks, unlike rsync).
(a) [2 points] Assume that no file is changed twice during a week. Calculate the amount
of storage required for each of the seven backups for the week, given in terms of p
and D.
(b) [2 points] Now, assume that a file can be changed twice. A file, if changed twice or
more, will never return to its original state. Which of the above answers, if any, is
expected to be different at the mean? Show your workings.
(c) [2 points] Which partial backups cannot be corrupted if we want to be able to
restore to the data at Saturday 11:59 PM?
3. Assume the following numbers describe the Bitcoin ecosystem:
I. The size of each block is at most 1 MB (= 1,048,576 Bytes), and there is exactly 1
block per 10 minutes. The reward for a successful block hash is 6 bitcoins.
II. Each transaction is at least 166 bytes in size. A block may contain nothing but
transactions.
III. In total, all miners produce 1020 hashes per second. All miners cooperate to ensure
that no two miners will attempt the same hash.
IV. It costs $8,000 to buy a mining device to produce 1016 hashes per second, and
$0.002 to run it per second for every miner.
(a) [2 points] What is the minimum price of a bitcoin such that miners avoid making
a running loss using the given mining device, if there are no transaction fees?
(b) [2 points] What is the maximum number of transactions per second?
(c) [2 points] Now, suppose that the price of a bitcoin stays the same as your answer
in (a), but the reward for a successful block hash has been halved to 3 bitcoins.
What is the mean transaction fee (in $) required for each transaction so that miners
continue to avoid making a running loss? (Show your workings clearly so that an
error from (a) or (b) will not affect your marks for this part.)
(d) [2 points] Suppose the price of a bitcoin is fixed at $2,500, there are no transaction
fees, and the reward for a successful block hash is still 6 bitcoins. What is the
minimum number of Bitcoin mining devices you would need to buy and run to earn
at least $1,000,000 profit in 365 days? Note that your purchases here will affect
the total hashing rate above in (III). (The cost of purchase and the cost of running
should both be counted as loss.)
Assignment 3 Due: 30th Nov, 2018 (Fri)
Programming assignment
Error Correcting Codes [45 points]
Error Correcting Codes (ECCs) can be used in unsafe transmission or storage devices to
improve reliability by providing redundancy. Unlike checksums, ECCs can automatically
correct errors up to a certain number of bits. In this question, you will be asked to
implement the general Hamming code, which can correct any 1-bit error in a general
string. The specifications of the Hamming code are as follows.
1. Write the input data string as a bitstring according to ASCII.
2. Choose enough parity bits and intersperse the data bits with parity bits, so that
the i-th parity bit pi
is followed by exactly 2i−1 − 1 data bits. Denote the i-th bit
of H as Hi
. Denote the length of H as |H|.
3. Let B(x) be the bitstring representation of the integer x, for example, B(5) = 00101.
4. Define each Mi to be a set of specific bit positions in H, such that Mi
is the set of
integers 1 ≤ x ≤ |H| where the i-th least significant bit of B(x) is 1.
5. Set the parity bit pi to be the XOR of all the bits of H in the positions indicated
by Mi
, except i itself:
pi =
M
x∈Mi\{i}
Hx
Here is a more detailed explanation of Mi
. Consider the integer x = 10, so B(10) is
1010. Then the 1st least significant bit is 0, the 2nd is 1, the 3rd is 0, and the 4th is 1
(reverse the bitstring). So x belongs to M2 and M4, not to M1 and M3.
To work out an example:
1. The input data string is “ab”, which becomes 0110000101100010 (16 data bits).
2. We need five parity bits, p1, p2, p3, p4, p5, as follows:
H = p1p20p3110p40001011p500010
p5 can be followed by up to 15 data bits, but we ran out of data bits, so we stopped
there. H3 = 0 and H8 = p4. |H| = 21.
3. For example, B(20) = 10100.
4.
M1 = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21}
M2 = {2, 3, 6, 7, 10, 11, 14, 15, 18, 19}
M3 = {4, 5, 6, 7, 12, 13, 14, 15, 20, 21}
M4 = {8, 9, 10, 11, 12, 13, 14, 15}
M5 = {16, 17, 18, 19, 20, 21}
Assignment 3 Due: 30th Nov, 2018 (Fri)
5.
p1 = H3 ⊕ H5 ⊕ H7 ⊕ H9 ⊕ H11 ⊕ H13 ⊕ H15 ⊕ H17 ⊕ H19 ⊕ H21 = 0
p2 = H3 ⊕ H6 ⊕ H7 ⊕ . . . = 1
p3 = H5 ⊕ H6 ⊕ H7 ⊕ . . . = 0
p4 = . . . = 1
p5 = . . . = 1
(a) [15 points] Write a program that will automatically generate the correct parity bits
for any input string. The input string will be the first argument of the program.
Your program, called a3a, should write the parity bits in the correct order to stdout
(e.g. cout or print) as characters, ”0” or ”1”. Continuing the above example, if
the program is called with:
./a3a ab
The program should display:
01011
(b) [20 points] Write a program that will automatically correct any one-bit error in
either the parity or the data string. The parity will be the first argument of the
program, and the data string will be the second argument of the program. Your
program, called a3b, should output the corrected parity bits to the first line of
stdout, and the corrected data string to the second line of stdout. If there is no
correction to be made, you should still output the original parity bits and the data
string. For example, if I run your program with:
./a3b 01011 ac
Your output should be:
01011
ab
The program will always be tested with the correct number of parity bits, and there
will either be a one-bit error in the parity or the data string, or no error. Either
type of error should be fixed. Also, note the meaning of an ASCII one-bit error:
“a” (01100001) can become “i” (01101001), but “a” cannot become “b” (01100010)
because that would be two bit flips.
(c) [10 points] Submit two sentences in files sentence1 and sentence2, such that they
have the same Hamming code (as output by part a). They should all be logical and
grammatically correct sentences with no typos, and they should all include your
@connect.ust.hk username. Any ASCII characters that are not letters, numbers, or
basic punctuation will be removed.
Hint: It may be easier to construct these sentences if you use numbers somewhere
in your sentence. Keep in mind that you should not look at anyone else’s sentence,
so there shouldn’t be a case where two students submit similar sentences.
Assignment 3 Due: 30th Nov, 2018 (Fri)
(d) [15 points (bonus)] Examine my program sendmoney.py, wherein a money transfer
agent uses Hamming code for message authentication against an adversary. This is
not good, even if the Hamming parity bits are delivered through a secure channel.
sendmoney.py uses your answer in (a) to check if the Hamming parity bits are
correct. (Call it with -c if you wrote in cpp, -j if you wrote in java, and -p if you
wrote in python. You need to compile the code yourself according to the instructions
on the next page.)
Imagine I have constructed a message “taowcse sends $1000000 to taow2”, for which
the correct Hamming parity bits are “100100110”. I call the money transfer agent
and tell them the correct parity bits. Then, I sent a packet with the message to
the money transfer agent, represented by a file called message. Then, the money
transfer agent executes:
python sendmoney.py -c/j/p 100100110 message
The output will be:
taowcse successfully sends $1000000 to taow2!
If the message is wrong, the output will be:
Hamming code check failed. Money transfer aborted.
Your objective is to change the file fakemessage, so that when the command python
sendmoney.py -c/j/p 100100110 fakemessage is run, you should see:
taowcse successfully sends $1000000 to !
Replace above with your correct @connect.ust.hk username. Do
not change either sendmoney.py or the parity bits; in this scenario, you are
only able to intercept the message file I sent to the money transfer agent.
Assignment 3 Due: 30th Nov, 2018 (Fri)
Submission instructions
All submissions should be done through the CASS system. Submit the following programs:
• a3.pdf, containing all your written answers.
• Files for the programming assignment: sentence1, sentence2, fakemessage (bonus).
• Code for the programming assignment, detailed below:
For the programming assignment, submit your code; do not submit any compiled files.
C++: Submit a3a.cpp, a3b.cpp. I will compile them and call ./a3a .
Python2: Submit a3a.py, a3b.py. I will call python a3a.py .
Java: Submit a3a.java, a3b.java. I will compile with javac a3a.java and then call java
a3a .
If you are writing in Python, please use Python2 instead of Python3. If you really want
to use Python3, please e-mail me so I can accomodate that.
If there is a Makefile in your folder, the Makefile will override all of the above. This
implies if you are not writing in C++, Python2, or Java, you must include a Makefile.
Keep in mind that plagiarism is a serious academic offense; you may discuss the assignment, but write your assignment alone and do not show or send anyone your answers and
code.
The submission system will be closed exactly 48 hours after the due date of the assignment. Submissions after then will not be accepted unless you have requested an extension
before the due date of the assignment. You will receive no marks if there is no submission
within 48 hours after the due date.
Assignment 3 Due: 30th Nov, 2018 (Fri)