THRESHOLD COMPUTATION AND CRYPTOGRAPHIC SECURITY

Threshold machines are Turing machines whose acceptance is determined by what portion of the machine's computation paths are accepting paths . Probabilistic machines are Turing machines whose acceptance is deter mined by the probability weight of the machine's accepting computation paths. In 1975, Simon proved that for unbounded-error polynomial-time machines these two notions yield the same class, PP. Perhaps because Simon's result seemed to collapse the threshold and probabilistic mode s of computation, the relationship between threshold and probabilistic computing for the case of bounded error has remained unexplored. In t his paper, we compare the bounded-error probabilistic class BPP with t he analogous threshold class, BPPpath, and, more generally, we study t he structural properties of BPPpath. We prove that BPPpath contains bo th NPBPP and P-NP[log] and that BPPpath is contained in P-Sigma 2p[log ], BPPNP, and PP. We conclude that, unless the polynomial hierarchy co llapses, bounded-error threshold computation is strictly more powerful than bounded-error probabilistic computation. We also consider the na tural notion of secure access to a database: an adversary who watches the queries should gain no information about the input other than perh aps its length. We show for both BPP and BPPpath that if there is a ny database for which this formalization of security differs from the se curity given by oblivious database access, then P not equal PSPACE. It follows that if any set lacking small circuits can be securely accept ed, then P not equal PSPACE.