Kooperativer Bibliotheksverbund

UID:

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

ISBN: 9780511546891 (ebook)

Inhalt: 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.

Anmerkung: Title from publisher's bibliographic system (viewed on 05 Oct 2015). , 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

Weitere Ausg.: Print version: ISBN 9780521791724

Sprache: Englisch

URL: https://doi.org/10.1017/CBO9780511546891