A significant body of work is devoted to understanding the power of randomness in private computation. In this work, we make further progress on this by studying the randomness in a simple model of private computation called 'Private Stateless Sequential (PSS)' model. We show that the functions which can be computed 1-privately (i.e., 1 semi-honest corruption) with O(1) randomness using a speak-O(1)-times protocols are exactly those which can be computed with a constant-width read-O(1) branching programs.
This is a joint work with Varun Narayanan, Manoj Prabhakaran and Vinod M. Prabhakaran.
