book

Hashing in Computer Science: Fifty Years of Slicing and Dicing

by Alan G. Konheim

July 2010

Intermediate to advanced

386 pages

10h 9m

English

Wiley-Interscience

Read now

Unlock full access

CHAPTER 1 Counting1.1 THE SUM AND PRODUCT RULES1.2 MATHEMATICAL INDUCTION1.3 FACTORIAL1.4 BINOMIAL COEFFICIENTS1.5 MULTINOMIAL COEFFICIENTS1.6 PERMUTATIONS1.7 COMBINATIONS1.8 THE PRINCIPLE OF INCLUSION-EXCLUSION1.9 PARTITIONS1.10 RELATIONS1.11 INVERSE RELATIONSAPPENDIX 1 Summations Involving Binomial Coefficients
2.1 RECURSIONS2.2 GENERATING FUNCTIONS2.3 LINEAR CONSTANT COEFFICIENT RECURSIONS2.4 SOLVING HOMOGENEOUS LCCRS USING GENERATING FUNCTIONS2.5 THE CATALAN RECURSION2.6 THE UMBRAL CALCULUS42.7 EXPONENTIAL GENERATING FUNCTIONS2.8 PARTITIONS OF A SET: THE BELL AND STIRLING NUMBERS2.9 ROUCHÉ’S THEOREM AND THE LAGRANGE’S INVERSION FORMULA
3.1 GROWTH NOTATION FOR SEQUENCES3.2 ASYMPTOTIC SEQUENCES AND EXPANSIONS3.3 SADDLE POINTS3.4 LAPLACE’S METHOD3.5 THE SADDLE POINT METHOD3.6 WHEN WILL THE SADDLE POINT METHOD WORK?3.7 SADDLE POINT BOUNDS3.8 EXAMPLES OF SADDLE POINT ANALYSIS
4.1 THE ORIGINS OF PROBABILITY THEORY4.2 CHANCE EXPERIMENTS, SAMPLE POINTS, SPACES, AND EVENTS4.3 RANDOM VARIABLES4.4 MOMENTS—EXPECTATION AND VARIANCE4.5 THE BIRTHDAY PARADOX14.6 CONDITIONAL PROBABILITY AND INDEPENDENCE4.7 THE LAW OF LARGE NUMBERS (LLN)4.8 THE CENTRAL LIMIT THEOREM (CLT)4.9 RANDOM PROCESSES AND MARKOV CHAINS

