Hashing in Computer Science by Konheim, Alan G. -- Read -- Imperial Library of Trantor

Index

Cover Half title page Title page Copyright page Dedication PREFACE Part I: MATHEMATICAL PRELIMINARIES

CHAPTER 1 Counting

1.1 THE SUM AND PRODUCT RULES 1.2 MATHEMATICAL INDUCTION 1.3 FACTORIAL 1.4 BINOMIAL COEFFICIENTS 1.5 MULTINOMIAL COEFFICIENTS 1.6 PERMUTATIONS 1.7 COMBINATIONS 1.8 THE PRINCIPLE OF INCLUSION-EXCLUSION 1.9 PARTITIONS 1.10 RELATIONS 1.11 INVERSE RELATIONS APPENDIX 1 Summations Involving Binomial Coefficients

CHAPTER 2 Recurrence and Generating Functions

2.1 RECURSIONS 2.2 GENERATING FUNCTIONS 2.3 LINEAR CONSTANT COEFFICIENT RECURSIONS 2.4 SOLVING HOMOGENEOUS LCCRS USING GENERATING FUNCTIONS 2.5 THE CATALAN RECURSION 2.6 THE UMBRAL CALCULUS4 2.7 EXPONENTIAL GENERATING FUNCTIONS 2.8 PARTITIONS OF A SET: THE BELL AND STIRLING NUMBERS 2.9 ROUCHÉ’S THEOREM AND THE LAGRANGE’S INVERSION FORMULA

CHAPTER 3 Asymptotic Analysis

3.1 GROWTH NOTATION FOR SEQUENCES 3.2 ASYMPTOTIC SEQUENCES AND EXPANSIONS 3.3 SADDLE POINTS 3.4 LAPLACE’S METHOD 3.5 THE SADDLE POINT METHOD 3.6 WHEN WILL THE SADDLE POINT METHOD WORK? 3.7 SADDLE POINT BOUNDS 3.8 EXAMPLES OF SADDLE POINT ANALYSIS

CHAPTER 4 Discrete Probability Theory

4.1 THE ORIGINS OF PROBABILITY THEORY 4.2 CHANCE EXPERIMENTS, SAMPLE POINTS, SPACES, AND EVENTS 4.3 RANDOM VARIABLES 4.4 MOMENTS—EXPECTATION AND VARIANCE 4.5 THE BIRTHDAY PARADOX1 4.6 CONDITIONAL PROBABILITY AND INDEPENDENCE 4.7 THE LAW OF LARGE NUMBERS (LLN) 4.8 THE CENTRAL LIMIT THEOREM (CLT) 4.9 RANDOM PROCESSES AND MARKOV CHAINS

CHAPTER 5 Number Theory and Modern Algebra

5.1 PRIME NUMBERS 5.2 MODULAR ARITHMETIC AND THE EUCLIDEAN ALGORITHM 5.3 MODULAR MULTIPLICATION 5.4 THE THEOREMS OF FERMAT2 AND EULER 5.5 FIELDS AND EXTENSION FIELDS 5.6 FACTORIZATION OF INTEGERS 5.7 TESTING PRIMALITY

CHAPTER 6 Basic Concepts of Cryptography

6.1 THE LEXICON OF CRYPTOGRAPHY 6.2 STREAM CIPHERS 6.3 BLOCK CIPHERS 6.4 SECRECY SYSTEMS AND CRYPTANALYSIS 6.5 SYMMETRIC AND TWO-KEY CRYPTOGRAPHIC SYSTEMS 6.6 THE APPEARANCE OF PUBLIC KEY CRYPTOGRAPHIC SYSTEMS 6.7 A MULTITUDE OF KEYS 6.8 THE RSA CRYPTOSYSTEM 6.9 DOES PKC SOLVE THE PROBLEM OF KEY DISTRIBUTION? 6.10 ELLIPTIC GROUPS OVER THE REALS 6.11 ELLIPTIC GROUPS OVER THE FIELD Zm,2 6.12 ELLIPTIC GROUPS CRYPTOSYSTEMS 6.13 THE MENEZES-VANSTONE ELLIPTIC CURVE CRYPTOSYSTEM 6.14 SUPER SINGULAR ELLIPTIC CURVES

Part II: HASHING FOR STORAGE: DATA MANAGEMENT

CHAPTER 7 Basic Concepts

CHAPTER 8 Hash Functions

8.1 THE ORIGIN OF HASHING 8.2 HASH TABLES 8.3 A STATISTICAL MODEL FOR HASHING 8.4 THE LIKELIHOOD OF COLLISIONS

CHAPTER 9 Hashing Functions: Examples and Evaluation

9.1 OVERVIEW: THE TRADEOFF OF RANDOMIZATION VERSUS COMPUTATIONAL SIMPLICITY 9.2 SOME EXAMPLES OF HASHING FUNCTIONS 9.3 PERFORMANCE OF HASHING FUNCTIONS: FORMULATION 9.4 THE χ2-TEST 9.5 TESTING A HASH FUNCTION 9.6 THE MCKENZIE ET AL. RESULTS

