This page is intentionally left blank.
Please do not open this question sheet until you are told to do so.

4810-1184 Algorithms for Information Security and Privacy 2018 – Final Examination
Problem 1
In this problem, we will try to find a relationship between the 𝑡-closeness anonymity scheme and theprivate PAC learning. Suppose that all possible sensitive information, which is annual salary in thisproblem, is {𝑖 millions: 3 ≤ 𝑖 ≤ 11}.
Question 1.1: Calculate the Earth Moving Distance for a group of two persons with salary 3 million and6 million.
Suppose that your answer to Question 1.1 is 𝑡.
Question 1.2: Consider a group of two persons with the Earth Moving Distance no smaller than 𝑡.
Discuss why the differences in salary between the two persons in the groups must be no larger than 3
million.
Consider the following type of queries from the machine learning algorithm:𝑓𝑖 (𝑇) ≔(𝑆𝑎𝑙𝑎𝑟𝑦 𝑜𝑓 𝑖) − 3)
8||𝑇||1(Question 1.3: Discuss why 𝑓𝑖 (𝑇) can be written in the form of ∑𝑗∈𝑇 𝑓𝑖 (𝑗) where 0 ≤ 𝑓𝑖 (𝑗) ≤ 1.
Suppose that we group all persons in our table to clusters with two persons. Each cluster must have theEarth Moving Distance no smaller than 𝑡. When the query from a machine learning algorithm is 𝑓𝑖 , wewill look at a cluster {𝑖, 𝑗} which 𝑖 belongs to. Then, we will give the machine learning algorithm thefollowing information:𝑓𝑖′ (𝑇) ≔(𝑠𝑎𝑙𝑎𝑟𝑦 𝑜𝑓 𝑖) − 3 (𝑠𝑎𝑙𝑎𝑟𝑦 𝑜𝑓 𝑗) − 3+)
8
82||𝑇||
1(Question 1.4: Calculate the maximum value for |𝑓𝑖′ (𝑇) − 𝑓𝑖 (𝑇)|Question 1.5: Discuss how we can use an SQ learning algorithm with all queries in the form of 𝑓𝑖 (𝑇)when the query answers is giving as 𝑓𝑖′ (𝑇).
Question 1.6: In the 𝑡-closeness anonymity scheme, we require that the Earth Moving Distance at eachcluster must be smaller than some value. Discuss why it is also important to require that the Earth
Moving Distance must be larger than some value.

4810-1184 Algorithms for Information Security and Privacy 2018 – Final Examination
Problem 2
We will work on divisors in this problem. However, instead of working on divisors for elliptic curve asin the class, we will work on divisors on prime field 𝔽11 here. Consider a function 𝑓 from 𝔽11 to real
numbers. Suppose that 𝑓(𝑥) = (𝑥 ⊕ 4)2 .
Question 2.1: Find all zero points of the function 𝑓.
Question 2.2: Calculate the orders of the zero points in Question 2.1.
Question 2.3: Discuss why there is no pole (𝑥 such that 𝑓(𝑥) → ∞) in the function 𝑓.
Question 2.4: What is the divisor of the function 𝑓?
Question 2.5: Discuss why there is no function 𝑓 such that 𝑑𝑖𝑣(𝑓) = 2[3].
Question 2.6: From your answer in Question 2.5, discuss why it is not possible to replace elliptic curve𝐸(𝔽𝑝 ) with the set 𝔽𝑝 to save the computation time.

Problem 3
Elliptic curve cryptography uses 5 times less memory than RSA. In this problem, we will try to further
reduce its memory consumption. From the following question, we will consider elliptic curve with
Weirstrass equation 𝑦 2 = 𝑥 3 + 𝐴𝑥 + 𝐵.
Question 3.1: Discuss why for any 𝑥 ′ ∈ 𝔽𝑝 , there is at most 2 points on elliptic curve of which the 𝑥coordinate is 𝑥′.
Question 3.2: Discuss what it is enough to use 1 bit to remember 𝑦-coordinate of all the points on elliptic
curve.
From next question, recall that (𝔽𝑝 − {0}, ⨂) is an abelian group.
Question 3.3: Use a property of an abelian group to explain why, for any 𝑘 ∈ 𝔽𝑝 − {0}, 𝑘 𝑝 = 𝑘.
Question 3.4: Discuss why, when we have 𝑋 on the right side of the Weirstrass equation, 𝑦 is either𝑝𝑋 𝑝/2 or −𝑋 2 .
Question 3.5: Discuss the computation time of calculating 𝑦-coordinate from 𝑥-coordinate.
Question 3.6: Discuss why “compressing” 𝑦 -coordinate to 1 bit is not very helpful from thecomputational point of view.