This page is intentionally left blank.
Please do not open this question set before you are allowed to do so.

4810-1184 Algorithms for Information Security and Privacy (Autumn 2018)
Midterm Problem 1
Suppose that we have a table 𝑇 with the weight information of all persons in a city. We want to use
the Laplacian mechanism to publish the average weight information 𝐴𝑉𝐺(𝑇). However, for now, let
suppose that 𝑓(𝑇) = 𝐴𝑉𝐺(𝑇)/2.
Question 1.1: Calculate the value of 𝐺𝑆(𝑓).
Question 1.2: What is the distribution that the noise we add to 𝑓(𝑇) should be drawn from?
Question 1.3: Discuss why your noise in Question 1.2 should be smaller than when 𝑓(𝑇) = 𝐴𝑉𝐺(𝑇).
Question 1.4: Discuss why, even the noise is smaller, scaling the value of 𝑓 will not help users to havea clearer information.
From next question, we will use the exponential mechanism to privately publish the average weight
𝐴𝑉𝐺(𝑇). Suppose that a publication of the mechanism 𝑝 must be a member of the set{40,50,60,70,80,90}.
Question 1.5: Design a utility function for each 𝑝.
Question 1.6: Calculate the value of Δ𝑈𝑡𝑖𝑙𝑖𝑡𝑦.
Question 1.7: Discuss why, when using your utility function, the exponential mechanism will work
well.
Question 1.8: Discuss why publishing 𝐴𝑉𝐺(𝑇)/2 instead of 𝐴𝑉𝐺(𝑇) will also not work in theexponential mechanism with your utility function. You can assume that, when trying to publish
𝐴𝑉𝐺(𝑇)/2, the possible publication can be {20,25,30,35,40,45}.

4810-1184 Algorithms for Information Security and Privacy (Autumn 2018)
Midterm Problem 2
Suppose that our database 𝑇 has 2 information, chosen party and ages, of all users. Also, forsimplicity, let assume that there is only 2 parties in our country, Melon-pan and Gyu-don. We know inadvance that there will be two queries to our database, which are:1) How many persons choose “Melon-pan” and has age below 30?
2) What is the percentage of persons who is below 40 and choose “Melon-pan” party?
Question 2.1: Discuss why reducing the table 𝑇 to 𝑇′ with the following information:1) chosen party2) if the person ages below 30 (boolean variable)
3) if the person ages below 40 (boolean variable)
will help reducing the computation time of the smallDB algorithm.
Question 2.2: Design a function 𝑓1 for Query 1. Your function must follow the assumption on thefunction for smallDB algorithm discussed in the class.
Question 2.3: Design a function 𝑓2 for Query 2. Your function must follow the assumption on thefunction for smallDB algorithm discussed in the class.
From next question, suppose that 𝛼 = 0.3.
Question 2.4: Calculate the number of records in the published small database, when log 2 = 0.7.
Question 2.5: Calculate the number of possible small tables.
From next question, assume that, the histogram of the table 𝑇′ is as follows:-Number of records with “Melon-pan” and “age below 30” is 500000
Number of records with “Melon-pan” and “age over 30” is 0
Number of records with “Gyu-don” and “age below 40” is 0
Number of records with “Gyu-don” and “age over 40” is 500000

Question 2.6: Calculate the number of possible small table 𝑈 with max[𝑓𝑖 (𝑇 ′ ) − 𝑓𝑖 (𝑈)] = 0.
𝑖

Question 2.7: Calculate the number of possible small table 𝑈 with max[𝑓𝑖 (𝑇 ′ ) − 𝑓𝑖 (𝑈)] = 1/8.
𝑖

Question 2.8: Based on your answer in Questions 2.6 and 2.7, try to a fast algorithm for smallDBalgorithm. By the algorithm, can you reduce the value of 𝛼 to a smaller value?

4810-1184 Algorithms for Information Security and Privacy (Autumn 2018)
Midterm Problem 3
Suppose that we want to publish the percentage of persons choosing Melon-pan party, i.e.
𝑓(𝑇) =#𝑀𝑒𝑙𝑜𝑛 − 𝑝𝑎𝑛||𝑇||.

We know that 𝑓(𝑇) must be between 0 and 1.
Question 3.1: Discuss why Laplacian mechanism can give a number smaller than 0 or larger than 1.
Question 3.2: Discuss why there would not be a privacy problem although the number is not between
0 and 1.
From next question, let consider the case that it is very unlikely to have 𝑓(𝑇) + 𝑛𝑜𝑖𝑠𝑒 smaller than 0or larger than 1. The probability that we have such the case it negligible.
Suppose that there is an attacker who want to know 𝑓(𝑇). The attacker keeps asking from the value𝑓(𝑇) + 𝑛𝑜𝑖𝑠𝑒 for 𝑛 times. Assume that he has got 𝑋1 , … , 𝑋𝑛 for the queries.
Question 3.3: Discuss why the expected value of 𝑋𝑖 is 𝑓(𝑇).
Let 𝑆 be an average of 𝑋𝑖 . The attacker will predict that 𝑓(𝑇) is 𝑆.
Question 3.4: Discuss why the expected value of 𝑆 is 𝑓(𝑇).
Question 3.5: Discuss why the probability that 𝑆 is different from 𝑓(𝑇) by more than 𝛼 is no morethan 2 ⋅ exp⁡(−2𝑛𝛼 2 ).
ln 10

Question 3.6: Calculate the probability that the attacker’s prediction has error smaller than √ 200 ≈0.11 when 𝑛 = 100.
Question 3.7: Discuss why your answer in Question 3.6 would imply a privacy problem for Laplacianmechanism. Discuss why we have already included this problem in the composition theorem.