Foundations of Cryptography Prof. Dr. Ashish Choudhury (Former) Infosys Foundation Career Development Chair Professor International Institute of Information Technology – Bangalore Lecture – 25 Information – Theoretic MACs Hello everyone, welcome to lecture 23. Namely messag What we are going to do is now we will see a candidate construction based on group theory and finite field arithmetic. So let us see the definition of abelian group first. So what exactly is an abelian group? So a group basically consists of a set which could be either finite or infinite, it has certain number of elements and along with that set you have an operation o and we say that the set along with the operation o constitutes a group if the following properties are satisfied. The first property is the closure property which states that if you take any two elements from the group, say a and b and perform the group operation o those two elements, then the result should again be a member of the group and that is why the name closure property. That means by performing the operation little o on any two group elements, you would not go outside or you would not get an element which is outside the group. You will still get an element which belongs to the group. So that is why the name closure property. The second property that we require from the set and operation o is as follows. It is called associativity property and which basically demands that if you take any 3 elements a, b, c from the group right, then it does not matter whether you perform the group operation on a and b and then following by performing the group operation on c. You will get the same answer if you first perform the group operation on b and c and then you perform the group operation on the result on the element a. That means the operation o satisfies the associativity property. The third property that we require is the existence of identity element, namely there should exist a unique element which we denote as say e belonging to the set which satisfy a magical property. Namely it should satisfy the condition that if you take any element a from the group and if you perform the group operation or the operation o on the element a and on the element e, then you should get back the element a and that is why we call that special element e as the identity element. That means you perform that operation o with e and any element a from the group, you will end up getting back the element a. The next property that we require from the set and operation o is as follows. We require that there should exist for every element a from the set , there should exist a special element which we denote as a inverse or a raise to power -1 such that if you perform the operation o on the element a and this element a-1, you should get back the identity element. So I stress that even though we are using the notation a raise to power minus -1, numerically it is not equal to 1/a because we are constructing where we are actually treating the set in abstract terms. That means your set could consist of any type of element, it need not be numbers or integers or so on, it could be consisting of say vectors, matrices and so on. So do not get confused that a to the power -1 stands for the numeric 1/ a, it is just a notation. What we are basically demanding here is that if you take any candidate element a from the set G, then corresponding to that you should also have a candidate element from the set G itself which I am denoting by this notation a-1 such that if you perform the operation o on the element a and on this special element a -1 , you should get back the identity element, right. So if my set G along with operation o satisfies these 4 properties, then I say that G, o is a group and on top of these 4 properties if my set G along with the operation o satisfies an additional condition namely that of commutativity property which requires that for any pair of elements a, b from the set G, it does not matter whether you perform the operation on a and b or on b and a, you get back the same answer, then that special group is called as an abelian group. So in the absence of commutative property, what we obtain is a group, but on top of that if the group also satisfies the commutativity property, then the group is called as an abelian group, right. So that is the definition of an abstract abelian group. Now let us see some candidate examples for an abelian group. So if you consider a set of integers which I denote by ℤ which is an infinite set and if I take the operation plus namely the integer addition. So my operation o in this case is plus and my set is nothing but ℤ, then the set of integers along with the integer addition satisfies the closure property, associativity property, existence of identity, existence of inverse and commutative property. You can verify that, right. So let us verify the closure property. If you take any two integers and add them numerically, you will again obtain an integer, so closure is satisfied. It is easy to verify that the operation integer addition satisfies the associativity property Because it does not matter that whether you add a and b first and followed by adding c, you get the same answer which you have by performing the addition of b and c first and then adding the answer to a, so the associativity property is satisfied. The element 0 belonging to the set of integers constitutes your identity element because a+0 for every integer a is going to give you back the element a and for every element a or for every integer a, you have the corresponding integer -a also belonging to the set of integers such that a + -a is going to give you the identity element namely 0. And it is easy to verify that for any two integers a and b, a+b is same as b+a, so the commutativity property is also satisfied. That means the set of integers ℤ along with the operation plus satisfies all the 5 axioms that I require from an abelian group and that is why the set of integers along with the integer addition operation constitutes a candidate abelian group okay right. So we have seen an example of abelian group. Now let us see whether the set of natural numbers which I denote by ℕ along with the operation plus constitutes a group or not. So it satisfies the closure property, if you take any two natural numbers and add it, you will get a natural number, the addition operation satisfies the associativity property over the set of natural numbers. The problem here is that you do not have the identity element right because you do not have the element 0 present in the set ℕ, so this axiom is not satisfied and it turns out that every natural number does not have an inverse in the set of natural numbers. So if you take for instance the element 2, its inverse should be ideally -2. S