In this talk, we consider the following problems:
- A significant body of work is devoted to understanding the power of randomness in private computation. 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.
- We study the distributed function computation problem with k users of which at most s may be controlled by an adversary and characterize the set of functions of the sources the decoder can reconstruct robustly in the following sense -- if the users behave honestly, the function is recovered with high probability (w.h.p.); if they behave adversarially, w.h.p, either one of the adversarial users will be identified or the function is recovered with vanishingly small distortion.
- We introduce the pseudo-random object called psedo-random homomorphism families (PHF). These objects are related to seed-homomorphic PRGs, and are observed to yield many standard computational assumptions. Upon imposing additional algebraic structures on these PHFs, they are shown to help obtain certain pseudo-random correlation generators (PCGs) from certain other PCG
