Institute of Information Science, Academia Sinica

We say that a function ƒ:Σn → {0,1} isɛ-fooled by k-wise indistinguishability if ƒ cannot distinguish with advantageɛbetween any two distributionsμ,ν overΣn whose projections to any k symbols are identical. We study the class of functions ƒ that are fooled by bounded indistinguishability, and highlight differences between this notion and that of bounded independence. WhenΣ = {0,1}, we observe that whether ƒ is fooled is closely related to its approximate degree. We also consider larger alphabets, and obtain a secret sharing scheme such that for every 0 <σ<ρ≤ 1 , it is possible to share a secret among n parties so that any set of fewer than σn parties can learn nothing about the secret, and any set of at least pn can reconstruct the secret. An appealing property of this scheme is that both sharing and reconstruction can be done with poly-sized AC0  circuits.