Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
What is Universal Hashing?
2.
Strongly Universal Hash Families in Cryptography
2.1.
Intuitive Proof:
2.2.
Mathematical Proof:
2.3.
Theorems
2.4.
Applications
3.
Frequently Asked Questions
3.1.
Define Confidentiality.
3.2.
Why do we use Cipher?
3.3.
What is RSA?
3.4.
Mention the principles of Cryptography.
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Strongly Universal Hash Families in Cryptography

Author Rupal Saluja
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

notion of cryptography

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 : hK(x) = y, hK(x’) = y’}| = |K|/M2

Intuitive Proof:

Suppose we fix x and x’ and x’ ≠  x. There are M2 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 Pd0 and Pd1 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:

Mathematical Proof

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 Pd0 = Pd1 = 1/M.

We know that,

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

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

Proof-

First Theorem

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)−1 mod p, and

b = y − x(y’− y)(x’− x)−1 mod p

Applications

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

notion of applications

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Define Confidentiality.

Confidentiality is the term used to describe the level of secrecy of data. If the data is highly-confidential, only the sender and receiver can access the message exchanged between them.

Why do we use Cipher?

Cipher is an algorithm used to transform plain text into cipher text by two methods- Substitution and Transposition.

What is RSA?

RSA is a public key algorithm used to manage keys for digital signatures. It calculates a modulus that is used as a key with recipient’s public key. 

Mention the principles of Cryptography.

The four principles of Cryptography include Data Confidentiality, Data Integrity, Authentication, and Non-repudiation.

Conclusion

Overall, we understood various theorems of one of the foundational concepts of Unconditionally Secure MACs- Strongly Universal Hash Families in Cryptography. We also learned in brief about Universal Hashing.

We hope the above discussion helped you understand the concepts of Strongly Universal Hash Families in Cryptography and can be used for future reference whenever needed. To learn more about Cryptography, you can refer to blogs on Security in CryptographySigning and Encrypting in CryptographyAuthenticated Encryption in CryptographyCBC MAC in Cryptography, and Message Authentication Codes in Cryptography.

Visit our website to read more such blogs. Make sure you enroll in our courses, take mock tests, solve problems, and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help fellow ninjas grow.

Happy Coding!

Previous article
Optimality of Deception Probabilities in Cryptography
Next article
Introduction to Public Key Cryptography
Live masterclass