《Modern Cryptography, Probabilistic Proofs and Pseudorandomness_Oded Goldreich》pdf电子书免费下载
下载方式一：
百度网盘下载地址：https://pan.baidu.com/s/1-U56vw8FAnca37pAOuqkKg
百度网盘密码：1111
下载方式二：
http://ziliaoshare.cn/Download/af_124023_pd_ModernCryptography,ProbabilisticProofsandPseudorandomness_OdedGoldreich.zip
|
|
作者：empty 页数：202 出版社：empty |
《Modern Cryptography, Probabilistic Proofs and Pseudorandomness_Oded Goldreich》介绍
The interplay between randomness and computation is one of the most fas-c in ating scientific phenomena uncovered in the last couple of decades， Thisinterplay is at the heart of modern cryptography and plays a fundamentalrole in complexity theory at large.Specifc ally， the interplay of randomnessand computation is pivotal to several intriguing notions of probabilistic proofsystems and is the focal of the computational approach to randomness.Thisbook provides an introduction to these three， somewhat interwoven domains(i.e.， cryptography， proofs and randomness) .
Modern Cryptography.Whereas classical ery p tography was confined tothe art of designing and breaking encryption schemes(or“secrecy codes ) ，Modern Cryptography is concerned with the rigorous analysis of any systemwhich should withstand malicious attempts to abuse it.We emphasize twoaspects of the transition from el as sical to moderner yp tography：(1) the wide-ning of scope from one specific task to an utmost wide general class of tasks；and(2) the move from an engineering-art which strives on ad-hoc tricks to ascientific discipline based on rigorous approaches and techniques.In this book we provide an introduction to the foundations of ModernCryptography， We focus on the paradigms， approaches and techniques usedto conceptualize， define and provide solutions to natural cryptographic pro-blems.We also survey some of the fundamental results obtained using theseparadigms， approaches and techniques The emphasis of the exposition is onthe need for and impact of a rigorous approachProbab listic Proof Systems.Various types of probabilistic proof systemshave played a central role in the development of computer scien oe in thelast decade.These proof systems share a common(untraditional) feature-they carry a probab ity of error； yet， this probability is explicitly boundedand can be reduced by successive application of the proof system.The gainin allowing this untraditional relaxation is sub et anti al， as demonstrated bythree wellknown results regarding interactive proofs， zero-knowledge proofs，
and probabilistic checkable proofs In each of these cases， allowing aboundedprobability of error makes the system much more powerful and useful thanthe traditional(errorless) counterparts.Focusing on the three types of proof sys terns mentioned above， but goingalso beyond them， we survey the basic def nitions and results regarding pro-babi listic proofs.Our exposition stresses both the similarities and differencesbetween the various types of probabilistic proofs.Pseudo randomness.A fresh view at the question of randomness was takenin the theory of computing：It has been postulated that a distribution ispseudorandom if it can not be told apart from the uniform distribution by anyefh cient procedure.This paradigm， originally associating efficient procedureswith polynomial-time algorithms， has been applied also with respect to avariety of limited classes of such distinguishing procedures.Starting with the general paradigm， we survey the archetypical case ofpseudorandom generators(withstanding any polynomial-time distinguisher) ，as well as generators withstanding space-bounded distinguish ers， the der an-do mization of complexity classes such as BPP， and some special-purposegenerators.
An Underlying AssumptionMuch of the contents of this book depends on the widely believed conjectureby which P#NP.This dependency is explicitly stated in some of the resultswhich make even stronger assumptions(such as the existence of one-wayfunctions) ， and is implicit in some results(such as the PCP Characterizationof NP) which would become uninteresting ifP=NP.On the Nature of this BookThis book offers an introduction and extensive survey to each of the threeareas mentioned above.It present both the basic notions and the most im-portant(and sometimes advanced) results.The presentation is focused onthe essentials and does not ella borate on details.In some cases it offers anovel and illuminating perspective.The goal is to provide the reader with1.A clear and structured over vic w of each of these areas.2.Knowledge of the most important notions， ideas， techniques and results3.Some new insights into each of these areasIt is hoped that the book maybe useful both to a beginner(who has onlysome background in the theory of computing) ， and to an expert in any ofthese areas.
OrganizationIn Chapter 1we survey the basic concepts， deh nitions and results in cryp-tography.In particular， we survey the basic tools of cryptography-compu-tational diffcult y， pseudo randomness and zero-knowledge proofs-and thebasic utilities-encryption， signatures， and general cryptographic protocols，Chapters 2 and 3 provides a wider perspective on two concepts mentioned inChapter 1.Specifc ally， Chapter 2 surveys various types of probabilistic proofsystems including interactive proofs， zero-knowledge proofs and probabil is ti-cally checkable proofs(PCP) .(The overlap with Chapter lis small， and thepresentation is quite different.) Likewise， Chapter 3 surveys various notionsof pseudorandom generators， viewing the one discussed in Chapter las anarchetypical instantiation of a general paradigm.The three chapters maybe read independently of eachother.In particu-lar， each starts with an individual brief introduction to the respective subjectmatter.As hinted above， although the chapters do overlap， the perspectivestaken in them are different.Specifically， Chapter l treats the theoretical foun-dations of a practical discipline， and so the presentation departs from practiceand emphasizes the import an cc of rigorous treatment for sound practice(andnot merely perse) .In contrast， Chapters 2 and 3 depart from the theoryof computing and emphasize the intellectual contents of the material(ratherthan its practical applicability) .The fact that different perspectives co-existin the same book， let alone in the same author， is indicative of the nature ofthe theory of computingThe three chapters are augmented by four appendices and an extensivebibliography.Most importantly， Appendix A provides some basic backgroundon computation and randomnessWe mention that important relations between randomness and compu-tation were di covered also in other domains of the theory of computation.Some examples are given in Appendix B.Appendix C provides proofs of two basic results； one being a folklore forwhich no proof has ever appeared， and the other for which the published proofis both too terse and more complex than the alternative presented here，
AcknowledgmentsMuch of the material was written while visiting the Laboratory for ComputerScience of MIT.A preliminary version of Chapter l has appeared in the proceedings ofAdvances in Cryptology-Crypto 97， Springer's Lecture Notes in ComputerScience(1997) ， Vol.1294， pages 46-74.Parts of the material presented in Chapter 2 have appeared in the pro-seiosTACSomgsLtrNoeinc mutes rnc 199)Vol.1200， pages 595-611.As for personal acknowledgments， I will only mention some of the peopleto whom I am most in debt for my professional development.These includeBenny Chor， Shimon Even， Shafi Goldwasser， Leonid Levin， Silvio Micali，and Avi Wigderson..very little do we have and in close which we can call our own inthe deep sense of the word We all have to accept and learn， eitherfrom our predecessors or from our contemporaries.Even the greatestgenius would not have achieved much if he had wished to extracteverything from inside himself.But there are many good people，who do not understand this， and spend half their lives wonderingin darkness with their dreams of originality.I have known artistswho were proud of not having followed any teacher and of owingeverything only to their own genius.Such fools!
《Modern Cryptography, Probabilistic Proofs and Pseudorandomness_Oded Goldreich》目录
1.The Foundations of Modern Cryptography
1.1 Introduction.
1.2 Central Paradigms.
1.3 Pseudo randomness.
1.4Zero-Knowledge.
1.5 Encryption.
1.6 Signatures.
1.7 Cryptographic Protocols
1.2.1 Computational Dii culty：
1.2.2 Computational In dist gui haly
1.2.3 The Simulation Paradigm，
1.3.1 The Basics.
1.3.2 Pseudorandom Functions.
1.4.1 The Basics.
1.4.2 Some Variants.
1.5.1Deinitions.
1.5.2 Constructions.
1.5.3 Security Beyond Passive Attacks.
1.6.1 Definitions.
1.6.2 Constructions.
1.6.3Two Variants.，
1.7.1 Definitions.
1.7.2Constructions.
1.8 Some Notes.
1.8.1General Notes
1.9 Historical Perspective.
110Two Suggestions for Future Research
1.11 Some Suggestions for Further Reading.
2.Probabilistic Proof Systems.
2.1 Introduction.
1.8.2 Specific Notes.
2.2.1Detinition.
115799地培巧巧幻
22 Interactive Proof System ns.
XIVTableofContents
2.3Zero-Knowledge Proof Systems.
3.6 Special Purpose Generators.
2.2.2 The Role of Randomness.
2.2.3 The Power of Interactive Proofs.
2.2.4 The Interact ve Proof System Her archy，
2.2.5How Powerful Should the Prover Be?.
2.3.1A Sample Definition.
2.32 The Power of Zero-Knowledge.
2.3.3 The Role of Randomness.
2.4.1 Definition.
2.5.1 Restricting the Prover's Strategy
2.5.3 Proofs of Knowledge-.
2.5.4 Refereed Games.
2.6.2 The Story.
2.6.3 Open Problems
3.3.1A Short Discussion.
3.3.2 Some Basic Observations
3.3.3 Constructions.
3.3.4 Pseudorandom Functions.
3.6.1Paiwie-Independence Generators
3.6.2 Small-Bias Generators.
3.6.3 RandomWalks on Expanders.
3.64 Samplers.
3.7.1 Discussion.
3.7.2 Historical Perspective.
2.4 Probabilistic aly Checkable Proof Systems.
2.5 Other Probabilistic Proof Systems，
2.6 Concluding Remarks.
26.1Comparion Among the Various No ins
3.Pseudorandom Generators.
3.1 Introduction.
3.2 The General Para dim.
3.3The Archetypical Case.
3.4De randomization of Time-complexity Classe
3.5 Space Pseudorandom Generators.
The Power of Probab tally Checkable Proofs.
PCP and Approximation.
More on PCP Itself.
The Role of Randomness.
Non-Interactive Proofs.
3.6.5 Dispersers， Extractors and Weak Random Sources
3.7ConcludingRernarks.
3.7.3 Open Problems.
A.Background on Randomness and Computation
A. 1 Probability Theory-Three Inequalities.
A. 2 Computational Models and Complexity Classes
A. 3 Complexity Classes-Glossary.
A. 4 Some Basic Cryptographic Settings.119
B.Randomized Computations.125
B. 1 Randomized Algorithms.125
B. 2 Randomness in Complexity Theory.135
A.2.1P， NP， and More.
A.2.2ProbablsticPolynomalTie.
A.2.3Non-Uniform Polynomial-Time.
A.2.4 Oracle Machines.
A.2.5 Space Bounded Machines
A.2.6 Average-Case Complexity.，
A.4.1 Encryption Schemes.
A.4.2 Digital Signatures and Message Authentication.
A.4.3TheRSAandRabin Functions.
B.1.1 Approx.Counting of DNF Sa ifying Assgn ments. 126
B.1.2 Finding a Perfect Matching .-. 127
B.1.3 Testing Whether Polynomials Are Identical . 130
B.1.4RandomiedRoundng Applied to Max SAT.132
B.1.5 Primality Testing.
B.1.6Tetng Graph Connectivity via