Kooperativer Bibliotheksverbund

UID:

Format: 1 online resource (xix, 372 pages) : , digital, PDF file(s).

ISBN: 1-107-38559-8 , 1-107-12164-7 , 0-511-03160-2 , 1-280-43006-0 , 9786610430062 , 0-511-20213-X , 0-511-17465-9 , 0-511-04120-9 , 0-511-32343-3 , 0-511-54689-0 , 0-511-04687-1

Content: Cryptography is concerned with the conceptualization, definition and construction of computing systems that address security concerns. The design of cryptographic systems must be based on firm foundations. This book presents a rigorous and systematic treatment of the foundational issues: defining cryptographic tasks and solving new cryptographic problems using existing tools. It focuses on the basic mathematical tools: computational difficulty (one-way functions), pseudorandomness and zero-knowledge proofs. The emphasis is on the clarification of fundamental concepts and on demonstrating the feasibility of solving cryptographic problems, rather than on describing ad-hoc approaches. The book is suitable for use in a graduate course on cryptography and as a reference book for experts. The author assumes basic familiarity with the design and analysis of algorithms; some knowledge of complexity theory and probability is also useful.

Note: First published 2001, reprinted with corrections 2003. , Encryption Schemes , Pseudorandom Generators , Digital Signatures , Fault-Tolerant Protocols and Zero-Knowledge Proofs , Some Background from Probability Theory , Notational Conventions , Three Inequalities , Computational Model , P, NP, and NP-Completeness , Probabilistic Polynomial Time , Non-Uniform Polynomial Time , Intractability Assumptions , Oracle Machines , Motivation to the Rigorous Treatment , Need for a Rigorous Treatment , Practical Consequences of the Rigorous Treatment , Tendency to Be Conservative , Historical Notes , Open Problems , Computational Difficulty , One-Way Functions: Motivation , One-Way Functions: Definitions , Strong One-Way Functions , Weak One-Way Functions , Two Useful Length Conventions , Candidates for One-Way Functions , Non-Uniformly One-Way Functions , Weak One-Way Functions Imply Strong Ones , Construction and Its Analysis (Proof of Theorem 2.3.2) , Illustration by a Toy Example , One-Way Functions: Variations , Universal One-Way Function , One-Way Functions as Collections , Examples of One-Way Collections , Trapdoor One-Way Permutations , Claw-Free Functions , On Proposing Candidates , Hard-Core Predicates , Hard-Core Predicates for Any One-Way Function , Hard-Core Functions , Efficient Amplification of One-Way Functions , Construction , Analysis , Historical Notes , Pseudorandom Generators , Motivating Discussion , Computational Approaches to Randomness , A Rigorous Approach to Pseudorandom Generators , Computational Indistinguishability , Relation to Statistical Closeness , Indistinguishability by Repeated Experiments , Indistinguishability by Circuits , Pseudorandom Ensembles , Definitions of Pseudorandom Generators , Standard Definition of Pseudorandom Generators , Increasing the Expansion Factor , Variable-Output Pseudorandom Generators , Applicability of Pseudorandom Generators , Pseudorandomness and Unpredictability , Pseudorandom Generators Imply One-Way Functions , Constructions Based on One-Way Permutations , Construction Based on a Single Permutation , Construction Based on Collections of Permutations , Using Hard-Core Functions Rather than Predicates , Constructions Based on One-Way Functions , Using 1-1 One-Way Functions , Using Regular One-Way Functions , Going Beyond Regular One-Way Functions , Pseudorandom Functions , Applications: A General Methodology , Pseudorandom Permutations , Historical Notes , Zero-Knowledge Proof Systems , Zero-Knowledge Proofs: Motivation , Notion of a Proof , Gaining Knowledge , Interactive Proof Systems , An Example (Graph Non-Isomorphism in IP) , Structure of the Class IP , Augmentation of the Model , Zero-Knowledge Proofs: Definitions , Perfect and Computational Zero-Knowledge , An Example (Graph Isomorphism in PZK) , Zero-Knowledge with Respect to Auxiliary Inputs , Sequential Composition ofh Zero-Knowledge Proofs , Zero-Knowledge Proofs for NP , Commitment Schemes , Zero-Knowledge Proof of Graph Coloring , General Result and Some Applications , Second-Level Considerations , Negative Results , On the Importance of Interaction and Randomness , Limitations of Unconditional Results , Limitations of Statistical ZK Proofs , Zero-Knowledge and Parallel Composition , Witness Indistinguishability and Hiding , Parallel Composition , Proofs of Knowledge , Reducing the Knowledge Error , Zero-Knowledge Proofs of Knowledge for NP , Proofs of Identity (Identification Schemes) , Strong Proofs of Knowledge , Computationally Sound Proofs (Arguments) , Perfectly Hiding Commitment Schemes , Perfect Zero-Knowledge Arguments for NP , Arguments of Poly-Logarithmic Efficiency , Constant-Round Zero-Knowledge Proofs , Using Commitment Schemes with Perfect Secrecy , Bounding the Power of Cheating Provers , Non-Interactive Zero-Knowledge Proofs , Extensions , Multi-Prover Zero-Knowledge Proofs , Two-Sender Commitment Schemes , Perfect Zero-Knowledge for NP , Historical Notes , A Background in Computational Number Theory , Prime Numbers , Quadratic Residues Modulo a Prime , Extracting Square Roots Modulo a Prime , Primality Testers , On Uniform Selection of Primes , Composite Numbers , Quadratic Residues Modulo a Composite , Extracting Square Roots Modulo a Composite , Legendre and Jacobi Symbols , Blum Integers and Their Quadratic-Residue Structure , Brief Outline of Volume , Encryption: Brief Summary , Beyond Eavesdropping Security , Signatures: Brief Summary , Cryptographic Protocols: Brief Summary , English

Additional Edition: ISBN 0-521-03536-8

Additional Edition: ISBN 0-521-79172-3

Language: English