Suppose each of k \le n^{o(1)} players holds an n-bit number x_i in its hand. The players wish to determine if \sum_{i \le k} x_i = s. We give a public-coin protocol with error 1\% and communication O(k \lg k). The communication bound is independent of n, and for $k ... more >>>

In the presence of a quantum adversary, there are two possible definitions of security for a pseudorandom function. The first, which we call standard-security, allows the adversary to be quantum, but requires queries to the function to be classical. The second, quantum-security, allows the adversary to query the function on ... more >>>