Please read PDF file to understand complete assignment

Remove this leakage is as follows: the data owner pre-processes the data items by adding dummy keywords so that each keyword matches the same number of data items (some being real matches and some possibly being dummy matches). This approach increases the size of the database and we want to investigate algorithms that minimize the size of the resulting database.

Problem Statement: Let W denote a set of keywords.
An encrypted database is a matrix with n rows and 2 columns, where the n rows represent n data items, and the two columns represent a keyword header and a payload. We denote as w1 , . . . , wn ∈ W the (not necessarily different) keywords
in the first column.

A fixed answer length encrypted database is an encrypted database with n rows and m ≥ 2 columns, where the n rows represent n data items, and the m columns represent a real keyword header, m - 2 dummy keyword headers and a payload, satisfying the following property. Let rw1 , . . . , rwn ∈ W denote the (not necessarily different) real keywords in the first column. For j = 2, . . . , m - 1, let dw1j , . . . , dwnj ∈ W denote the (dummy) keywords in the next m - 2 keyword header columns. Then, for each keyword w ∈ W , the number of occurrences of w, denoted as occ(w), in the first m - 1 columns is
either 0 or a fixed positive integer k.

main goal is to transform an encrypted database into a fixed answer length while minimizing the number of dummy keyword headers. To do that, we can choose dummy keywords dw1j , . . . , dwnj from the set {rw1 , . . . , rwn , ⊥} so that occ(rw1 ) = • • • = occ(rwn ) = k, for some positive integer k, and the number m - 2 is minimized. Note that a dummy keyword can be either a real keyword or a meaningless symbol ⊥.

Assignment: Complete as many as possible among tasks (1)-(3).
1. What is the smallest possible value for k (as a function of occ(rw1 ), . . . , occ(rwn ))?

2. Let t denote the number m - 2 of dummy keyword headers. Can you provide an upper bound for t (as a function of
occ(rw1 ), . . . , occ(rwn ))? Can you provide a lower bound for t (as a function of occ(rw1 ), . . . , occ(rwn ))?

3. Can you define algorithm(s) to choose dummy keywords dw1j , . . . , dwnj , for j = 2, . . . , m - 1, from the set
{rw1 , . . . , rwn , ⊥} so to transform an encrypted database into a fixed answer length one and at the same time minimize
t?