Randomness in Interactive Proofs

The quantitative aspects of randomness in interactive proof systems are studied. The result is a randomness-efficient error-reduction technique: given an Arthur-Merlin proof system (error probability <or=1/3) in which Arthur sends l=l(n) random bits per rounds, a proof system that achieves error probability 2/sup -k/ at the cost of Arthur sending only 2l+O(k) random bits per round is constructed. The method maintains the number of rounds in the game. Underlying the transformation is a novel sampling method for approximating the average value of an arbitrary function f:

Authors

• Mihir Bellare
• Oded Goldreich 0001
• Shafi Goldwasser

Keywords

• Polynomials
• Error probability
• Computer science
• Costs
• Laboratories
• Sampling methods
• Computational modeling
• Protocols
• Voting
• Interactive System
• Head And Tail
• Probability 2
• Random Bits
• Round Of The Game
• Loss Of Generality
• Random Walk
• Deterministic Processes
• Common Input
• End Of The Game
• Boolean Function
• Message Length
• Probabilistic Polynomial Time
• Original Game