On the Randomness Cost of Linear Secure Computation : (Invited Presentation)
Yanliang Zhou, Hua Sun, Shengli Fu · 2019
We consider the problem of secure computation, where K users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We show that to compute M generic linear independent combinations of the messages securely (i.e., for the linear secure computation problem), it suffices to use min(|(K-M-1)/2|, M) randomness symbols per message symbol (i.e., the randomness cost is no larger than min(|(K-M-1)/2|, M)). The optimality of the achieved randomness cost remains open.