Strongly Universal Hash Families in Cryptography

Introduction

Cyber threats and fraud are rising daily to steal public data. Cryptography encrypts information, text messages, and emails using a Cipher algorithm. It ensures authentication and security against these threats and protects them. It is an essential part of Network Security. With an increase in technology involvement, the applications of Cryptography have increased to another level.

In this blog, we will understand various theorems of one of the foundational concepts of Unconditionally Secure MACs- Strongly Universal Hash Families in Cryptography. We will also learn in brief about Universal Hashing and Hash Families.

What is Universal Hashing?

Before moving into the concept of Universal Hashing, we must have a brief idea about Hashing.

Hashing is an efficient tool used in many different areas. It includes Cryptography, complexity theory, dictionary data structure, etc. There are two types of hashing- Universal Hashing and Perfect Hashing. In this blog, we will mainly focus on Universal Hashing. 

Universal Hashing is a process of randomly selecting a hash function with a certain mathematical property from a family of hash functions. The selection must be such that it expects low number of collisions. The most commonly used universal hash families are for hashing integers, strings, and vectors to make their calculation quite efficient. Universal Hash Families have several fascinating applications- implementation of hash tables, randomized algorithms, and especially cryptography.

Strongly Universal Hash Families in Cryptography

You already learned that strongly universal hash families have several applications. We will continue with the definition of hash families.

Suppose that (X, Y, K, H) is an (N, M) hash family. The given below hash family is strongly universal with this condition satisfied: x, x’ ∈ X such that x ≠ x’, and for every y, y’ ∈ Y.

|{K ∈ K : h_K(x) = y, h_K(x’) = y’}| = |K|/M2

Intuitive Proof:

Suppose we fix x and x’ and x’ ≠  x. There are M² possibilities for the ordered pair (y, y’). The definition above says that the number of hash functions in the family H mapping x to y and x’ to y’ is independent of the selection of y and y’. We know that there are total |K| hash functions, so this number becomes |K|/M2.

You must know that strongly universal hash families immediately output authentication codes. You can easily calculate Pd₀ and Pd₁ using these codes. Now, we will have a look on the mathematical proof of strongly universal hash families.

Mathematical Proof:

Let x, x’ ∈ X and y ∈ Y be fixed, where x’ ≠ x’ . Then we have the following:

Theorems

Certain theorems that conclude the properties of strongly universal hash families are given below.

First Theorem:

Suppose that (X, Y, K, H) is a strongly universal (N, M)- hash family. Then (X, Y, K, H) is an authentication code with Pd₀ = Pd₁ = 1/M.

We know that,

{K ∈ K : h_K(x) = y, h_K(x’) = y’}| = |K|/M2

for every x ∈ X and y ∈ Y. Therefore, payoff(x,y) becomes 1/M and hence Pd₀= 1/M.

Proof-

Second Theorem:

Let p be prime. For a, b ∈ Zp, define f_(a,b): Zp → Zp by the rule:

f_(a,b) (x) = ax + b mod p

Then (Zp, Zp, Zp × Zp, {f_(a,b) : a, b ∈ Zp}) is a strongly universal (p, p)-hash family.

Proof-

Suppose x, x’, y, y’∈ Zp, where x ≠x’. We will proof that there is a unique key (a, b) ∈ Zp × Zp such that ax + b ≡ y (mod p) and ax’ + b ≡ y’ (mod p).

This is easy, as (a, b) is the solution of a system of two linear equations in two unknowns over Zp.

Specifically,

a = (y’− y)(x’− x)⁻¹ mod p, and

b = y − x(y’− y)(x’− x)⁻¹ mod p

Applications

The three prominent applications of Strongly Universal Hash Families are given below.

Quasirandom Number Generation

It is like any other random number generation process but with a complex algorithm. It uses theorems and functions of strongly universal hash families for random number generation.

Derandomization

As we already know that you can use functions and theorems of strongly universal hash families for random number generation, you can also them to derandomize the equations in hand.

Privacy Amplification

The theorems and functions used in randomization and derandomization also help increase the privacy of the applications.