Title: Randomness, Interactive Proofs, and Zero-Knowledge — A Survey
Abstract: Recent approaches to the notions of randomness and proofs are surveyed. The new notions differ from the traditional ones in being subjective to the capabilities of the observer rather than reflecting ideal entities. The new notion of randomness regards probability distributions as equal if they cannot be told apart by efficioent procedures. This notion is constructive and is suited for many applications. The new notion of a proof allows the introduction of the notion of zero-knowledge proofs: convincing arguments which yield nothing but the validity of the assertion. The new approaches to randomness and proofs are based on basic concepts and results from the theory of resource-bounded computation. In order to make the survey as accessible as possible, we have presented elements of the theory of resource bounded computation (but only to the extent required for the description of the new approaches).
Publication Year: 1995
Publication Date: 1995-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 9
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot