Enhancing Security in Online Voting Systems: A Cryptographic Approach Utilizing Galois Fields

Cryptology is the study of developing cryptosystems and methods to crack the designed cryptosystems. Algorithms are designed to encrypt and decrypt information, exchange keys used for encryption and decryption, generate keys and hack the cryptosystem designed [1]. These algorithms are developed from the concepts of mathematical sciences such as finite fields, modular arithmetic, matrices etc. and are implemented using the programming languages [2]. The security, time and space complexity of the developed algorithm is of main concern in applying it in real time. The security of a cryptosystem is mainly constituted in the cryptographic key used to encode data and retrieve it. To safeguard the cryptographic key accountable for the security, several key exchange protocols are developed depending upon the number of communicating parties. These protocols ensure the safe key transfer over communication channels. But most of the key exchange protocols are prone to the Man-In-The-Middle attack which can be eradicated by providing user authentication.

One of the practical scenarios where user authorization and authentication are necessary is Election. Election is a fair process of electing a candidate based on the number of votes casted in favour. This process was manually conducted in ancient times. Electronic Voting Machines are invaded over time to facilitate elections by conducting them in short duration achieving total secrecy. With further onset of technology concerning human comfort, online voting systems are designed which overcome congestion at polling booths and support remote voting. Internet voting is implemented for small scale elections [3] but the need for an efficient protocol which could be practically implemented for large-scale elections is prevalent.

A Voting System includes three major steps: Registration of voters, Vote Casting and Counting. The initial step of a voting system assures that no unauthorized voter casts the vote. Subsequently, votes are casted by the authorized voters at the polling booth which are stored in secret ballots. Finally, the encrypted votes are transferred to the counting officer over a secure channel for results. The entire framework of a secure Voting system is designed to achieve total secrecy and individual, eligible and universal verifiability [4, 5]. Internet Voting apply mathematical algorithms in software to establish the framework of a voting system [4, 6].

Porkodi and Sangavai [7] studied secure e-voting scheme over Circulant matrices is developed assuming the authenticity of the votes casted by the authorized voters. Falkner [8] et al. studied the initialization phase of registration operates a Pseudo Random Key Stream Generator (PRKG) to generate passwords for designing individual secret QR codes for voters. These QR Codes are employed by the voters to participate in the elections.

A Pseudo Random Key Stream (PRKS) is a sequence of numbers produced by a mathematical algorithm with an input seed value. A PRKS is periodic after certain time and an adversary could guess the key stream with the knowledge of the input seed value. Our aim of this paper is to develop an authentication scheme which provides two-factor authentication and overcome the threat of a PRKG. The scheme applies an efficient cryptographic technique inspired from Amiruddin et al. [9] and Verma and Jain [10] to generate multiple keys for voters which authorize them to vote and retain the authenticity of the voter. The authentication scheme supports the registration phase of an online voting system which supports medium to large scale elections.

Amiruddin et al. [9] found that key generation techniques are proposed whose performance is measured by testing the algorithm for its key generation speed, key randomness, periodicity and complexity of the algorithm. Verma and Jain [10] studied Reed Solomon codes and parity check matrices are used in correcting passwords that are entered incorrect by the user with minute error. The designed method prompts the user with the correct password characters by retaining the security. In Cody Planteen [11], a method is proposed to develop a cryptographic key using the biometric fingerprints of a user.

The proposed authentication scheme in this paper is procured through the following mathematical and cryptographic concepts:

1.1 Galois field GF(2^m)

A Galois field is a field which has finite number of elements whose order is either a prime or a prime power. The elements of a Galois field GF(2^m) can be identified as polynomials of a maximum degree of (m-1) or group of m bits which comprises of either 0s or 1s. When the elements are in the form of polynomials in GF(2^m) over a chosen irreducible polynomial of degree m, the field operations are addition modulo 2 and multiplication modulo 2. Due to the modulo 2 operations performed, the polynomials can be mapped to the group of binary bits. In Galois field GF(2^m), the chosen irreducible polynomial of degree m plays an important role in identifying the elements of the field. With the change in the chosen irreducible polynomial, the mapping of polynomials with their equivalent group of m bits consisting of 0s and 1s differ [12, 13].

1.2 Subfields of GF(2^m)

A subset of Galois field GF(2^m) is its subfield if it is a field with respect to the same operations. The order of a subfield of GF(2^m), is necessarily a power (n) of 2 where n divides m. Thus, the total number of subfields of a field of order 2^m is equal to the number of positive divisors of m. The subfield of GF(2^m) can be constructed by means of a primitive element of GF(2^m). In the section 3 of this paper, the subfields of a Galois field GF(2⁸) are constructed [12, 13].

1.3 Group codes

A group code B^a is a collection of block codes which forms a subgroup of an abelian group B^b where a<b and order of B^a=2^a. An encoding function is a mapping from B^m to Bⁿ  where m<n. The set comprising of all the elements of B^m which are mapped to the elements of Bⁿ forms a group with respect to XOR operation if the last (n-m)x(n-m) sub matrix of the parity check matrix of order mx(n-m) chosen is an identity matrix [13].

The rest of the paper is organized as follows: Section 2 presents the methodological approach of the proposed authentication scheme for OVS. Section 3 illustrates the proposed scheme through an example and describes its application in OVM. Section 4 covers the detailed analysis of the proposed scheme by describing its security aspects and implementation in medium scale elections. Section 5 concludes the presented work by highlighting its uniqueness, merits and applications.

The proposed method is implemented through the example below:

Step 1:

Consider a Galois Field GF(2⁸) with an irreducible polynomial $x^8+x^4+x^3+x^2+1$. The total number of elements in GF(2⁸) is 256. Let $\alpha$ be the root of the polynomial $x^8+x^4+x^3+x^2+1$. Since the powers of $\alpha$ generate all the elements of GF(2⁸) and its order is 255 therefore $\alpha$ is the primitive element of GF(2⁸).

The example of identifying an element $\alpha^9$ of the Galois field GF(2⁸) with an irreducible polynomial $x^8+x^4+x^3+x^2+1$:

$\begin{aligned} & \alpha^9=\alpha \cdot \alpha^8  =\alpha \cdot\left(\alpha^4+\alpha^3+\alpha^2+1\right)  =\left(\alpha^5+\alpha^4+\alpha^3+\alpha\right)\end{aligned}$

The vector associated with the polynomial $\alpha^5+\alpha^4+\alpha^3+\alpha$ is calculated as:

$\alpha^7$	$\alpha^6$	$\alpha^5$	$\alpha^4$	$\alpha^3$	$\alpha^2$	$\alpha^1$	$\alpha^0$
0	0	1	1	1	0	1	0

The elements of GF(2⁸) and the vector associated to each element of the field is tabulated in the Table 1.

Step 2:

The number of proper subfields of GF(2⁸) are: $q=($ Number of positive divisors of 8$)-1=3$, which are $\mathrm{F}_2, \mathrm{~F}_{2^2}$ and $\mathrm{F}_{2^4}$.

Here, $o\left(F_2\right)=2, o\left(F_{2^2}\right)=4$ and $o\left(F_{2^4}\right)=16$.

Let us consider one of the primitive elements of GF(2⁸), $\alpha$ for tracing the elements of the subfields $\mathrm{F}_2, \mathrm{~F}_{2^2}$ and $\mathrm{F}_{2^4}$.

$F_2=\{0\} \cup<\alpha^{\frac{255}{1}}>=\{0,1\}=\{00000000,00000001\}$

$\begin{aligned} & F_{2^2}=\{0\} \cup<\alpha^{\frac{255}{3}}> \\ & =\left\{0,1, \alpha^{85}, \alpha^{170}\right\} \\ & =\left\{0,1, \alpha^7+\alpha^6+\alpha^4+\alpha^2+\alpha, \alpha^7+\alpha^6+\alpha^4+\alpha^2+\alpha+1\right\} \\ & =\{00000000,00000001,11010110,11010111\}\end{aligned}$

