In a recent work (Sun2017), Sun and Jafar defined the Private Computation (PC) problem where a user wants to compute a function of $K$ datasets, using $N$ distributed and non-colluding servers, without revealing which function the user wants to compute to any individual server. The considered setting is the "basic" one where the functions to be computed are arbitrary linear combinations of the datasets. In the paper, it is stated that this setting opens the door to numerous other open problems through various generalizations, including nonlinear functions.

The problem is studied in terms of capacity $C$, which is defined as the maximum number of bits of the desired function that can be retrieved per bit of total download from all servers. Nothing is said about the computational cost of the protocol for the servers.

In other works (such as Karpuk2018 or Heidarzadeh2020) the focus is again on capacity, and nothing is said about computational complexity.

I would like to know if the reason of this lack of interest for the computational aspects are due to the fact that the considered functions are simple, and further work on the topic has to come. Or if maybe I am missing important references (and probably I do). In that case, I ask for pointers that could help in my search.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy