COMPLEXITY AND CRYPTOGRAPHY

By L. GAAND

CONTENTS BASICS OF CRYPTOGRAPHY CRYPTOGRAPHIC MODELS A BASIC SCENARIO: CRYPTOSYSTEMS CLASSICAL CRYPTOGRAPHY MODERN CRYPTOGRAPHY COMPLEXITY THEORY WHAT IS COMPLEXITY THEORY? DETERMINISTIC TURING MACHINES DECISION PROBLEMS AND LANGUAGES COMPLEXITY OF FUNCTIONS SPACE COMPLEXITY NON-DETERMINISTIC COMPUTATION NON-DETERMINISTIC POLYNOMIAL TIME – NP POLYNOMIAL TIME REDUCTIONS NP-COMPLETENESS TURING REDUCTIONS AND NP-HARDNESS COMPLEMENTS OF LANGUAGES IN NP CONTAINMENTS BETWEEN COMPLEXITY CLASSES NP REVISITED – NON-DETERMINISTIC TURING MACHINES PROBABILISTIC COMPUTATION CAN TOSSING COINS HELP? PROBABILISTIC TURING MACHINES AND RP PRIMALITY TESTING ZERO-ERROR PROBABILISTIC POLYNOMIAL TIME BOUNDED-ERROR PROBABILISTIC POLYNOMIAL TIME NON-UNIFORM POLYNOMIAL TIME CIRCUITS PROBABILISTIC CIRCUITS THE CIRCUIT COMPLEXITY OF MOST FUNCTIONS 4 10 HARDNESS RESULTS SYMMETRIC CRYPTOSYSTEMS INTRODUCTION THE ONE TIME PAD: VERNAM’S CRYPTOSYSTEM PERFECT SECRECY LINEAR SHIFT-REGISTER SEQUENCES LINEAR COMPLEXITY NON-LINEAR COMBINATION GENERATORS BLOCK CIPHERS AND DES RIJNDAEL AND THE AES THE POHLIG–HELLMAN CRYPTOSYSTEM ONE WAY FUNCTIONS IN SEARCH OF A DE?NITION STRONG ONE-WAY FUNCTIONS ONE WAY FUNCTIONS AND COMPLEXITY THEORY WEAK ONE-WAY FUNCTIONS PUBLIC KEY CRYPTOGRAPHY NON-SECRET ENCRYPTION THE COCKS–ELLIS NON-SECRET CRYPTOSYSTEM THE RSA CRYPTOSYSTEM THE ELGAMAL PUBLIC KEY CRYPTOSYSTEM PUBLIC KEY CRYPTOSYSTEMS AS TRAPDOOR FUNCTIONS INSECURITIES IN RSA FINDING THE RSA PRIVATE KEY AND FACTORING RABIN’S PUBLIC KEY CRYPTOSYSTEM PUBLIC KEY SYSTEMS BASED ON NP-HARD PROBLEMS 7 10 PROBLEMS WITH TRAPDOOR SYSTEMS DIGITAL SIGNATURES PUBLIC KEY-BASED SIGNATURE SCHEMES ATTACKS AND SECURITY OF SIGNATURE SCHEMES SIGNATURES WITH PRIVACY THE IMPORTANCE OF HASHING THE BIRTHDAY ATTACK KEY ESTABLISHMENT PROTOCOLS THE BASIC PROBLEMS KEY DISTRIBUTION WITH SECURE CHANNELS DIF?E–HELLMAN KEY ESTABLISHMENT AUTHENTICATED KEY DISTRIBUTION SECRET SHARING SHAMIR’S SECRET SHARING SCHEME SECURE ENCRYPTION 10 1 INTRODUCTION 10 2 PSEUDORANDOM GENERATORS 10 3 HARD AND EASY BITS OF ONE-WAY FUNCTIONS 10 4 PSEUDORANDOM GENERATORS FROM HARD-CORE PREDICATES 10 5 PROBABILISTIC ENCRYPTION 10 6 EF?CIENT PROBABILISTIC ENCRYPTION IDENTI?CATION SCHEMES 11 1 INTRODUCTION 11 2 INTERACTIVE PROOFS 11 3 ZERO KNOWLEDGE 11 4 PERFECT ZERO-KNOWLEDGE PROOFS 11 5 COMPUTATIONAL ZERO KNOWLEDGE 11 6 THE FIAT–SHAMIR IDENTI?CATION SCHEME APPENDIX