Sample(x)=(a*x< =t) is a distinguisher with probability 1/8

TY - GEN

T1 - Sample(x)=(a*x< =t) is a distinguisher with probability 1/8

AU - Thorup, Mikkel

N1 - Conference code: 56

PY - 2015/12/11

Y1 - 2015/12/11

N2 - A random sampling function Sample: U → {0, 1} for a key universe U is a distinguisher with probability. If for any given assignment of values v(x) to the keys x ∈ U, including at least one non-zero v(x) ≠ 0, the sampled sum Σ{v(x)|x ∈ U ∧. Sample(x) = 1} is non-zero with probability at least α. Here the key values may come from any commutative monoid (addition is commutative and associative and zero is neutral). Such distinguishers were introduced by Vazirani [PhD thesis 1986], and Naor and Naor used them for their small bias probability spaces [STOC'90]. Constant probability distinguishers are used for testing in contexts where the key values are not computed directly, yet where the sum is easily computed. A simple example is when we get a stream of key value pairs (x1, v1), (x2, v2), , (xn, vn) where the same key may appear many times. The accumulated value of key x is v(x) = Σ{v1|xi = x}. For space reasons, we may not be able to maintain x(x) for every key x, but the sampled sum is easily maintained as the single value Σ {vi | Sample(xi) = 1}. Here we show that when dealing with Ω-bit integers, if α is a uniform odd Ω-bit integer and t is a uniform Ω-bit integer, then Sample(x) = [ax mod 2Ω ≤t] is a distinguisher with probability 1/8. Working with standard units, that is, Ω = 8,16,32,64, we exploit that Ω-bit multiplication works modulo 2., discarding overflow automatically, and then the sampling decision is implemented by the C-code a∗x<=t. Previous such samplers were much less computer friendly, e.g., The distinguisher of Naor and Naor [STOC'90] was more complicated and involved a 7-independent hash function.

AB - A random sampling function Sample: U → {0, 1} for a key universe U is a distinguisher with probability. If for any given assignment of values v(x) to the keys x ∈ U, including at least one non-zero v(x) ≠ 0, the sampled sum Σ{v(x)|x ∈ U ∧. Sample(x) = 1} is non-zero with probability at least α. Here the key values may come from any commutative monoid (addition is commutative and associative and zero is neutral). Such distinguishers were introduced by Vazirani [PhD thesis 1986], and Naor and Naor used them for their small bias probability spaces [STOC'90]. Constant probability distinguishers are used for testing in contexts where the key values are not computed directly, yet where the sum is easily computed. A simple example is when we get a stream of key value pairs (x1, v1), (x2, v2), , (xn, vn) where the same key may appear many times. The accumulated value of key x is v(x) = Σ{v1|xi = x}. For space reasons, we may not be able to maintain x(x) for every key x, but the sampled sum is easily maintained as the single value Σ {vi | Sample(xi) = 1}. Here we show that when dealing with Ω-bit integers, if α is a uniform odd Ω-bit integer and t is a uniform Ω-bit integer, then Sample(x) = [ax mod 2Ω ≤t] is a distinguisher with probability 1/8. Working with standard units, that is, Ω = 8,16,32,64, we exploit that Ω-bit multiplication works modulo 2., discarding overflow automatically, and then the sampling decision is implemented by the C-code a∗x<=t. Previous such samplers were much less computer friendly, e.g., The distinguisher of Naor and Naor [STOC'90] was more complicated and involved a 7-independent hash function.

U2 - 10.1109/FOCS.2015.82

DO - 10.1109/FOCS.2015.82

M3 - Article in proceedings

T3 - Symposium on Foundations of Computer Science. Annual Proceedings

SP - 1277

EP - 1291

BT - Proceedings. 56th Annual Symposium on Foundations of Computer Science

PB - IEEE

T2 - The Annual Symposium on Foundations of Computer Science

Y2 - 18 October 2015 through 20 October 2015

ER -