$\begin{aligned} & F_{2^4}=\{0\} \cup<\alpha^{\frac{255}{15}}> \\ & =\left\{\begin{array}{c}0,1, \alpha^{17}, \alpha^{34}, \alpha^{51}, \alpha^{68}, \alpha^{85}, \alpha^{102}, \alpha^{119}, \alpha^{136}, \\ \alpha^{153}, \alpha^{170}, \alpha^{187}, \alpha^{204}, \alpha^{221}, \alpha^{238}\end{array}\right\} \\ & =\left\{\begin{array}{c}0,1,\left(\alpha^7+\alpha^4+\alpha^3\right),\left(\alpha^6+\alpha^3+\alpha^2+\alpha\right),\left(\alpha^3+\alpha\right), \\ \left(\alpha^7+\alpha^4+\alpha^3+1\right),\left(\alpha^7+\alpha^6+\alpha^4+\alpha^2+\alpha\right), \\ \left(\alpha^6+\alpha^2\right),\left(\alpha^7+\alpha^4+\alpha+1\right), \\ \left(\alpha^6+\alpha^3+\alpha^2+\alpha+1\right),\left(\alpha^7+\alpha^4+\alpha\right), \\ \left(\alpha^7+\alpha^6+\alpha^4+\alpha^2+\alpha+1\right), \\ \left(\alpha^7+\alpha^6+\alpha^4+\alpha^3+\alpha^2\right), \\ \left(\alpha^7+\alpha^6+\alpha^4+\alpha^3+\alpha^2+1\right), \\ \left(\alpha^6+\alpha^2+1\right),\left(\alpha^3+\alpha+1\right)\end{array}\right\} \\ & =\left\{\begin{array}{c}00000000,00000001,10011000,01001110,00001010, \\ 10011001,11010110,01000100,10010011,01001111, \\ 10010010,11010111,11011100,11011101,01000101, \\ 00001011\end{array}\right\}\end{aligned}$

The distinct elements in all the proper subfields of the chosen Galois field could be identified only by the person who has the knowledge of the chosen Galois field which is private to the system. Thus, an adversary has no knowledge of the input values which ought to be the no. of 0s and 1s in the code words associated with the subfield elements.

Table 1. Elements of GF(2⁸)

Primitive Element ($\alpha$)  Power	Polynomial	Vector
$\alpha^{-inf}$	0	00000000
$\alpha^0$	1	00000001
$\alpha^1$	$\alpha$	00000010
$\alpha^2$	$\alpha^2$	00000100
$\alpha^3$	$\alpha^3$	00001000
$\alpha^4$	$\alpha^4$	00010000
$\alpha^5$	$\alpha^5$	00100000
$\alpha^6$	$\alpha^6$	01000000
$\alpha^7$	$\alpha^7$	10000000
$\alpha^8$	$\alpha^4+\alpha^3+\alpha^2+1$	00011101
$\alpha^9$	$\alpha^5+\alpha^4+\alpha^3+\alpha$	00111010
$\alpha^{10}$	$\alpha^6+\alpha^5+\alpha^4+\alpha^2$	01110100
$\alpha^{11}$	$\alpha^7+\alpha^6+\alpha^5+\alpha^3$	11101000
$\alpha^{12}$	$\alpha^7+\alpha^6+\alpha^3+\alpha^2+1$	11001101
$\alpha^{13}$	$\alpha^7+\alpha^2+\alpha+1$	10000111
$\alpha^{14}$	$\alpha^4+\alpha+1$	00010011
$\alpha^{15}$	$\alpha^5+\alpha^2+\alpha$	00100110
$\alpha^{16}$	$\alpha^6+\alpha^3+\alpha^2$	01001100
$\alpha^{17}$	$\alpha^7+\alpha^4+\alpha^3$	10011000
$\alpha^{18}$	$\alpha^5+\alpha^3+\alpha^2+1$	00101101
$\alpha^{19}$	$\alpha^6+\alpha^4+\alpha^3+\alpha$	01011010
$\alpha^{20}$	$\alpha^7+\alpha^5+\alpha^4+\alpha^2$	10110100
$\alpha^{21}$	$\alpha^6+\alpha^5+\alpha^4+\alpha^2+1$	01110101
$\alpha^{22}$	$\alpha^7+\alpha^6+\alpha^5+\alpha^3+\alpha$	11101010
$\alpha^{23}$	$\alpha^7+\alpha^6+\alpha^3+1$	11001001
$\vdots$	$\vdots$	$\vdots$
$\alpha^{254}$	$\alpha^7+\alpha^3+\alpha^2+\alpha$	10001110

Step 3:

