CNS - 37 - Group Theory
Lecture Info
Date:
Lecturer: Giuseppe Bianchi
Slides: (42-groups.pdf)
Introduction: In this lecture we briefly review some basic result from group theory that will help us understand how to actually implement verifiable secret sharing techniques.
1 What is a Group?
A group is the simplest possible structure studied by group theory, and it is defined as a couple \((G, \circ)\), where \(G\) is a set of elements and \(\circ\) is an operation that satisfies the following properties:
Closure property: For any \(g_1, g_2 \in G\), the result of combining these two elements is also a member of the group. That is,
\[g_x = g_1 \circ g_2\]
Identity: There is a group member \(I \in G\) such that for any \(g\)
\[g \circ I = I \circ g = g\]
Inverse: For any \(g\), there is a \(g^{-1}\) such that
\[g \circ g^{-1} = I\]
Associativity: For any \(g_1, g_2, g_3\) we have that
\[(g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3)\]
If the operation is also commutative, meaning that
\[g_1 \circ g_2 = g_2 \circ g_1\]
then the group is callled an Abelian group.
2 The \(\mathbb{Z}_p^*\) group
With the symbol \(\mathbb{Z}_p^*\) we denote a very important group in group theory, which is also known as the multiplicative group modulo p, where \(p\) is a prime number. This group is defined as follows:
The set is the set of \(p-1\) elements \(\{1, 2, \ldots, p-1\}\).
The operation is multiplication modulo \(p\).
Notice that this set of numbers with the multiplication modulo \(p\) operation is a group, because all the properties we have previously mentioned are valid for this particular structure. In particular when we work mod \(N\) a value \(x\) has an inverse if and only if \(\text{gcd}(x, N) = 1\), which means that when \(N\) is a prime number than all the elements of the set have an inverse, and thus we have a group structure.
2.1 Example \(\mathbb{Z}_{11}^*\)
The elements of the group \(\mathbb{Z}_{11}^*\) are
\[\mathbb{Z}_{11}^* = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\]
The inverses for each element instead are displayed below
\[\begin{split} 1 &\to 1 \\ 2 &\to 6 \,\,\,\,,\,\,\,\, 6 \to 2 \\ 3 &\to 4 \,\,\,\,,\,\,\,\, 4 \to 3 \\ 5 &\to 9 \,\,\,\,,\,\,\,\, 9 \to 5 \\ 7 &\to 8 \,\,\,\,,\,\,\,\, 8 \to 7 \\ 10 &\to 10 \\ \end{split}\]
To compute such inverses the extended euclidean algorithm, already discussed in a previous lecture can be used.
3 Exponentiation
Notice that in groups we can talk about exponentiation, since exponentiation is the repetition of multiplication, which is the only operation we can apply to the group elements. That is, exponentiation is just a convenient to write iterated multiplications
\[x^k = \underbrace{x \circ x \circ \ldots \circ k}_{k \text{ times }}\]
3.1 Generator of a Group
A generator of a group of order \(m\) is an element \(g \in G\) of the group such that
\[g^0, \,\,\, g^1, \,\,\, \ldots, \,\,\, g^{m-1}\]
are all members of the group.
If \(m\) is prime, then any member except the identity is a generator.
3.2 Order of a Group
The order of a group is defined to be as the highest iteration after which you go back to the original element.
This means that, since \(\mathbb{Z}_p^*\) has \(p-1\) elements, the order of the group \(\mathbb{Z}_p^*\) is not a prime number, because if \(p\) is prime, then \(p-1\) is an even number.
3.2.1 Example \(\mathbb{Z}_{11}^*\)
Consider our previous group \(\mathbb{Z}_{11}^* = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\). Then we get that:
\(g = 2\) is a generator, since
\[\{2^1, 2^2, 2^3, \ldots, 2^{10}\} = \{2, 4, 8, 5, 10, 9, 7, 3, 6, 1\}\]
\(g = 3\) is not a generator, since
\[\{3^1, 3^3, 3^3, \ldots, 3^{10}\} = \{3, 9, 5, 4, 1, 3, 9, 5, 4, 1\}\]
\(g = 4\) is not a generator, since
\[\{4^1, 4^4, 4^4, \ldots, 4^{10}\} = \{4, 5, 9, 3, 1, 4, 5, 9, 3, 1\}\]
\(g = 5\) is not a generator, since
\[\{5^1, 5^5, 5^5, \ldots, 5^{10}\} = \{5, 3, 4, 9, 1, 5, 3, 4, 9, 1\}\]
\(g = 6\) is a generator, since
\[\{6^1, 6^6, 6^6, \ldots, 6^{10}\} = \{6, 3, 7, 9, 10, 5, 8, 4, 2, 1\}\]
\(g = 7\) is a generator, since
\[\{7^1, 7^7, 7^7, \ldots, 7^{10}\} = \{7, 5, 2, 3, 10, 4, 6, 9, 8, 1\}\]
\(g = 8\) is a generator, since
\[\{8^1, 8^8, 8^8, \ldots, 8^{10}\} = \{8, 9, 6, 4, 10, 3, 2, 5, 7, 1\}\]
\(g = 9\) is a generator, since
\[\{9^1, 9^9, 9^9, \ldots, 9^{10}\} = \{9, 4, 3, 5, 1, 9, 4, 3, 5, 1\}\]
\(g = 10\) is a generator, since
\[\{10^1, 10^10, 10^10, \ldots, 10^{10}\} = \{10, 1, 10, 1, 10, 1, 10, 1, 10, 1\}\]
The take home message is that if you take an element \(g\) and you start computing \(g^1, g^2, \ldots\) you either generate all elements of the group or you generate a subgroup whose order is a factor of the size of the original group.
4 Strong Primes
Consider a prime \(p\). We know that the order of the group \(\mathbb{Z}_p^*\) is \(p-1\), and therefore such number is even and not prime. We can however ask the following question: can we find a \(q\) prime such that
\[p-1 = 2 \cdot q\]
If we can find a prime number \(p\) such that \((p-1)/2\) is also prime, then we have some interesting properties. These numbers do exist and they are called strong primes. A prime \(p\) is said to be a strong prime if there exists another prime \(q\) such that
\[p = 2q + 1\]
An example of a strong prime is \(p = 83\), since \(p-1 = 82 = 2 \cdot 41\), where \(q = 41\).
Notice that if we have a strong prime \(p\), then when we pick an element \(g \in \mathbb{Z}_p^*\) such that \(g \neq 1, -1\), and we start generating elements \(g^0, g^1, \ldots\) then either two things can happen:
The element \(g\) generates the entire group.
The element \(g\) generates a subgroup of prime order \(q\).
If \(p\) is a very large and strong prime number, then in the worst case we will end up in a subgroup of prime order \(q\), which is still very large. This is much stronger than simply using a large prime \(p\), because if we only required the prime to be "large", then potentially \(p-1\) can have many small factors.
5 Quadratic Residue Subgroup
An element \(x \in \mathbb{Z}_p^*\) is a quadratic residue if it admits square root in \(\mathbb{Z}_p^*\), i.e. if there exists an \(a\) such that
\[a^2 \mod p = x\]
There is a very easy criterion that can be used to check if an element \(x \in \mathbb{Z}_p^*\) is a quadratic residue or not. Notice that \(x^{(p-1)/2}\) can be either \(1\) or \(-1\). The important result, thanks to Legendre, is that if \(x^{(p-1)/2} = 1\) then we are in a subgroup, and if it isn't we are not in a subgroup.
For example the quadratic residues in \(\mathbb{Z}_p^*\) are the following
\[\text{QR}_{11} = \{1, 3, 4, 5, 9\}\]
6 The Problem with Feldman
Notice that the Feldman scheme we introduced in the last lecture has a problem in the computation of the verifier: the polynomial computed in the exponetial, that is
\[\begin{split} & \;\;\; c_0 \cdot c_1^{x_i} \cdot c_2^{x_i^2} \cdot c_3^{x_i^3} \cdot \ldots \cdot c_{t-1}^{x_i^{t-1}} = \\ &= (g^s) \cdot (g^{a_1})^{x_i} \cdot (g^{a_2})^{x_i^2} \cdot (g^{a_3})^{x_i^3} \cdot \ldots \cdot (g^{a_{t-1}})^{x_i^{t-1}} = \\ &= g^{s + a_1x_i + a_2x_i^2 + a_3x_i^3 + \ldots + a_{t-1}x_i^{t-1}} = \\ &= g^{p(x_i)} \\ \end{split}\]
is computed working in modulus \(\phi(p) = p-1\), which is non-prime and therefore not secure. The idea is then to have \(g\) be a generator of a subgroup, and to select \(p\) as a big strong prime, so that the order of the subgroup generated by \(g\) is also a big prime. This can be done by taking \(g\) to be the square of any other element different from \(1\) and \(-1\) in \mathbb{Z}_p^*$.
6.1 Fixing it
To fix the scheme simply choose a large and strong prime number \(p\) such that \(p-1 = 2 \cdot q\), and do the normal shamir scheme working with \(\mod q\), while the commitments are generated \(\mod p\).
With this approach the arithmetic that we do when checking the validity of each share is done modulus \(q\), which is alright since for the polynomial generation we have used modulus \(q\).