We say that a function f : n 0 1 is -fooled by k -wise indistinguishability if f cannot distinguish with advantage between any two distributions and over n whose projections to any k symbols are identical. We study the class of functions f that are fooled by bounded indistinguishability.

When = 0 1 , we observe that whether f is fooled is closely related to its approximate degree. For larger alphabets , we obtain several positive and negative results. Our results imply the first efficient secret sharing schemes with a high secrecy threshold in which the secret can be reconstructed in AC 0 . More concretely, we show 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, any set of at least n parties can reconstruct the secret, and where both the sharing and the reconstruction are done by AC 0 circuits of size pol y ( n ) . We present additional cryptographic applications of our results to low-complexity secret sharing, visual secret sharing, leakage-resilient cryptography, and protecting against "selective failure" attacks.