Cyclotomic matrix of order 8.
Confidentiality and Integrity are two paramount objectives in the evaluation of information and communication technology. In this chapter, we propose an arithmetic approach for designing asymmetric key cryptography. Our method is based on the formulation of cyclotomic matrices correspond to a diophantine system. The strategy uses in cyclotomic matrices to design a one-way function. The result of a one-way function that is efficient to compute, however, is hard to process its inverse except if privileged information about the hidden entry is known. Also, we demonstrate that encryption and decryption can be efficiently performed with the asymptotic complexity of Oe2.373. Finally, we study the computational complexity of the cryptosystem.
- finite fields
- discrete logarithm problem
- cyclotomic numbers
- cyclotomic matrix
- public key
- secret key
Apart from a rich history of Message encryption, the cryptosystem became more popular in the twentieth century upon the evolution of information technology. Until the last part of the 1970s, all cryptographic message was sent by the symmetric key. This implies somebody who has sufficient data to encode messages likewise has enough data to decode messages. Consequently, the clients of the framework must have to impart the secret key furtively. As a result of an issue stealthily key sharing, Diffie and Hellman  developed a totally new sort of cryptosystem called public key cryptosystem.
In a Public key cryptosystem, both parties (in a two-party system) have a pair of public enciphering and secret deciphering keys [2, 3]. Any party can send encrypted messages to an assigned party using a public enciphering key. However, only the assigned party can decrypt the message utilizing their corresponding secret deciphering key . After that various public key cryptosystems were introduced based on tricky mathematical problems. Among these, RSA is the longest reasonable use of cryptography. Since its design, in spite of all effort, it has not been broken yet. The security of the RSA is acknowledged to be established on the issue of the factorization of an enormous composite number. Be that as it may, there are some practical issues in RSA execution. The fundamental issue is the key arrangement time that is absurdly long for computationally restricted processors used in certain applications. Another issue is the size of the key. It was demonstrated that the time required to factor an n-bit integer by
Discrete logarithm problem (DLP) is a mathematical problem that occurs in many settings and it is hard to compute exponent in a known multiplicative group . Diffie-Hellman , ElGamal , Digital Signature Algorithm , Elliptic curve cryptosystems [11, 12] are the schemes evolved under the Discrete logarithm algorithm. The security of Diffie-Hellman relied upon the complexity of solving the discrete logarithm problem. However, the scheme has some disadvantages. It has not been demonstrated that breaking the Diffie-Hellman key exchange has relied upon DLP and also the scheme is vulnerable to a man-in-the-middle attack. For the security aspect, cryptosystem  was proposed, to introduce a digital signature algorithm (DSA) that’s primarily based on Diffie-Hellman DLP and key distribution scheme. It was demonstrated that DSA is around multiple times littler than the RSA signature and later DSA has been supplanted by the elliptic curves digital signature algorithm (ECDSA). Nonetheless, it has some practical implementation problems [13, 14, 15]. The length of the smallest signature is of 320 bits, which is still being too long for computationally restricted processors. Another issue emerged is as a correlation with RSA in a field with prime characteristics, which is forty times slower than RSA .
There are some other designs for public-key cryptosystems based on some extensive features of matrices. However, there were some practical implementation problems. Thus it had never achieved wide popularity in the cryptographic community. McElice  come up with a public key cryptosystem rooted on the Goppa codes Hamming metric. The scheme has the advantage that it has two to three orders of magnitude faster than RSA. Despite its advantage, it has some drawbacks. It was demonstrated that the length of the public key is bits and the data expansion is too large. Some other extensions of the scheme can also be found in [18, 19, 20]. Unfortunately, the scheme & its variants has been broken in [21, 22, 23]. Later, Gabidulin  come up with the rank metric & the Gabidulin codes over a finite field with elements, where i.e. , as an alternative for the Hamming metric. The efficiency of the scheme relied on same set of parameters and the complexity of the decoding algorithm for random codes in rank metric is tons higher than the Hamming metric [17, 25, 26, 27]. Numerous fruitful attacks were utilized on the structure of the public code [28, 29, 30]. To prevent these attacks, numerous alterations of the cryptosystems were made, consequently drastically increases the size of the key [31, 32, 33]. Lau and Tan  proposed new encryption with a public key matrix by considering the addition of a random distortion matrix over of full column rank . There are also many other design on matrices, which are not cited here, but none of them gain wide popularity in the cryptographic community due to lack of efficient implementation problems in one and another way.
Thinking about these inadequacies, it would be desirable to have a cryptosystem dependent on other than the presumptions as of now being used. Thus, we propose a cyclotomy asymmetric cryptosystem (CAC) based on strong assumptions of DLP that have to reduce the key size and faster the computational process.
1.1 Outline of our scheme
In this chapter, we consider two significant problems in the theory of cyclotomic numbers over . The first one deals with an efficient algorithm for fast computation of all the cyclotomic numbers of order , where is prime. The subsequent one deals with designing public key cryptosystem based on cyclotomic matrices of order . The strategy employs for designing public-key cryptosystem utilizing cyclotomic matrices of order , whose entries are cyclotomic numbers of order , be prime, where cyclotomic numbers are certain pairs of solutions of order over a finite field with elements.
In our approach, to designing cyclotomy asymmetric cryptosystem (CAC) based on trapdoor one-way function (OWF). The public key is obtained by choosing a non-trivial generator . The chosen value of the generator constructs a cyclotomic matrix of order . It is believed that cyclotomic matrices of order is always non-singular if the value of . Since there are efficient algorithms for the construction of cyclotomic matrices. Consequently, the key setup time in our proposed cryptosystem is much shorter than previously designed cryptosystems.
In the scheme, the secret key is given by choosing a different non-trivial generator, which is accomplished by discrete logarithm problem (DLP) over a finite field . A key-expansion algorithm is employed to expand the secret keys, which form a non-singular matrix of order . Here it is important to note that, if one can change the generators of , then entries of cyclotomic matrices get interchanged among themselves, however, the nature of the cyclotomic matrices remain as same. The decryption algorithm involves efficient algebraic operations of matrices. Hence the decryption in our proposed CAC is very efficient. In view of the perspective on the efficient encryption and decryption features, the polynomial time algorithm ensures that the proposed CAC makes it attractive in computationally restricted processors.
The chapter is organized as follows: Section 2 presents the definition and notations, including some well-known properties of cyclotomic numbers of order . Section 3 presents the construction of cyclotomic matrices of order . Section 4 contains encryption and decryption algorithms of CAC along with a numerical example. In addition, the computational complexity of the proposed CAC is discussed and in Section 5 presents the encryption & decryption can be efficiently perform with asymptotic complexity of . Finally, a brief conclusion is reflected in Section 6.
2. Cyclotomic numbers
Cyclotomic numbers are one of the most vital objects in Number Theory. These numbers had been substantially utilized in Cryptography, Coding Theory and other branches of Information Theory. Thus, calculation of cyclotomic numbers, so called to as cyclotomic number problems, of various orders is one of the primary problems in Number Theory. Complete answers for cyclotomic number problem for = , , , , , , , , , , , , , , , , with an odd prime had been investigated by many authors see ([35, 36, 37, 38, 39, 40] and the references there in). The section contains the generalized definition of cyclotomic numbers of order , useful notations followed by properties of cyclotomic numbers of order . These properties play a vital role in determining which cyclotomic numbers of order are sufficient for the determination of all cyclotomic numbers of order . The section also examines the cyclotomic matrices of order .
2.1 Definition and notations
Let be an integer, and an odd prime. One writes for some positive integer . Let be the finite field of elements and let be a generator of the cyclic group . For , the cyclotomic number of order is defined as the number of solutions of the following:
2.2 Properties of cyclotomic numbers of order
In this subsection, we recalled some elementary properties of cyclotomic numbers of order . Let be a prime for an odd prime and we write for some positive integer . It is clear that whenever and as well as . These imply the following:
Applying these facts, one can check that
where is given by
3. Cyclotomic matrices
This section presents the procedure to determine cyclotomic matrices of order for prime . We determine the equality relation of cyclotomic numbers and discuss how few of the cyclotomic numbers are enough for the construction of whole cyclotomic matrix. Further generators for a chosen value of will be determined followed by the generation of a cyclotomic matrix. At every step, we have included a numerical example for the convenience to understand the procedure easily.
For instance Table 1 depicts a typical cyclotomic matrix of order 8 (assuming ). Whose construction steps have been given in the next subsection.
3.1 Construction of cyclotomic matrix
Typically construction of a cyclotomic matrix has been subdivided into four subsequent steps. Below are those ordered steps for the construction of a cyclotomic matrix;
For given , choose a prime such that satisfies , . The initial entries of the cyclotomic matrix are the arrangement of pair of numbers where and usually vary from to .
Determine the equality relation of pair of , which reduces the complexity of pair of solution of Eq. (1), that is discuss in next sub-section.
Determine the generators of chosen (i.e. generators of ). Let , , ,…, be generators of .
Choose a generator (say ) of and put in Eq. (1). This will give cyclotomic matrix of order w.r.t. chosen generator .
The first step initializes the entries of cyclotomic matrix of order 2. Value of will be determined for given . Assuming , an example of such initialization of matrix of order 8 has been shown in Table 1.
For the construction of cyclotomic matrix, it does not require to determine all the cyclotomic numbers of a cyclotomic matrix which is shown in Table 1 . By well-known properties of cyclotomic numbers of order , cyclotomic numbers are divided into various classes, therefore there are a pair of the relation between the entries of initial table (Table 1) of a cyclotomic matrix. Thus to avoid calculating the same solutions in multiple times, we determine the equality relation of cyclotomic numbers (i.e. equality of solutions of ). In the next subsection, we will discuss which cyclotomic numbers are enough for the construction of the cyclotomic matrix. Thus it helps us to the faster computation of cyclotomic matrix.
3.2 Determination of equality relation of cyclotomic numbers
This subsection presents the procedure to determine the equality relation of cyclotomic numbers (i.e. the relation of pair of ), which reduces the complexity of solutions of pair of (see also ). For the determination of cyclotomic matrices, it is not necessary to obtain all cyclotomic numbers of order . The minimum number of cyclotomic numbers required to determine all the cyclotomic numbers (i.e. required for construction of cyclotomic matrix) depends on the value of positive integer on expressing prime . By (2), if is even, then
Thus by (5) and (6), cyclotomic numbers of order can be divided into various classes.
and : In this case, (5) gives classes of singleton, three and six elements. form singleton class, , , form classes of three elements where and rest of the cyclotomic numbers form classes of six elements.
and : In this case, (5) divide cyclotomic numbers of order into classes of singleton, second, three and six elements. form singleton class, , , form classes of three elements, where , which is grouped into classes of two elements and rest of the cyclotomic numbers form classes of six elements.
and : Using (6), once again we get classes of singleton, three and six elements. forms singleton class, , , form classes of three elements, where and rest of the cyclotomic numbers form classes of six elements.
and : In this situation, (6) partitions cyclotomic numbers of order into classes of singleton, two, three and six elements. Here form singleton class, , , form classes of three elements, where , which is grouped into classes of two elements and rest of the cyclotomic numbers form classes of six elements.
2: Declare integer variable .
3: INPUT , an odd prime and
4: Declare an array of size , where each element of array is tuple structure (i.e. ordered pair of , where and are integers).
5: INPUT , prime number greater than 2
Further, if entries of the updated table are non-negative, then each entry should be replace by , otherwise add . It is clear from above exploration, cyclotomic numbers of order are divided into different classes depending on the values of and . For and let be even, then give unique solution, cyclotomic numbers of the form , , where gives the same solutions and rest of cyclotomic numbers (i.e. ) which forms classes of six elements has maximum distinct numbers of solutions. Therefore the initial table (i.e. Table 1) of cyclotomic matrix reduces to Table 2. Similarly, for and let be odd, then give unique solution, cyclotomic numbers of the form , , where gives the same solutions and rest of cyclotomic numbers (i.e. ) which forms classes of six elements has maximum distinct numbers of solutions. Therefore the initial table (i.e. Table 1) of cyclotomic matrix reduces to Table 3. One can observe that pairs of two parameter numbers reduced to distinct pairs (see Table 2 and Table 3).
3.3 Determination of generators of
To determine the solutions of (1), we need the generator of the cyclic group . Let us choose finite field of order that satisfy . Let , , ,…, be generators of . We consider finite field of order (i.e. ), since the chosen value of with respect to the value of take previously. Now to determine the generators of cyclic group . The detail procedure to obtain the generator of has been depicted in Algorithm 2. If is a set that contain all the generator of , we could get elements of as , , , , , , , .
1: Declare integer variable , count
2: Declare integer array
6: Declare integer array
7: Declare integer variable
9: count = 0
28: is generator
3.4 Generation of cyclotomic matrices
This subsection, present an algorithm for the generation of cyclotomic matrices of order . Note that entries of cyclotomic matrices are solutions of (1). Thus we need the generator of the cyclic group , which is discussed in the previous subsection. On substituting the generators of in Algorithm 3, we obtain the cyclotomic matrices of order corresponding to different generators of . The chosen value of implies w.r.t. assume value of . Therefore the cyclotomic matrix will be obtain from Table 2. Let us choose a generator (say ) from set . On substituting in Algorithm 3, it will generate cyclotomic matrix of order over w.r.t. chosen generator . Matrix show the corresponding cyclotomic matrix of order w.r.t. chosen generator .
1: INPUT: The value of
2: Declare an array (where elements are two tuple structure)
3: Declare integer variable
4. The public-key cryptosystem
In this section, we present the approach for designing a public key cryptosystem using cyclotomic matrices discussed in Section 3. The scheme employ matrices of order , whose entries are cyclotomic numbers of order . The public key is a non-trivial generator, say of a set of generator in along with and . The set of generator is obtain by Algorithm 2. The chosen public keys generate a cyclotomic matrix as of required order (i.e. order of ) make use of Algorithm 3. Here, we define a trapdoor one-way function as ; , are non-trivial generators of . Thus, the secret key are the values of , , & . To encrypt a message, define composition of matrix as , where is a message block matrix, is a cyclotomic matrix w.r.t. and is the ciphertext matrix. Other way one can define . Therefore, the length of the ciphertext in CAC is equal to .
To decrypt a message, an algorithm is required to expand the secret keys provided by the secret values. Therefore, the Algorithm 4 is utilized for this purpose.
1: SECRET INPUT: The values of , , and
2: Algorithm 1
3: Algorithm 2
The main purpose, to utilize the above algorithm is to construct a non-singular cyclotomic matrix of order w.r.t. non-trivial generator () in . Now to decrypt the message, we define inverse composition relation of matrices, which is , where matrix is obtain by some efficient algebraic computation of matrix. Other way one can define respectively.
4.1 Determination of matrix
The following steps have been taken for the determination of matrix .
Determine the equality of cyclotomic matrix of order corresponding to the secret values of & , which is perform by Algorithm 1.
Each entry of equality of cyclotomic matrix is multiplied by .
Compute the inverse of equality of cyclotomic matrix generated in step 2.
Finally, on substitution the values of the generated cyclotomic matrix corresponding to to an inverse matrix in step 3.
The following two algorithms (i.e. Algorithm 5 & 6) are utilized to encrypt and decrypt a message in the proposed CAC, respectively.
1: Transfer the plain text (message) into its numerical value and store in matrix of order
2: PUBLIC INPUT: The values of and
3: Execute Algorithm 3
4: Check: Generated cyclotomic matrix in step 3 is non-singular
5: Cipher matrix: Multiply cyclotomic matrix and the matrix generated in step 1
6: Ciphertext: The corresponding text values of matrix generated in step 5
1: Input: The cipher matrix/ciphertext
2: Execute Algorithm 4
3: Each entries of equality of cyclotomic matrix (i.e. output matrix of Algorithm 1) is multiply by . The entries of the generated matrix are pair of cyclotomic number
4: Compute the inverse of generated matrix in step and substitute the value of each pair of cyclotomic number from generated matrix in step
5: Now multiply the cipher text matrix to generated matrix in step , we get back to the original plain text message.
4.2 Computational complexity of the CAC
In this section, we would validate the computational complexity of the proposed CAC. The computational complexity measures the amount of computational effort required, by the best as of now known techniques, to break a system . However, it is exceptionally hard to demonstrate the computational complexity of public-key cryptosystems [2, 3]. For instance, if the public modulus of RSA is factored into its prime components, at that point the RSA is broken. Be that as it may, it is not demonstrated that breaking RSA is identical to factoring its modulus . Here, we study the computational complexity of the CAC by providing arguments related to the inversion of the one-way function in CAC to a best known computational algorithm. The complexity of anonymous decryption could be understood as; if we assume that an attacker wants to recover the secret key by using all the information’s available to them. Then they need to solve the discrete logarithm problem (DLP) to find the secret key followed by a number of steps described in Algorithm 6. Since, the one-way function is define analogous to discrete logarithm problem (DLP). However, although most mathematicians and computer scientists believe that the DLP is unsolvable . The complexity of the DLP depends on the cyclic group. It is believed to be a hard problem for the multiplicative group of a finite field of large cardinality. Therefore even determining the very first step is nearly unsolvable.
If it is the case that somehow attacker manages to solve the DLP, then they have to determine Eq. (1) and calculate all the solutions corresponding to different pairs . Further, it is required to determine the relation matrix based on equality relation among the solutions of Eq. (1). Where entries of the relation matrix are the two-tuple structure of . Finally, entries of inverse of the relation matrix are required to replace through the implication of DLP.
Here we could observe the computational complexity as it increases with the value of and . Therefore it is nearly impossible to determine the secret key for a large value of and ; hence uphold the secure formulation claim of the proposed work.
4.3 An example of the CAC
In this section, we provide an example for the proposed CAC. The example is designed according to guidelines described in Section 4. The main purpose of this example is to show the reliability of our cryptosystem. It is important to note that this example is non-viable for the proposed CAC, since the values of the parameters are too small.
We choose two distinct non-trivial generators of a set of generator in (the set of generator is obtain by employing Algorithm 2), say and . Now, we evaluate the complex relation between these chosen generators, which can perform by DLP. One can write . Consider that . The public key is the public values & and the private key is the secret values , & . The public values generated cyclotomic matrix of order as required, which is
Now compute the inverse of and substitute the value from
Finally, we obtain
5. The complexity of CAC
Time and space are usually prominent factors to establish the effectiveness of security solutions. In the before seen sections, we have established the computational difficulty to break the proposed work. Further, we would demonstrate the complexity of the solution in terms of worst-case running time.
The time complexity of Algorithm 1 in worst case is . Since formation of matrix of order and Update_Table() individually will take . In algorithm 2,
Since is a positive integer, therefore when attains its minimum value i.e. 1,
For any higher value of , there is guarantee that
Hence, we conclude that Algorithm 2 can take in worst case.
Similarly, in Algorithm 3,
Encryption as expressed in Algorithm 5 constitutes of three logical divisions and the complexity of encryption would be the sum of the complexity of its part. The state divisions within are as follows;
Generating cyclotomic matrix
Checking the singularity of the cyclotomic matrix.
Multiplication of generated cyclotomic matrix and matrix corresponds to plain text.
Starting from the generation of the cyclotomic matrix, comprises the total complexity as stated earlier. Further, checking singularity involves the computation of determinants of the matrix of order . In worst case computing determinant of a matrix of order by fast algorithm  takes . Hence, singularity of the cyclotomic matrix of order could be computed in time. Finally, multiplication of cyclotomic matrix of order and matrix corresponds to plain text of order will take time. Therefore, Complexity of Encryption would become . Thus a polynomial time complexity seems to be quite worthwhile.
Decryption as expressed in Algorithm 6 that include Algorithm 4 which sums the complexity of Algorithm 1 and 3, therefore takes + time. Further, multiplication of cyclotomic matrix of order by a constant value , therefore yield complexity. Likewise, inverse of a matrix of order can be computed by a fast algorithm  in , therefore, inverse of generated matrix of order could be computed in time. Finally multiplication of two matrix of order could be computed in by best known algorithm  till date. Therefore, Complexity of decryption would be + + + , which becomes .
In this chapter, we have introduced a secured asymmetric key cryptography model applying the principle of cyclotomic numbers over a finite field. Procedure to generate cyclotomic matrix along with public & private key have been presented, where the relation between the public & private key has acquired by discrete logarithm problem (DLP). Finally, a convincing argument to strengthen the claim has been presented followed by the method of encryption, decryption & a numerical example.
The authors are thankful and acknowledge the Central University of Jharkhand, Ranchi, Jharkhand for providing the necessary facilities to carry out this research.
Mathematics Subject Classification (2010)
11T22; 11T71; 94A60; 11T24