Let us define an encoding function $e: B^8 \rightarrow B^{10}$ by $e\left(x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8\right)=\left(x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8 x_9 x_{10}\right)$ where $x_9=x_1 \oplus x_2 \oplus x_4 \oplus x_6 \oplus x_7$ and $x_{10}=x_1 \oplus x_3 \oplus x_4 \oplus x_8$. The parity check matrix is $P=\left[\begin{array}{llllllll}1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1\end{array}\right]$.

Different parity matrices in an encoding function yield different functional values for the same code word, thereby responsible to generate different pass codes.

Step 4:

The elements of the subfields $\mathrm{F}_2, \mathrm{~F}_{2^2}$ and $\mathrm{F}_{2^4}$ are mapped with the code words of B⁸↔B¹⁰ corresponding to the defined encoding function in the step 3 which is depicted in the Table 2.

Table 2. Mapping of B⁸↔B¹⁰

Subfield	B8	B10
$\mathrm{F}_2$	00000000 00000001	0000000000 0000000101
$\mathrm{~F}_{2^2}$	00000000 00000001 11010110 11010111	0000000000 0000000101 1101011010 1101011111
$\mathrm{F}_{2^4}$	00000000 00000001 10011000 01001110 00001010 10011001 11010110 01000100 10010011 01001111 10010010 11010111 11011100 11011101 01000101 00001011	0000000000 0000000101 1001100000 0100111010 0000101010 1001100101 1101011010 0100010000 1001001111 0100111111 1001001010 1101011111 1101110000 1101110101 0100010101 0000101111

Excluding the repeated elements in the subfields, a total of 16 booths are possible in the example whose private keys are listed in the Table 3. Therefore, l=16.

Table 3. Private key of each booth

Booth	B8	B10
1	00000000	0000000000
2	00000001	0000000101
3	11010110	1101011010
4	11010111	1101011111
5	10011000	1001100000
6	01001110	0100111010
7	00001010	0000101010
8	10011001	1001100101
9	01000100	0100010000
10	10010011	1001001111
11	01001111	0100111111
12	10010010	1001001010
13	11011100	1101110000
14	11011101	11011110101
15	01000101	0100010101
16	00001011	0000101111

Step 5:

The voter inputs the voter ID which is sent as an input to the pass code framer. Sequentially, the voter is mapped with one of the booths which are uniquely identified through the mapped code words. The number of voters that could be assigned to a single booth is equal to the number of parity check matrices possible through the proposed encoding function. The input by the voter, the codeword in B⁸ which is assigned to the specified booth and its corresponding code word in B¹⁰ are fed as an input to the PRKG to compute the required pass code. The Voter ID and the pass code combination are noted by the voter which is used to authenticate the voter to cast vote. The voters who have generated their pass codes are registered in the respective booths and are considered to be authorized. The process is depicted through the Figure 1. Before voting the voters are verified at their assigned booths to validate their votes. This is performed by capturing their ID and pass code combination verified as illustrated in the Figure 2.

1.png

Figure 1. Authorization

2.png

Figure 2. Authentication

The pass code framer generates ID and pass code combination in three segments where the first segment is the ID which determines the assigned booth, the second segment is a decimal equivalent to the code word assigned to the respective booth which determines the correctness of the booth and the third segment is the pass code generated through the PRKG which is verified against the stored ID-pass code combination. When all the three segments are not a mismatch, the voter is considered to be authenticated and allowed to cast vote.

An efficient and secure pass code generation technique is proposed applying mathematical and cryptographic tools whose application in an OVS is witnessed. PRKG are periodic over a certain instant of time and rely on a predictable input seed value. The developed authentication scheme is advantageous over the systems which apply only Pseudo random numbers generators to authenticate the user. Our method ensures a two-factor authentication by generating the pass code in two segments. The first segment of the pass code is reliable and retains security as long as the encoding function, Galois field and the irreducible polynomial utilized in the method are private to the system. The developed method facilitates authorization and authentication in medium scale elections with a suitable choice of the chosen Galois field GF(2^a) and the domain B^a and co-domain B^b, b>a of the encoding function e and hence satisfies the important criteria of eligibility in an e-Voting scheme. The proposed model is also helpful in telemedicine to provide authorization and authentication to the legitimate parties involved in an e-HCS platform.