Hashing in Computer Science: Fifty Years of Slicing and Dicing

Hashing in Computer Science: Fifty Years of Slicing and Dicing

Released July 2010
Publisher(s): Wiley-Interscience
ISBN: 9780470344736

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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.

Table of contents

  1. Cover
  2. Half title page
  3. Title page
  4. Copyright page
  5. Dedication
  6. PREFACE
  7. Part I: MATHEMATICAL PRELIMINARIES
    1. CHAPTER 1 Counting
      1. 1.1 THE SUM AND PRODUCT RULES
      2. 1.2 MATHEMATICAL INDUCTION
      3. 1.3 FACTORIAL
      4. 1.4 BINOMIAL COEFFICIENTS
      5. 1.5 MULTINOMIAL COEFFICIENTS
      6. 1.6 PERMUTATIONS
      7. 1.7 COMBINATIONS
      8. 1.8 THE PRINCIPLE OF INCLUSION-EXCLUSION
      9. 1.9 PARTITIONS
      10. 1.10 RELATIONS
      11. 1.11 INVERSE RELATIONS
      12. APPENDIX 1 Summations Involving Binomial Coefficients
    2. CHAPTER 2 Recurrence and Generating Functions
      1. 2.1 RECURSIONS
      2. 2.2 GENERATING FUNCTIONS
      3. 2.3 LINEAR CONSTANT COEFFICIENT RECURSIONS
      4. 2.4 SOLVING HOMOGENEOUS LCCRS USING GENERATING FUNCTIONS
      5. 2.5 THE CATALAN RECURSION
      6. 2.6 THE UMBRAL CALCULUS4
      7. 2.7 EXPONENTIAL GENERATING FUNCTIONS
      8. 2.8 PARTITIONS OF A SET: THE BELL AND STIRLING NUMBERS
      9. 2.9 ROUCHÉ’S THEOREM AND THE LAGRANGE’S INVERSION FORMULA
    3. CHAPTER 3 Asymptotic Analysis
      1. 3.1 GROWTH NOTATION FOR SEQUENCES
      2. 3.2 ASYMPTOTIC SEQUENCES AND EXPANSIONS
      3. 3.3 SADDLE POINTS
      4. 3.4 LAPLACE’S METHOD
      5. 3.5 THE SADDLE POINT METHOD
      6. 3.6 WHEN WILL THE SADDLE POINT METHOD WORK?
      7. 3.7 SADDLE POINT BOUNDS
      8. 3.8 EXAMPLES OF SADDLE POINT ANALYSIS
    4. CHAPTER 4 Discrete Probability Theory
      1. 4.1 THE ORIGINS OF PROBABILITY THEORY
      2. 4.2 CHANCE EXPERIMENTS, SAMPLE POINTS, SPACES, AND EVENTS
      3. 4.3 RANDOM VARIABLES
      4. 4.4 MOMENTS—EXPECTATION AND VARIANCE
      5. 4.5 THE BIRTHDAY PARADOX1
      6. 4.6 CONDITIONAL PROBABILITY AND INDEPENDENCE
      7. 4.7 THE LAW OF LARGE NUMBERS (LLN)
      8. 4.8 THE CENTRAL LIMIT THEOREM (CLT)
      9. 4.9 RANDOM PROCESSES AND MARKOV CHAINS
    5. CHAPTER 5 Number Theory and Modern Algebra
      1. 5.1 PRIME NUMBERS
      2. 5.2 MODULAR ARITHMETIC AND THE EUCLIDEAN ALGORITHM
      3. 5.3 MODULAR MULTIPLICATION
      4. 5.4 THE THEOREMS OF FERMAT2 AND EULER
      5. 5.5 FIELDS AND EXTENSION FIELDS
      6. 5.6 FACTORIZATION OF INTEGERS
      7. 5.7 TESTING PRIMALITY
    6. CHAPTER 6 Basic Concepts of Cryptography
      1. 6.1 THE LEXICON OF CRYPTOGRAPHY
      2. 6.2 STREAM CIPHERS
      3. 6.3 BLOCK CIPHERS
      4. 6.4 SECRECY SYSTEMS AND CRYPTANALYSIS
      5. 6.5 SYMMETRIC AND TWO-KEY CRYPTOGRAPHIC SYSTEMS
      6. 6.6 THE APPEARANCE OF PUBLIC KEY CRYPTOGRAPHIC SYSTEMS
      7. 6.7 A MULTITUDE OF KEYS
      8. 6.8 THE RSA CRYPTOSYSTEM
      9. 6.9 DOES PKC SOLVE THE PROBLEM OF KEY DISTRIBUTION?
      10. 6.10 ELLIPTIC GROUPS OVER THE REALS
      11. 6.11 ELLIPTIC GROUPS OVER THE FIELD Zm,2
      12. 6.12 ELLIPTIC GROUPS CRYPTOSYSTEMS
      13. 6.13 THE MENEZES-VANSTONE ELLIPTIC CURVE CRYPTOSYSTEM
      14. 6.14 SUPER SINGULAR ELLIPTIC CURVES
  8. Part II: HASHING FOR STORAGE: DATA MANAGEMENT
    1. CHAPTER 7 Basic Concepts
      1. 7.1 OVERVIEW OF THE RECORDS MANAGEMENT PROBLEM
      2. 7.2 A SIMPLE STORAGE MANAGEMENT PROTOCOL: PLAIN VANILLA CHAINING
      3. 7.3 RECORD-MANAGEMENT WITH SORTED KEYS
    2. CHAPTER 8 Hash Functions
      1. 8.1 THE ORIGIN OF HASHING
      2. 8.2 HASH TABLES
      3. 8.3 A STATISTICAL MODEL FOR HASHING
      4. 8.4 THE LIKELIHOOD OF COLLISIONS
    3. CHAPTER 9 Hashing Functions: Examples and Evaluation
      1. 9.1 OVERVIEW: THE TRADEOFF OF RANDOMIZATION VERSUS COMPUTATIONAL SIMPLICITY
      2. 9.2 SOME EXAMPLES OF HASHING FUNCTIONS
      3. 9.3 PERFORMANCE OF HASHING FUNCTIONS: FORMULATION
      4. 9.4 THE χ2-TEST
      5. 9.5 TESTING A HASH FUNCTION
      6. 9.6 THE MCKENZIE ET AL. RESULTS
    4. CHAPTER 10 Record Chaining with Hash Tables
      1. 10.1 SEPARATE CHAINING OF RECORDS
      2. 10.2 ANALYSIS OF SEPARATE CHAINING HASHING SEQUENCES AND THE CHAINS THEY CREATE
      3. 10.3 A COMBINATORIAL ANALYSIS OF SEPARATE CHAINING
      4. 10.4 COALESCED CHAINING
      5. 10.5 THE PITTEL-YU ANALYSIS OF EICH COALESCED CHAINING
      6. 10.6 TO SEPARATE OR TO COALESCE; AND WHICH VERSION? THAT IS THE QUESTION
    5. CHAPTER 11 Perfect Hashing
      1. 11.1 OVERVIEW
      2. 11.2 CICHELLI’S CONSTRUCTION
    6. CHAPTER 12 The Uniform Hashing Model
      1. 12.1 AN IDEALIZED HASHING MODEL
      2. 12.2 THE ASYMPTOTICS OF UNIFORM HASHING
      3. 12.3 COLLISION-FREE HASHING
    7. CHAPTER 13 Hashing with Linear Probing
      1. 13.1 FORMULATION AND PRELIMINARIES
      2. 13.2 PERFORMANCE MEASURES FOR LP HASHING
      3. 13.3 ALL CELLS OTHER THAN HTn−1 IN THE HASH-TABLE OF n CELLS ARE OCCUPIED
      4. 13.4 m-KEYS HASHED INTO A HASH TABLE OF n CELLS LEAVING CELL HTn−1 UNOCCUPIED
      5. 13.5 THE PROBABILITY DISTRIBUTION FOR THE LENGTH OF A SEARCH
      6. 13.6 ASYMPTOTICS
      7. 13.7 HASHING WITH LINEAR OPEN ADDRESSING: CODA
      8. 13.8 A POSSIBLE IMPROVEMENT TO LINEAR PROBING
    8. CHAPTER 14 Double Hashing
      1. 14.1 FORMULATION OF DOUBLE HASHING1
      2. 14.2 PROGRESSIONS AND STRIDES
      3. 14.3 THE NUMBER OF PROGRESSIONS WHICH FILL A HASH-TABLE CELL
      4. 14.4 DOMINANCE
      5. 14.5 INSERTION-COST BOUNDS RELATING UNIFORM AND DOUBLE HASHING
      6. 14.6 USUALLYDOUBLEHASH
      7. 14.7 THE UDH CHANCE EXPERIMENT AND THE COST TO INSERT THE NEXT KEY BY DOUBLE HASHING
      8. 14.8 PROOF OF EQUATION (14.12a)
      9. 14.9 USUALLYDOUBLEHASH′
      10. 14.10 PROOF OF EQUATION (14.12b)
    9. CHAPTER 15 Optimum Hashing
      1. 15.1 THE ULLMAN–YAO FRAMEWORK1
      2. 15.2 THE RATES AT WHICH A CELL IS PROBED AND OCCUPIED
      3. 15.3 PARTITIONS OF (i)SCENARIOS, (i)SUBSCENARIOS, AND THEIR SKELETONS
      4. 15.4 RANDOMLY GENERATED m-SCENARIOS
      5. 15.5 BOUNDS ON RANDOM SUMS
      6. 15.6 COMPLETING THE PROOF OF THEOREM 15.1
  9. Part III: SOME NOVEL APPLICATIONS OF HASHING
    1. CHAPTER 16 Karp-Rabin String Searching
      1. 16.1 OVERVIEW
      2. 16.2 THE BASIC KARP-RABIN HASH-FINGERPRINT ALGORITHM
      3. 16.3 THE PLAIN VANILLA KARP-RABIN FINGERPRINT ALGORITHM
      4. 16.4 SOME ESTIMATES ON PRIME NUMBERS
      5. 16.5 THE COST OF FALSE MATCHES IN THE PLAIN VANILLA KARP-RABIN FINGERPRINT ALGORITHM
      6. 16.6 VARIATIONS ON THE PLAIN VANILLA KARP-RABIN FINGERPRINT ALGORITHM
      7. 16.7 A NONHASHING KARP-RABIN FINGERPRINT
    2. CHAPTER 17 Hashing Rock and Roll
      1. 17.1 OVERVIEW OF AUDIO FINGERPRINTING
      2. 17.2 THE BASICS OF FINGERPRINTING MUSIC
      3. 17.3 HAAR WAVELET CODING
      4. 17.4 MIN-HASH
      5. 17.5 SOME COMMERCIAL FINGERPRINTING PRODUCTS
    3. CHAPTER 18 Hashing in E-Commerce
      1. 18.1 THE VARIED APPLICATIONS OF CRYPTOGRAPHY
      2. 18.2 AUTHENTICATION
      3. 18.3 THE NEED FOR CERTIFICATES
      4. 18.4 CRYPTOGRAPHIC HASH FUNCTIONS
      5. 18.5 X.509 CERTIFICATES AND CCIT STANDARDIZATION
      6. 18.6 THE SECURE SOCKET LAYER (SSL)
      7. 18.7 TRUST ON THE WEB · · · TRUST NO ONE OVER 40!
      8. 18.8 MD5
      9. 18.9 CRITICISM OF MD5
      10. 18.10 THE WANG-YU COLLISION ATTACK
      11. 18.11 STEVEN’S IMPROVEMENT TO THE WANG-YU COLLISION ATTACK
      12. 18.12 THE CHOSEN-PREFIX ATTACK ON MD5
      13. 18.13 THE ROGUE CA ATTACK SCENARIO
      14. 18.14 THE SECURE HASH ALGORITHMS
      15. 18.15 CRITICISM OF SHA-1
      16. 18.16 SHA-2
      17. 18.17 WHAT NOW?
      18. APPENDIX 18 Sketch of the Steven’s Chosen Prefix Attack
      19. A18.1 BIRTHDAYING1 [SCHNEIER 1996, PP. 165–166], [OORSCHOT AND WIENER 1999]
      20. A18.2 THE BINARY SIGNED DIGIT REPRESENTATION (BSDR)
      21. A18.3 DIFFERENTIAL ANALYSIS
      22. A18.4 OUTLINE OF THE STEVENS CONSTRUCTION
    4. CHAPTER 19 Hashing and the Secure Distribution of Digital Media
      1. 19.1 OVERVIEW
      2. 19.2 INTELLECTUAL PROPERTY (COPYRIGHTS AND PATENTS)
      3. 19.3 STEGANOGRAPHY
      4. 19.4 BOIL, BOIL, TOIL AND · · · BUT FIRST, CAREFULLY MIX
      5. 19.5 SOFTWARE DISTRIBUTION SYSTEMS
      6. 19.6 WATERMARKS
      7. 19.7 AN IMAGE-PROCESSING TECHNIQUE FOR WATERMARKING
      8. 19.8 USING GEOMETRIC HASHING TO WATERMARK IMAGES
      9. 19.9 BIOMETRICS AND HASHING
      10. 19.10 THE DONGLE24
      11. APPENDIX 19 Reed-Solomon and Hadamard Coding
      12. A.19.0 CODES
      13. A.19.1 REED-SOLOMON CODES
      14. A.19.3 HADAMARD CODES
  10. Exercises and Solutions
    1. PART II, CHAPTER 7
    2. PART II, CHAPTER 8
    3. PART II, CHAPTER 10
    4. PART II, CHAPTER 11
    5. PART II, CHAPTER 12
    6. PART II, CHAPTER 13
    7. PART II, CHAPTER 14
    8. PART II, CHAPTER 15
    9. PART III, CHAPTER 16
    10. PART III, CHAPTER 17
    11. PART III, CHAPTER 18
    12. PART III, CHAPTER 19
  11. Index

Product information

  • Title: Hashing in Computer Science: Fifty Years of Slicing and Dicing
  • Author(s):
  • Release date: July 2010
  • Publisher(s): Wiley-Interscience
  • ISBN: 9780470344736