Contents

• Contents
• Traditional Encryption Systems
• Introduction to Number Theory
  • Congruences
  • The Greatest Common Divisor
  • Powers modulo a prime
  • Primitive roots
  • Proof of Theorem 5
• Encryption techniques based on powers and congruences
  • The Diffie-Hellman key exchange procedure
  • The Rivest-Shamir-Adleman public key system
  • A public key system as hard as factoring
• Subset-Sum (Knapsack) problems and their uses
  • Subset-sum problems are hard
  • A proposed public-key system based on subset-sum
  • Breaking Knapsack Cryptosystems
  • Other uses of the subset-sum problem
• Subset-Sum Problems and NP-Completeness
  • The Satisfiability Problem
  • Converting (SP) to (SSP)
  • Converting (SSP) to (SP)
  • Cook's Theorem
  • Terminology
• A probabilistic test for primality
  • Analysis of the Rabin test
• Probabilistic Encryption
  • The Goldwasser-Micali encryption system
  • Weak laws of large numbers
  • The magic of sampling
  • Determining algorithm performance by sampling
  • Two versions of QRA
  • Knowing a pseudo-square does not help much
  • The inability to distinguish two plaintexts
  • Semantic Security
  • How to play poker over the telephone
• Pseudo-random number generators
  • The Quadratic Generator
  • The Next Bit Theorem
  • The Efficient Test Theorem
• Further results on pseudo-random generators
  • Hard-Core Predicates and Pseudo-Random Numbers
  • Construction of hard-core predicates
  • A recent pseudo-random number generator