FOUNDATIONS OF CRYPTOGRAPHY: BASIC TECHNIQUES
CONTENTS 1 INTRODUCTION 1 1 CRYPTOGRAPHY: MAIN TOPICS 1 1 1 ENCRYPTION SCHEMES 1 1 2 PSEUDORANDOM GENERATORS 1 1 3 DIGITAL SIGNATURES 1 1 4 FAULT-TOLERANT PROTOCOLS AND ZERO-KNOWLEDGE PROOFS 1 2 SOME BACKGROUND FROM PROBABILITY THEORY 1 2 1 NOTATIONAL CONVENTIONS 1 2 2 THREE INEQUALITIES 1 3 THE COMPUTATIONAL MODEL 1 3 1 P, NP, AND NP-COMPLETENESS 1 3 2 PROBABILISTIC POLYNOMIAL TIME 1 3 3 NON-UNIFORM POLYNOMIAL TIME 1 3 4 INTRACTABILITY ASSUMPTIONS 1 3 5 ORACLE MACHINES 1 4 MOTIVATION TO THE RIGOROUS TREATMENT 1 4 1 THE NEED FOR A RIGOROUS TREATMENT 1 4 2 PRACTICAL CONSEQUENCES OF THE RIGOROUS TREATMENT 1 4 3 THE TENDENCY TO BE CONSERVATIVE 1 5 MISCELLANEOUS 1 5 1 HISTORICAL NOTES 1 5 2 SUGGESTIONS FOR FURTHER READING 1 5 3 OPEN PROBLEMS 1 5 4 EXERCISES 2 COMPUTATIONAL DIFFICULTY 2 1 ONE-WAY FUNCTIONS: MOTIVATION 2 2 ONE-WAY FUNCTIONS: DE?NITIONS 2 2 1 STRONG ONE-WAY FUNCTIONS 2 2 2 WEAK ONE-WAY FUNCTIONS 2 2 3 TWO USEFUL LENGTH CONVENTIONS 2 2 4 CANDIDATES FOR ONE-WAY FUNCTIONS 2 2 5 NON-UNIFORMLY ONE-WAY FUNCTIONS WEAK ONE-WAY FUNCTIONS IMPLY STRONG ONES 2 3 1 THE CONSTRUCTION AND ITS ANALYSIS (PROOF OF THEOREM 2 3 2) 2 3 2 ILLUSTRATION BY A TOY EXAMPLE 2 3 3 DISCUSSION 2 4 ONE-WAY FUNCTIONS: VARIATIONS 2 4 1 ? UNIVERSAL ONE-WAY FUNCTION 2 4 2 ONE-WAY FUNCTIONS AS COLLECTIONS 2 4 3 EXAMPLES OF ONE-WAY COLLECTIONS 2 4 4 TRAPDOOR ONE-WAY PERMUTATIONS 2 4 5 ? CLAW-FREE FUNCTIONS 2 4 6 ? ON PROPOSING CANDIDATES 2 5 HARD-CORE PREDICATES 2 5 1 DE?NITION 2 5 2 HARD-CORE PREDICATES FOR ANY ONE-WAY FUNCTION 2 5 3 ? HARD-CORE FUNCTIONS 2 6 ? EF?CIENT AMPLI?CATION OF ONE-WAY FUNCTIONS 2 6 1 THE CONSTRUCTION 2 6 2 ANALYSIS 2 7 MISCELLANEOUS 2 7 1 HISTORICAL NOTES 2 7 2 SUGGESTIONS FOR FURTHER READING 2 7 3 OPEN PROBLEMS 2 7 4 EXERCISES 3 PSEUDORANDOM GENERATORS 3 1 MOTIVATING DISCUSSION 3 1 1 COMPUTATIONAL APPROACHES TO RANDOMNESS 3 1 2 A RIGOROUS APPROACH TO PSEUDORANDOM GENERATORS 3 2 COMPUTATIONAL INDISTINGUISHABILITY 3 2 1 DE?NITION 3 2 2 RELATION TO STATISTICAL CLOSENESS 3 2 3 INDISTINGUISHABILITY BY REPEATED EXPERIMENTS 3 2 4 ? INDISTINGUISHABILITY BY CIRCUITS 3 2 5 PSEUDORANDOM ENSEMBLES 3 3 DE?NITIONS OF PSEUDORANDOM GENERATORS 3 3 1 STANDARD DE?NITION OF PSEUDORANDOM GENERATORS 3 3 2 INCREASING THE EXPANSION FACTOR 3 3 3 ? VARIABLE-OUTPUT PSEUDORANDOM GENERATORS 3 3 4 THE APPLICABILITY OF PSEUDORANDOM GENERATORS 3 3 5 PSEUDORANDOMNESS AND UNPREDICTABILITY 3 3 6 PSEUDORANDOM GENERATORS IMPLY ONE-WAY FUNCTIONS 3 4 CONSTRUCTIONS BASED ON ONE-WAY PERMUTATIONS 3 4 1 CONSTRUCTION BASED ON A SINGLE PERMUTATION 3 4 2 CONSTRUCTION BASED ON COLLECTIONS OF PERMUTATIONS 3 4 3 ? USING HARD-CORE FUNCTIONS RATHER THAN PREDICATES 3 5 ? CONSTRUCTIONS BASED ON ONE-WAY FUNCTIONS 3 5 1 USING 1-1 ONE-WAY FUNCTIONS 3 5 2 USING REGULAR ONE-WAY FUNCTIONS 3 5 3 GOING BEYOND REGULAR ONE-WAY FUNCTIONS 3 6 PSEUDORANDOM FUNCTIONS 3 6 1 DE?NITIONS 3 6 2 CONSTRUCTION 3 6 3 APPLICATIONS: A GENERAL METHODOLOGY 3 6 4 ? GENERALIZATIONS 3 7 ? PSEUDORANDOM PERMUTATIONS 3 7 1 DE?NITIONS 3 7 2 CONSTRUCTION 3 8 MISCELLANEOUS 3 8 1 HISTORICAL NOTES 3 8 2 SUGGESTIONS FOR FURTHER READING 3 8 3 OPEN PROBLEMS 3 8 4 EXERCISES 4 ZERO-KNOWLEDGE PROOF SYSTEMS 4 1 ZERO-KNOWLEDGE PROOFS: MOTIVATION 4 1 1 THE NOTION OF A PROOF 4 1 2 GAINING KNOWLEDGE 4 2 INTERACTIVE PROOF SYSTEMS 4 2 1 DE?NITION 4 2 2 AN EXAMPLE (GRAPH NON-ISOMORPHISM IN IP) 4 2 3 ? THE STRUCTURE OF THE CLASS IP 4 2 4 AUGMENTATION OF THE MODEL 4 3 ZERO-KNOWLEDGE PROOFS: DE?NITIONS 4 3 1 PERFECT AND COMPUTATIONAL ZERO-KNOWLEDGE 4 3 2 AN EXAMPLE (GRAPH ISOMORPHISM IN PZK) 4 3 3 ZERO-KNOWLEDGE WITH RESPECT TO AUXILIARY INPUTS 4 3 4 SEQUENTIAL COMPOSITION OF ZERO-KNOWLEDGE PROOFS 4 4 ZERO-KNOWLEDGE PROOFS FOR NP 4 4 1 COMMITMENT SCHEMES 4 4 2 ZERO-KNOWLEDGE PROOF OF GRAPH COLORING 4 4 3 THE GENERAL RESULT AND SOME APPLICATIONS 4 4 4 SECOND-LEVEL CONSIDERATIONS 4 5 ? NEGATIVE RESULTS 4 5 1 ON THE IMPORTANCE OF INTERACTION AND RANDOMNESS 4 5 2 LIMITATIONS OF UNCONDITIONAL RESULTS 4 5 3 LIMITATIONS OF STATISTICAL ZK PROOFS 4 5 4 ZERO-KNOWLEDGE AND PARALLEL COMPOSITION 4 6 ? WITNESS INDISTINGUISHABILITY AND HIDING 4 6 1 DE?NITIONS 4 6 2 PARALLEL COMPOSITION 4 6 3 CONSTRUCTIONS 4 6 4 APPLICATIONS 4 7 ? PROOFS OF KNOWLEDGE 4 7 1 DE?NITION 4 7 2 REDUCING THE KNOWLEDGE ERROR 4 7 3 ZERO-KNOWLEDGE PROOFS OF KNOWLEDGE FOR NP 4 7 4 APPLICATIONS 4 7 5 PROOFS OF IDENTITY (IDENTI?CATION SCHEMES) 4 7 6 STRONG PROOFS OF KNOWLEDGE 4 8 ? COMPUTATIONALLY SOUND PROOFS (ARGUMENTS) 4 8 1 DE?NITION 4 8 2 PERFECTLY HIDING COMMITMENT SCHEMES 4 8 3 PERFECT ZERO-KNOWLEDGE ARGUMENTS FOR NP 4 8 4 ARGUMENTS OF POLY-LOGARITHMIC EF?CIENCY 4 9 ? CONSTANT-ROUND ZERO-KNOWLEDGE PROOFS 4 9 1 USING COMMITMENT SCHEMES WITH PERFECT SECRECY 4 9 2 BOUNDING THE POWER OF CHEATING PROVERS 4 10 ? NON-INTERACTIVE ZERO-KNOWLEDGE PROOFS 4 10 1 BASIC DE?NITIONS 4 10 2 CONSTRUCTIONS 4 10 3 EXTENSIONS 4 11 ? MULTI-PROVER ZERO-KNOWLEDGE PROOFS 4 11 1 DE?NITIONS 4 11 2 TWO-SENDER COMMITMENT SCHEMES 4 11 3 PERFECT ZERO-KNOWLEDGE FOR NP 4 11 4 APPLICATIONS 4 12 MISCELLANEOUS 4 12 1 HISTORICAL NOTES 4 12 2 SUGGESTIONS FOR FURTHER READING 4 12 3 OPEN PROBLEMS 4 12 4 EXERCISES