000			08379nam a22003498i 4500
001			CR9780511546891
003			UkCbUP
005			20200124160333.0
006			m|||||o||d||||||||
007			cr||||||||||||
008			090508s2003||||enk o ||1 0|eng|d
020			_a9780511546891 (ebook)
020			_z9780521791724 (hardback)
020			_z9780521035361 (paperback)
040			_aUkCbUP _beng _erda _cUkCbUP
050	0	0	_aQA268 _b.G5745 2003
082	0	0	_a652/.8 _221
100	1		_aGoldreich, Oded, _eauthor.
245	1	0	_aFoundations of cryptography : _bbasic tools / _cOded Goldreich.
264		1	_aCambridge : _bCambridge University Press, _c2003.
300			_a1 online resource (xix, 372 pages) : _bdigital, PDF file(s).
336			_atext _btxt _2rdacontent
337			_acomputer _bc _2rdamedia
338			_aonline resource _bcr _2rdacarrier
500			_aTitle from publisher's bibliographic system (viewed on 05 Oct 2015).
505	0	0	_g1.1.1. _tEncryption Schemes _g2 -- _g1.1.2. _tPseudorandom Generators _g3 -- _g1.1.3. _tDigital Signatures _g4 -- _g1.1.4. _tFault-Tolerant Protocols and Zero-Knowledge Proofs _g6 -- _g1.2. _tSome Background from Probability Theory _g8 -- _g1.2.1. _tNotational Conventions _g8 -- _g1.2.2. _tThree Inequalities _g9 -- _g1.3. _tComputational Model _g12 -- _g1.3.1. _tP, NP, and NP-Completeness _g12 -- _g1.3.2. _tProbabilistic Polynomial Time _g13 -- _g1.3.3. _tNon-Uniform Polynomial Time _g16 -- _g1.3.4. _tIntractability Assumptions _g19 -- _g1.3.5. _tOracle Machines _g20 -- _g1.4. _tMotivation to the Rigorous Treatment _g21 -- _g1.4.1. _tNeed for a Rigorous Treatment _g21 -- _g1.4.2. _tPractical Consequences of the Rigorous Treatment _g23 -- _g1.4.3. _tTendency to Be Conservative _g24 -- _g1.5.1. _tHistorical Notes _g25 -- _g1.5.3. _tOpen Problems _g27 -- _g2 _tComputational Difficulty _g30 -- _g2.1. _tOne-Way Functions: Motivation _g31 -- _g2.2. _tOne-Way Functions: Definitions _g32 -- _g2.2.1. _tStrong One-Way Functions _g32 -- _g2.2.2. _tWeak One-Way Functions _g35 -- _g2.2.3. _tTwo Useful Length Conventions _g35 -- _g2.2.4. _tCandidates for One-Way Functions _g40 -- _g2.2.5. _tNon-Uniformly One-Way Functions _g41 -- _g2.3. _tWeak One-Way Functions Imply Strong Ones _g43 -- _g2.3.1. _tConstruction and Its Analysis (Proof of Theorem 2.3.2) _g44 -- _g2.3.2. _tIllustration by a Toy Example _g48 -- _g2.4. _tOne-Way Functions: Variations _g51 -- _g2.4.1. _tUniversal One-Way Function _g52 -- _g2.4.2. _tOne-Way Functions as Collections _g53 -- _g2.4.3. _tExamples of One-Way Collections _g55 -- _g2.4.4. _tTrapdoor One-Way Permutations _g58 -- _g2.4.5. _tClaw-Free Functions _g60 -- _g2.4.6. _tOn Proposing Candidates _g63 -- _g2.5. _tHard-Core Predicates _g64 -- _g2.5.2. _tHard-Core Predicates for Any One-Way Function _g65 -- _g2.5.3. _tHard-Core Functions _g74 -- _g2.6. _tEfficient Amplification of One-Way Functions _g78 -- _g2.6.1. _tConstruction _g80 -- _g2.6.2. _tAnalysis _g81 -- _g2.7.1. _tHistorical Notes _g89 -- _g3 _tPseudorandom Generators _g101 -- _g3.1. _tMotivating Discussion _g102 -- _g3.1.1. _tComputational Approaches to Randomness _g102 -- _g3.1.2. _tA Rigorous Approach to Pseudorandom Generators _g103 -- _g3.2. _tComputational Indistinguishability _g103 -- _g3.2.2. _tRelation to Statistical Closeness _g106 -- _g3.2.3. _tIndistinguishability by Repeated Experiments _g107 -- _g3.2.4. _tIndistinguishability by Circuits _g111 -- _g3.2.5. _tPseudorandom Ensembles _g112 -- _g3.3. _tDefinitions of Pseudorandom Generators _g112 -- _g3.3.1. _tStandard Definition of Pseudorandom Generators _g113 -- _g3.3.2. _tIncreasing the Expansion Factor _g114 -- _g3.3.3. _tVariable-Output Pseudorandom Generators _g118 -- _g3.3.4. _tApplicability of Pseudorandom Generators _g119 -- _g3.3.5. _tPseudorandomness and Unpredictability _g119 -- _g3.3.6. _tPseudorandom Generators Imply One-Way Functions _g123 -- _g3.4. _tConstructions Based on One-Way Permutations _g124 -- _g3.4.1. _tConstruction Based on a Single Permutation _g124 -- _g3.4.2. _tConstruction Based on Collections of Permutations _g131 -- _g3.4.3. _tUsing Hard-Core Functions Rather than Predicates _g134 -- _g3.5. _tConstructions Based on One-Way Functions _g135 -- _g3.5.1. _tUsing 1-1 One-Way Functions _g135 -- _g3.5.2. _tUsing Regular One-Way Functions _g141 -- _g3.5.3. _tGoing Beyond Regular One-Way Functions _g147 -- _g3.6. _tPseudorandom Functions _g148 -- _g3.6.3. _tApplications: A General Methodology _g157 -- _g3.7. _tPseudorandom Permutations _g164 -- _g3.8.1. _tHistorical Notes _g169 -- _g4 _tZero-Knowledge Proof Systems _g184 -- _g4.1. _tZero-Knowledge Proofs: Motivation _g185 -- _g4.1.1. _tNotion of a Proof _g187 -- _g4.1.2. _tGaining Knowledge _g189 -- _g4.2. _tInteractive Proof Systems _g190 -- _g4.2.2. _tAn Example (Graph Non-Isomorphism in IP) _g195 -- _g4.2.3. _tStructure of the Class IP _g198 -- _g4.2.4. _tAugmentation of the Model _g199 -- _g4.3. _tZero-Knowledge Proofs: Definitions _g200 -- _g4.3.1. _tPerfect and Computational Zero-Knowledge _g200 -- _g4.3.2. _tAn Example (Graph Isomorphism in PZK) _g207 -- _g4.3.3. _tZero-Knowledge with Respect to Auxiliary Inputs _g213 -- _g4.3.4. _tSequential Composition ofh Zero-Knowledge Proofs _g216 -- _g4.4. _tZero-Knowledge Proofs for NP _g223 -- _g4.4.1. _tCommitment Schemes _g223 -- _g4.4.2. _tZero-Knowledge Proof of Graph Coloring _g228 -- _g4.4.3. _tGeneral Result and Some Applications _g240 -- _g4.4.4. _tSecond-Level Considerations _g243 -- _g4.5. _tNegative Results _g246 -- _g4.5.1. _tOn the Importance of Interaction and Randomness _g247 -- _g4.5.2. _tLimitations of Unconditional Results _g248 -- _g4.5.3. _tLimitations of Statistical ZK Proofs _g250 -- _g4.5.4. _tZero-Knowledge and Parallel Composition _g251 -- _g4.6. _tWitness Indistinguishability and Hiding _g254 -- _g4.6.2. _tParallel Composition _g258 -- _g4.7. _tProofs of Knowledge _g262 -- _g4.7.2. _tReducing the Knowledge Error _g267 -- _g4.7.3. _tZero-Knowledge Proofs of Knowledge for NP _g268 -- _g4.7.5. _tProofs of Identity (Identification Schemes) _g270 -- _g4.7.6. _tStrong Proofs of Knowledge _g274 -- _g4.8. _tComputationally Sound Proofs (Arguments) _g277 -- _g4.8.2. _tPerfectly Hiding Commitment Schemes _g278 -- _g4.8.3. _tPerfect Zero-Knowledge Arguments for NP _g284 -- _g4.8.4. _tArguments of Poly-Logarithmic Efficiency _g286 -- _g4.9. _tConstant-Round Zero-Knowledge Proofs _g288 -- _g4.9.1. _tUsing Commitment Schemes with Perfect Secrecy _g289 -- _g4.9.2. _tBounding the Power of Cheating Provers _g294 -- _g4.10. _tNon-Interactive Zero-Knowledge Proofs _g298 -- _g4.10.3. _tExtensions _g306 -- _g4.11. _tMulti-Prover Zero-Knowledge Proofs _g311 -- _g4.11.2. _tTwo-Sender Commitment Schemes _g313 -- _g4.11.3. _tPerfect Zero-Knowledge for NP _g317 -- _g4.12.1. _tHistorical Notes _g320 -- _gAppendix _tA Background in Computational Number Theory _g331 -- _gA.1. _tPrime Numbers _g331 -- _gA.1.1. _tQuadratic Residues Modulo a Prime _g331 -- _gA.1.2. _tExtracting Square Roots Modulo a Prime _g332 -- _gA.1.3. _tPrimality Testers _g332 -- _gA.1.4. _tOn Uniform Selection of Primes _g333 -- _gA.2. _tComposite Numbers _g334 -- _gA.2.1. _tQuadratic Residues Modulo a Composite _g335 -- _gA.2.2. _tExtracting Square Roots Modulo a Composite _g335 -- _gA.2.3. _tLegendre and Jacobi Symbols _g336 -- _gA.2.4. _tBlum Integers and Their Quadratic-Residue Structure _g337 -- _gAppendix B _tBrief Outline of Volume _g338 -- _gB.1. _tEncryption: Brief Summary _g338 -- _gB.1.3. _tBeyond Eavesdropping Security _g343 -- _gB.2. _tSignatures: Brief Summary _g345 -- _gB.3. _tCryptographic Protocols: Brief Summary _g350.
520			_aCryptography 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.
650		0	_aCoding theory.
650		0	_aCryptography _xMathematics.
776	0	8	_iPrint version: _z9780521791724
856	4	0	_uhttps://doi.org/10.1017/CBO9780511546891
999			_c522797 _d522795