Randomness-Efficient Oblivious Sampling

We introduce a natural notion of obliviousness of a sampling procedure, and construct a randomness-efficient oblivious sampler. Our sampler uses O(l+log /spl delta//sup -1//spl middot/log l) coins to output m=poly(/spl epsiv//sup -1/, log /spl delta//sup -1/, log l) sample points x/sub 1/, .. ., x/sub m/, /spl isin/ {0, 1}/sup 1/ such that Pr[|1/m/spl Sigma//sub i=1//sup m/f(x/sub i/)-E[f]|>

Authors

• Mihir Bellare
• John Rompel

Keywords

• Sampling methods
• Electronic mail
• Tail
• Random variables
• Security
• Polynomials
• Boolean functions
• Standard Procedures
• Error Probability
• Constant Factor
• Even Number
• Hash Function
• Head And Tail
• Error Reduction
• Independent Random Variables
• Common Input
• Boolean Function
• Security Parameter
• Random Bits
• Message Length
• Round Of The Game
• Collection Of Random Variables