Randomness and Computation

DOI10.1007/978-3-642-22670-0_33zbMath1343.68181OpenAlexW2275340472MaRDI QIDQ3088199

Oded Goldreich

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_33

zbMATH Keywords

encryption schemesinteractive proofszero-knowledge proofsprobabilistically checkable proofsproperty testingpseudorandomnessmessage authentication schemes

Mathematics Subject Classification ID

Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

Cryptographic Assumptions: A Position Paper

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic encryption
• P, NP, and NP-Completeness
• A Brief Introduction to Property Testing
• Introduction to Testing Graph Properties
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• The Knowledge Complexity of Interactive Proof Systems
• Probabilistic checking of proofs
• A Pseudorandom Generator from any One-way Function
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Foundations of Cryptography
• Interactive proofs and the hardness of approximating cliques
• Foundations of Cryptography
• Robust Characterizations of Polynomials with Applications to Program Testing
• lgorithmic and Analysis Techniques in Property Testing
• Computational Complexity

This page was built for publication: Randomness and Computation