Do you think IIT Guwahati certified course can help you in your career?
Introduction
In this article, we will try to understand the Blom Scheme in cryptography. Blom’s scheme is an algorithm which is used in cryptography to enhance security. It is a key management scheme. We will also try to understand why we use it and also try to understand the benefits of using it.
Bloom Filters
Suppose we want to create an account on any website where the username of all the users on the platform is unique. The username which we want to use is first checked with all the usernames which have been taken. But how is it done?
The first thing which comes to our mind is searching. There are several search methods. For example
Linear Search It is one of the easiest search methods. But it has a time complexity of O(n), which makes it unfit for this task.
Binary Search We have to store all the usernames in sorted order. The entered username is matched with the middle element. If it does not match, then it seeks for that half of the usernames where the possibility of the name being present is. This process is continued until we get the halves empty, i.e. no element is present in the two halves. This search method is better as compared to the previous one as we have a time complexity of O(log n).
Though we have the binary search for searching the names, it is not a very fast method. We can use Bloom Filter.
Bloom Filter is a data structure which can be used to inspect whether an element is present in an array or not. It can represent a set of any number, which a hash table can’t. Inserting an element is always successful. Deleting an element from the filter is impossible. And doing so may cause deletions of other elements also.
If the purpose is to store a large number of identities, then we can use a hashmap, array, or linked list. In terms of memory, they are not very efficient. The data item is not stored in Bloom Filters. The hash function used must be fast. The main difficulty in Bloom Filters is generating the hash function.
Cryptography has gained a lot of attention in recent decades. Most people are aware of the term cryptography and have made it an important part of their lives. It generally works online. We know that cryptography has various security challenges, and it surely works very well to safeguard or protect the user’s details and does not give us any chance to complain about this issue. But have you ever thought about how things work internally? Today, we will look at a fundamental concept of cryptography, the Blom scheme. So, let’s dive deep into the concept of the Blom scheme.
Before knowing about the Blom scheme, we must understand why it came into the scenario. We have a problem known as the n2 problem. We need to transmit the nC2 keys securely. This requires a large amount of memory. We get the solution to this problem by Blom scheme.
In the Blom scheme, we provide each participant with a public identifier and a secret key from any trusted party. This system enables any two participants to communicate with each other via a shared key. This approach becomes quite expensive, even for small networks. Therefore, it can’t be considered a practical solution. Thus, our main concern is reducing the information stored and transmitted.
The key distribution method allows any two nodes to find a secret key pairwise in the network. Let a network consist of N nodes, which are given a term as N users. The interest of λ number of users or lesser cannot reveal the keys that the other network members are holding. λ is the threshold and is a parameter for the security of the network.
Mathematically: λ ∝ security of the network
This property is a crucial and necessary parameter because someone trying to gain access to the network will have to attack a more extensive section of the network to have control over the network. Apart from this, we use λ to determine the memory needed to store the information of the key. λ is directly proportional to memory usage. We can consider the network secure until λ number of nodes is compromised (gained access). This property is known as the λ-secure property.
Note- Blom’s scheme was not originally made for wireless sensor networks. But, certain modifications were made to make it optimal for wireless sensor networks.
The base station constructs a matrix M of size (λ +1) x P over a finite field F(q), where P is the number of nodes, and λ is the secure parameter. P is called the public matrix, i.e., all the information of P is public information, which means every sensor node in the network can access the information of P, and the same goes with the advisories. Next, the base station, over a finite field F(q), creates a symmetric matrix called M of the size (λ + 1) x (λ + 1). The base station computes (M.P)T resulting in a matrix A of size P x (λ + 1) where (M.P)T is the transpose matrix of (M.P). Matrix M is to be kept secret. As M is symmetric, it can be seen that:
A.P = (M.P)T.P = PT.DT.P = PT..D.P = (A.P)T
This implies that A.P is a symmetric matrix. We are storing the result of A.P in another matrix and naming it K. As K is symmetric, Kij = Kji.
When nodes i and j require the pairwise key, they first exchange their columns of P and then compute Kij and Kji, respectively. The λ secure property ensures that no nodes other than i and j can compute Kij or Kji, provided no more than λ nodes are compromised.
Vandermonde matrix contains the terms of a geometric progression in every row. Any (λ + 1) columns of P must be linearly independent to achieve λ-secure property. Since every element in the field F(q) represents a pairwise key, let the length of pairwise be l, and then q should be chosen so that it is the smallest prime number greater than 2l.
We know that si ≠ sj, if i is not equal to j. λ + 1 columns of G are linearly independent when s, s2, s3, . . , sN are all distinct. We can generate the whole column provided we are given a node.
Modified Blom’s Scheme
Blom scheme also has a problem. Blom scheme uses the Vandermonde matrix, which is a public matrix and generates all keys. All the elements of the matrix are chosen distinctively so that λ +1 columns are linearly independent. The problem arises when the value of λ increases. The number of rows in the public matrix increases, and this results in greater values as they are in geometric series.
To reduce the computation and memory overhead, instead of using the Vandermonde matrix, we can use an Adjacency matrix. As it is a square matrix with 0s and 1s, it helps to reduce the complexity of calculating values for all the elements. Another advantage of using the Adjacency matrix is it reduces the memory of sensors to save the columns. One change is done to the Adjacency matrix in that all the zeroes are replaced with q-1, where q is a prime number.
The steps for calculating the key are as follows:
Generating a G matrix Let’s consider a finite field, F(q), and select a primitive element. Let's construct the adjacency matrix G of the size N x N. Depending on the value of λ, the first λ rows, along with N columns, are selected as the public matrix.
Generating key spaces The Central Authority generates ⍵, symmetric matrices D1, D2, . . . , D⍵ of size (λ+1)x(λ+1).
Computing the Secret Key The Central Authority saves each row in the node memory with the corresponding index. If node i want to communicate with node j then node i multiplies the row Ai with column Gj, and the final result will be stored in the secret key.
Blom’s scheme is a key exchange protocol used in cryptography. The issue with Blom’s scheme is the complexity of computation as well as memory usage. This modification in Blom’s scheme using the Adjacency matrix helps to reduce the computation along with the memory usage.
Frequently Asked Questions
What is cryptography?
Cryptography is a secure technique in which the sender and receiver are allowed to see the contents of the message. The term crypto is derived from the Greek word kryptos, which means hidden.
Where is cryptography used?
We generally use cryptography in computer passwords, e-commerce transactions, banking transactions, etc.
What are the advantages of using cryptography?
Users’ data is protected against unauthorised access. Information is kept secure using cryptographic techniques. Data integrity is ensured.
What is the distribution of keys?
Key distribution is the transfer of keys, as well as of the keying materials. The key distribution must be done secretly to ensure data security.
Why is the distribution of keys important?
The main difficulty is distributing the keys to the entities that require them instead of any other entity. The best method for distributing the key is cryptography.
Conclusion
In this article, we discussed its not bloom but Blom scheme in cryptography. We hope this blog on its not bloom but Blom scheme in cryptography was helpful. You can also refer to other similar articles.
24+ registered 
