Modern cryptography, probabilistic proofs and pseudo-randomness
Random number generation in numerical analysis (65C10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Data encryption (aspects in computer science) (68P25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory (94-01) Cryptography (94A60)
The book gives an introduction and extensive survey to the three areas of: modern cryptography, probabilistic proof systems and pseudo-randomness. From the preface of the book: `The goal is to provide the reader with 1. A clear and structured overview of each of these areas. 2. Knowledge of the most important notions, ideas, techniques and results in each area. 3. Some new insights into each of these areas.' The first chapter introduces the basic notions of computational difficulty, pseudorandomness and zero-knowledge systems. In addition it gives a fairly comprehensive survey of the cryptographic utilities of encryption, signatures, including hash functions, and protocols. More discursive than a theorem and proof approach, it gives insight into the fundamentals of the subject. The second chapter concentrates on the three proof systems of interactive proofs, zero knowledge proofs and probabilistic checkable proofs. In particular, the role of randomness is viewed as a unifying theme for these discussions. Other interactive proof systems are also reviewed, including models in which the prover is restricted in its choice of strategy, a model in which the prover-verifier interaction is restricted and a model in which one proves knowledge of facts rather than their validity. Some open problems are also described. The third chapter focuses on the theory of randomness rooted in complexity theory. Here, objects are considered equal if they cannot be distinguished by any efficient procedure. The notions of stretching functions which take short strings and output longer ones, and computational indistinguishability, are fundamental to the approach. The book contains three appendices. The first contains background on probability theory assumed throughout the book and includes a discussion on computational models and complexity classes. It concludes with a review of four basic problems of cryptography, encryption schemes, digital signatures, message authentication and RSA and Rabin functions. The Appendix B demonstrates the usage of randomness in a variety of computational settings, including discussions on randomized algorithms, the role of randomness in complexity theory and randomness in distributed computing. The last appendix provides proofs of two basic results concerning, respectively, the behaviour of the error in parallel repetition of interactive proofs, with the number of repetitions, and the existence of a generic hard core predicate, used in chapter three.
- Reducing complexity assumptions for statistically-hiding commitment
- An overview of distinguishing attacks on stream ciphers
- Quantum lower bounds for the Goldreich-Levin problem
- A simple remote user authentication scheme
- Interactive and probabilistic proof-checking
- Proofs of proximity for context-free languages and read-once branching programs
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- More efficient PAC-learning of DNF with membership queries under the uniform distribution
- A tight parallel repetition theorem for partially simulatable interactive arguments via smooth KL-divergence
- A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols
- Practical construction and analysis of pseudo-randomness primitives
- Quantum algorithms for the Goldreich-Levin learning problem
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
- Randomness and computation
- scientific article; zbMATH DE number 176068 (Why is no real title available?)
- Foundations of Cryptography
- Finding significant Fourier coefficients: clarifications, simplifications, applications and limitations
- A probabilistic polynomial-time calculus for analysis of cryptographic protocols (preliminary report)
- Distinguishing distributions using Chernoff information
- Pseudo-deterministic proofs
- scientific article; zbMATH DE number 7250162 (Why is no real title available?)
- Appraising two decades of distributed computing theory research
- Rapidly computing sparse Legendre expansions via sparse Fourier transforms
- Tweakable Enciphering Schemes from Hash-Sum-Expansion
- Computational sample complexity and attribute-efficient learning
- Pseudorandom generators without the XOR lemma
- A consequence of a proof of the one-way function existence for the problem of macroscopic superpositions
- Zero-knowledge identification scheme based on Weil pairing
- A note on Yao's theorem about pseudo-random generators
- On parallel repetition of interactive proof systems
- On parallel repetition of PCPs
- Exploring confusion in product ciphers through regression analysis
This page was built for publication: Modern cryptography, probabilistic proofs and pseudo-randomness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1273742)