5.1 PRIME NUMBERS5.2 MODULAR ARITHMETIC AND THE EUCLIDEAN ALGORITHM5.3 MODULAR MULTIPLICATION5.4 THE THEOREMS OF FERMAT2 AND EULER5.5 FIELDS AND EXTENSION FIELDS5.6 FACTORIZATION OF INTEGERS5.7 TESTING PRIMALITY
6.1 THE LEXICON OF CRYPTOGRAPHY6.2 STREAM CIPHERS6.3 BLOCK CIPHERS6.4 SECRECY SYSTEMS AND CRYPTANALYSIS6.5 SYMMETRIC AND TWO-KEY CRYPTOGRAPHIC SYSTEMS6.6 THE APPEARANCE OF PUBLIC KEY CRYPTOGRAPHIC SYSTEMS6.7 A MULTITUDE OF KEYS6.8 THE RSA CRYPTOSYSTEM6.9 DOES PKC SOLVE THE PROBLEM OF KEY DISTRIBUTION?6.10 ELLIPTIC GROUPS OVER THE REALS6.11 ELLIPTIC GROUPS OVER THE FIELD Zm,26.12 ELLIPTIC GROUPS CRYPTOSYSTEMS6.13 THE MENEZES-VANSTONE ELLIPTIC CURVE CRYPTOSYSTEM6.14 SUPER SINGULAR ELLIPTIC CURVES
CHAPTER 7 Basic Concepts7.1 OVERVIEW OF THE RECORDS MANAGEMENT PROBLEM7.2 A SIMPLE STORAGE MANAGEMENT PROTOCOL: PLAIN VANILLA CHAINING7.3 RECORD-MANAGEMENT WITH SORTED KEYS
8.1 THE ORIGIN OF HASHING8.2 HASH TABLES8.3 A STATISTICAL MODEL FOR HASHING8.4 THE LIKELIHOOD OF COLLISIONS
9.1 OVERVIEW: THE TRADEOFF OF RANDOMIZATION VERSUS COMPUTATIONAL SIMPLICITY9.2 SOME EXAMPLES OF HASHING FUNCTIONS9.3 PERFORMANCE OF HASHING FUNCTIONS: FORMULATION9.4 THE χ2-TEST9.5 TESTING A HASH FUNCTION9.6 THE MCKENZIE ET AL. RESULTS
10.1 SEPARATE CHAINING OF RECORDS10.2 ANALYSIS OF SEPARATE CHAINING HASHING SEQUENCES AND THE CHAINS THEY CREATE10.3 A COMBINATORIAL ANALYSIS OF SEPARATE CHAINING10.4 COALESCED CHAINING10.5 THE PITTEL-YU ANALYSIS OF EICH COALESCED CHAINING10.6 TO SEPARATE OR TO COALESCE; AND WHICH VERSION? THAT IS THE QUESTION
11.1 OVERVIEW11.2 CICHELLI’S CONSTRUCTION
12.1 AN IDEALIZED HASHING MODEL12.2 THE ASYMPTOTICS OF UNIFORM HASHING12.3 COLLISION-FREE HASHING
13.1 FORMULATION AND PRELIMINARIES13.2 PERFORMANCE MEASURES FOR LP HASHING13.3 ALL CELLS OTHER THAN HTn−1 IN THE HASH-TABLE OF n CELLS ARE OCCUPIED13.4 m-KEYS HASHED INTO A HASH TABLE OF n CELLS LEAVING CELL HTn−1 UNOCCUPIED13.5 THE PROBABILITY DISTRIBUTION FOR THE LENGTH OF A SEARCH13.6 ASYMPTOTICS13.7 HASHING WITH LINEAR OPEN ADDRESSING: CODA13.8 A POSSIBLE IMPROVEMENT TO LINEAR PROBING
14.1 FORMULATION OF DOUBLE HASHING114.2 PROGRESSIONS AND STRIDES14.3 THE NUMBER OF PROGRESSIONS WHICH FILL A HASH-TABLE CELL14.4 DOMINANCE14.5 INSERTION-COST BOUNDS RELATING UNIFORM AND DOUBLE HASHING14.6 USUALLYDOUBLEHASH14.7 THE UDH CHANCE EXPERIMENT AND THE COST TO INSERT THE NEXT KEY BY DOUBLE HASHING14.8 PROOF OF EQUATION (14.12a)14.9 USUALLYDOUBLEHASH′14.10 PROOF OF EQUATION (14.12b)
15.1 THE ULLMAN–YAO FRAMEWORK115.2 THE RATES AT WHICH A CELL IS PROBED AND OCCUPIED15.3 PARTITIONS OF (i)SCENARIOS, (i)SUBSCENARIOS, AND THEIR SKELETONS15.4 RANDOMLY GENERATED m-SCENARIOS15.5 BOUNDS ON RANDOM SUMS15.6 COMPLETING THE PROOF OF THEOREM 15.1
CHAPTER 16 Karp-Rabin String Searching16.1 OVERVIEW16.2 THE BASIC KARP-RABIN HASH-FINGERPRINT ALGORITHM16.3 THE PLAIN VANILLA KARP-RABIN FINGERPRINT ALGORITHM16.4 SOME ESTIMATES ON PRIME NUMBERS16.5 THE COST OF FALSE MATCHES IN THE PLAIN VANILLA KARP-RABIN FINGERPRINT ALGORITHM16.6 VARIATIONS ON THE PLAIN VANILLA KARP-RABIN FINGERPRINT ALGORITHM16.7 A NONHASHING KARP-RABIN FINGERPRINT
17.1 OVERVIEW OF AUDIO FINGERPRINTING17.2 THE BASICS OF FINGERPRINTING MUSIC17.3 HAAR WAVELET CODING17.4 MIN-HASH17.5 SOME COMMERCIAL FINGERPRINTING PRODUCTS
18.1 THE VARIED APPLICATIONS OF CRYPTOGRAPHY18.2 AUTHENTICATION18.3 THE NEED FOR CERTIFICATES18.4 CRYPTOGRAPHIC HASH FUNCTIONS18.5 X.509 CERTIFICATES AND CCIT STANDARDIZATION18.6 THE SECURE SOCKET LAYER (SSL)18.7 TRUST ON THE WEB · · · TRUST NO ONE OVER 40!18.8 MD518.9 CRITICISM OF MD518.10 THE WANG-YU COLLISION ATTACK18.11 STEVEN’S IMPROVEMENT TO THE WANG-YU COLLISION ATTACK18.12 THE CHOSEN-PREFIX ATTACK ON MD518.13 THE ROGUE CA ATTACK SCENARIO18.14 THE SECURE HASH ALGORITHMS18.15 CRITICISM OF SHA-118.16 SHA-218.17 WHAT NOW?APPENDIX 18 Sketch of the Steven’s Chosen Prefix AttackA18.1 BIRTHDAYING1 [SCHNEIER 1996, PP. 165–166], [OORSCHOT AND WIENER 1999]A18.2 THE BINARY SIGNED DIGIT REPRESENTATION (BSDR)A18.3 DIFFERENTIAL ANALYSISA18.4 OUTLINE OF THE STEVENS CONSTRUCTION
19.1 OVERVIEW19.2 INTELLECTUAL PROPERTY (COPYRIGHTS AND PATENTS)19.3 STEGANOGRAPHY19.4 BOIL, BOIL, TOIL AND · · · BUT FIRST, CAREFULLY MIX19.5 SOFTWARE DISTRIBUTION SYSTEMS19.6 WATERMARKS19.7 AN IMAGE-PROCESSING TECHNIQUE FOR WATERMARKING19.8 USING GEOMETRIC HASHING TO WATERMARK IMAGES19.9 BIOMETRICS AND HASHING19.10 THE DONGLE24APPENDIX 19 Reed-Solomon and Hadamard CodingA.19.0 CODESA.19.1 REED-SOLOMON CODESA.19.3 HADAMARD CODES
PART II, CHAPTER 7PART II, CHAPTER 8PART II, CHAPTER 10PART II, CHAPTER 11PART II, CHAPTER 12PART II, CHAPTER 13PART II, CHAPTER 14PART II, CHAPTER 15PART III, CHAPTER 16PART III, CHAPTER 17PART III, CHAPTER 18PART III, CHAPTER 19

Overview

Written by one of the developers of the technology, Hashing is both a historical document on the development of hashing and an analysis of the applications of hashing in a society increasingly concerned with security. The material in this book is based on courses taught by the author, and key points are reinforced in sample problems and an accompanying instructor s manual. Graduate students and researchers in mathematics, cryptography, and security will benefit from this overview of hashing and the complicated mathematics that it requires.