CHAPTER 10 Record Chaining with Hash Tables

CHAPTER 11 Perfect Hashing

11.1 OVERVIEW 11.2 CICHELLI’S CONSTRUCTION

CHAPTER 12 The Uniform Hashing Model

12.1 AN IDEALIZED HASHING MODEL 12.2 THE ASYMPTOTICS OF UNIFORM HASHING 12.3 COLLISION-FREE HASHING

CHAPTER 13 Hashing with Linear Probing

CHAPTER 14 Double Hashing

14.1 FORMULATION OF DOUBLE HASHING1 14.2 PROGRESSIONS AND STRIDES 14.3 THE NUMBER OF PROGRESSIONS WHICH FILL A HASH-TABLE CELL 14.4 DOMINANCE 14.5 INSERTION-COST BOUNDS RELATING UNIFORM AND DOUBLE HASHING 14.6 USUALLYDOUBLEHASH 14.7 THE UDH CHANCE EXPERIMENT AND THE COST TO INSERT THE NEXT KEY BY DOUBLE HASHING 14.8 PROOF OF EQUATION (14.12a) 14.9 USUALLYDOUBLEHASH′ 14.10 PROOF OF EQUATION (14.12b)

CHAPTER 15 Optimum Hashing

15.1 THE ULLMAN–YAO FRAMEWORK1 15.2 THE RATES AT WHICH A CELL IS PROBED AND OCCUPIED 15.3 PARTITIONS OF (i)SCENARIOS, (i)SUBSCENARIOS, AND THEIR SKELETONS 15.4 RANDOMLY GENERATED m-SCENARIOS 15.5 BOUNDS ON RANDOM SUMS 15.6 COMPLETING THE PROOF OF THEOREM 15.1

Part III: SOME NOVEL APPLICATIONS OF HASHING

CHAPTER 16 Karp-Rabin String Searching

CHAPTER 17 Hashing Rock and Roll

17.1 OVERVIEW OF AUDIO FINGERPRINTING 17.2 THE BASICS OF FINGERPRINTING MUSIC 17.3 HAAR WAVELET CODING 17.4 MIN-HASH 17.5 SOME COMMERCIAL FINGERPRINTING PRODUCTS

CHAPTER 18 Hashing in E-Commerce

18.1 THE VARIED APPLICATIONS OF CRYPTOGRAPHY 18.2 AUTHENTICATION 18.3 THE NEED FOR CERTIFICATES 18.4 CRYPTOGRAPHIC HASH FUNCTIONS 18.5 X.509 CERTIFICATES AND CCIT STANDARDIZATION 18.6 THE SECURE SOCKET LAYER (SSL) 18.7 TRUST ON THE WEB · · · TRUST NO ONE OVER 40! 18.8 MD5 18.9 CRITICISM OF MD5 18.10 THE WANG-YU COLLISION ATTACK 18.11 STEVEN’S IMPROVEMENT TO THE WANG-YU COLLISION ATTACK 18.12 THE CHOSEN-PREFIX ATTACK ON MD5 18.13 THE ROGUE CA ATTACK SCENARIO 18.14 THE SECURE HASH ALGORITHMS 18.15 CRITICISM OF SHA-1 18.16 SHA-2 18.17 WHAT NOW? APPENDIX 18 Sketch of the Steven’s Chosen Prefix Attack A18.1 BIRTHDAYING1 [SCHNEIER 1996, PP. 165–166], [OORSCHOT AND WIENER 1999] A18.2 THE BINARY SIGNED DIGIT REPRESENTATION (BSDR) A18.3 DIFFERENTIAL ANALYSIS A18.4 OUTLINE OF THE STEVENS CONSTRUCTION

CHAPTER 19 Hashing and the Secure Distribution of Digital Media

19.1 OVERVIEW 19.2 INTELLECTUAL PROPERTY (COPYRIGHTS AND PATENTS) 19.3 STEGANOGRAPHY 19.4 BOIL, BOIL, TOIL AND · · · BUT FIRST, CAREFULLY MIX 19.5 SOFTWARE DISTRIBUTION SYSTEMS 19.6 WATERMARKS 19.7 AN IMAGE-PROCESSING TECHNIQUE FOR WATERMARKING 19.8 USING GEOMETRIC HASHING TO WATERMARK IMAGES 19.9 BIOMETRICS AND HASHING 19.10 THE DONGLE24 APPENDIX 19 Reed-Solomon and Hadamard Coding A.19.0 CODES A.19.1 REED-SOLOMON CODES A.19.3 HADAMARD CODES

Exercises and Solutions

PART II, CHAPTER 7 PART II, CHAPTER 8 PART II, CHAPTER 10 PART II, CHAPTER 11 PART II, CHAPTER 12 PART II, CHAPTER 13 PART II, CHAPTER 14 PART II, CHAPTER 15 PART III, CHAPTER 16 PART III, CHAPTER 17 PART III, CHAPTER 18 PART III, CHAPTER 19

Index