# On the role of the Fibonacci matrix as key in modified ECC

Munesh Kumari1111🖂<EMAIL_ADDRESS>(Orcid: 0000-0002-6541-0284) ,
Jagmohan Tanti2222🖂<EMAIL_ADDRESS>
1Department of Mathematics, Central University of Jharkhand, India, 835205
2Department of Mathematics, Babasaheb Bhimrao Ambedkar University, Lucknow,
India, 226025

###### Abstract

In this paper, we have proposed a modified cryptographic scheme based on the
application of recursive matrices as key in ECC and ElGamal. For encryption,
we consider mapping analogous to affine Hill cipher in which a plaintext
matrix has been constructed by points corresponding to letters on elliptic
curves. In the formation of key-space, the generalized Fibonacci matrices have
been taken into account, which is the sequence of matrices. The beauty of
considering Fibonacci matrices is their construction where we need only two
parameters(integers) in place of $n^{2}$ elements. The use of a recursive
matrix makes a large keyspace for our proposed scheme and increases its
efficiency. Thus, it reduces time as well space complexity, and its security &
strength is based on EC-DLP which is a hard problem in number theory.

Keyword: Elliptic Curve Cryptography; Fibonacci Sequences; Multinacci
Matrices; ElGamal Cryptosystem; Key Space
Mathematics Subject Classifications: 11T71; 14G50; 14H52; 68P25; 94A60

##  1 Introduction

In discrete mathematics, recursive matrices are rich in many senses like
properties, construction, the existence of inverse…etc. One of the popular
recursive matrices is generalized Fibonacci matrix [9], it can be constructed
with only two parameters (n,k) and its element is taken from a generalized
Fibonacci sequence. Kalika et.al.[11] proposed a public key cryptography based
on generalized Fibonacci matrices where they also discussed properties of
Fibonacci matrices.
Nowadays dependency of the people across the world on the internet has been
increased. After arising of COVID-19 situation, most of the meetings, academic
activities, business, etc. are taking place in online mode where we used to
share a huge number of data (e.g. personal information, video, audio, images,
etc.). Now the question arises, is our data received by the authenticated
recipient with integrity and confidentiality? So, here comes the Cryptography
with the solution to these problems. Cryptography is the science of study
about the security, privacy, and confidentiality of information transmitted
over a secured channel.
Elliptic curve cryptography(ECC) has recently attracted the industry sectors
and academia very much. The reason behind this attraction is that for the
equivalent security it uses a significantly smaller key size as compared to
other schemes like RSA and ElGmal. Use of ECC reduces processing power,
computations, and storage space. Hence it is ideal for implementation.
A public-key cryptosystem based on discrete logarithm problem(DLP) was
proposed by T. ElGamal[3] in 1984 which is known as ElGamal Cryptosystem. A
new approach to public key cryptography(PKC) using Elliptic curves was taken
by N.Koblitz[8] named as Elliptic Curve Cryptography(ECC). The most
fascinating thing about ECC was that it uses a smaller key size for the same
level of security as the RSA cryptosystem provides. The basics of elliptic
curves, algebra on it, and the benefits of using elliptic curve cryptography
over RSA can be found in [17, 6, 10, 15]. Balamurugan et.al [1] proposed a new
approach to the ECC based on the application of matrices and ElGamal
technique, further they claimed to provide high security for the encrypted
messages. Singh et.al[14] have proposed an alternative to the problem of a
large key size that requires high computing power devices. A fast mapping
method based on the matrix approach is presented by Geetha et.al[4] for ECC,
where they offer high security for the encrypted message. Priyatharsan et.al.
in [12] proposed a new cryptographic system using the elliptic curve
cryptography based on square matrices. In[1, 4, 12], they have worked with
matrix approach and in this one has to check the invertibility of a matrix and
then find the inverse of that matrix which takes much time as well as space.
In most of the cryptographic schemes, authors have considered matrix for
encryption and key generation. Here comes the requirement of fast computation
and key generation, so for that purpose, we are using generalized Fibonacci
matrices which help us in fast computation.

This paper is organized as follows. In section 2, the basic concepts of
Elliptic Curve Cryptography and properties of multinacci matrices are
outlined. In section 3, we have proposed an encryption scheme analogous to
affine Hill cipher in which a plaintext matrix has been constructed by points
corresponding to letters followed by an example. And lastly, in section 4, we
have done analysis on key-space and probability of retrieving the key matrix
in the context of $GL_{n}(\mathbb{F}_{p})$.

##  2 Preliminaries

###  2.1 Elliptic Curve over a finite field [16, 5, 13]

######  Definition 2.1 (Elliptic Curve).

For $p\in\mathbb{Z}^{+}$ a prime and $\mathbb{F}_{p}=\mathbb{Z}/p\mathbb{Z}$,
an elliptic curve $E$ over $\mathbb{F}_{p}$ is the set of points (x, y) with
x,y $\in\mathbb{F}_{p}$ which satisfy the equation

$y^{2}=x^{3}+ax+b,$ (2.1)

where $a,b\in\mathbb{F}_{p}$ such that $4a^{3}+27b^{2}\neq 0\pmod{p}$ together
with a single element denoted by $\mathcal{O}$ and called the ”point at
infinity”.

The elliptic curve over $\mathbb{F}_{p}$ is denoted by
$E_{\mathbb{F}_{p}}(a,b)$.

The points on $E_{\mathbb{F}_{p}}(a,b)$ forms an additive abelian group with
’$\mathcal{O}$’ as the identity element.

###  2.2 Generalized Fibonacci Matrix[11]

######  Definition 2.2.

The generalized Fibonacci sequence of order $n$ is defined by the recurrence
relation,

$t_{k+n}=t_{k}+t_{k+1}+t_{k+2}+...+t_{k+n-1},\hskip 28.45274ptk\geq 0$ (2.2)

with $t_{0}=t_{1}=...=t_{n-2}=0$ and $t_{n-1}=1$.

The generalized Fibonacci sequence is also known as multinacci sequence and
it’s corresponding matrix is generalized Fibonacci matrix (sometime it is also
called multinacci matrix).
Multinacci sequence can be also defined in negative direction by rearranging
eqn.(2.2), which is given as,

$t_{-k}=t_{-k+n}-(t_{-k+1}+...+t_{-k+n-1}),\hskip 28.45274ptfor~{}~{}k\geq-1,$
(2.3)

where initial values are same as of eqn.(2.2).
In particular for $n=2$, eqn.(2.2) is Fibonacci sequence [A000045] while for
$n=3$, eqn.(2.2) gives tribonacci sequence [7, 9].

#### Multinacci Matrix/Generalized Fibonacci matrix(GFM)

The generalized Fibonacci matrix(GFM)[11] $F_{n}^{k}$ of order n is given by,

$F_{n}^{k}=\begin{bmatrix}t_{k+n-1}&t_{k+n-2}+t_{k+n-3}+...+t_{k}&\cdots&t_{k+n-2}&\\\
t_{k+n-2}&t_{k+n-3}+t_{k+n-4}+...+t_{k-1}&\cdots&t_{k+n-3}\\\
\vdots&\vdots&\ddots&\vdots\\\
t_{k+1}&t_{k}+t_{k-1}+...+t_{k-n+2}&\cdots&t_{k}\\\
t_{k}&t_{k-1}+t_{k-2}+...+t_{k-n+1}&\cdots&t_{k-1}\end{bmatrix}_{n\times
n},~{}~{}~{}\text{for}~{}~{}k=0,\pm 1,\pm 2,...$ (2.4)

with initial matrix,

$\displaystyle F_{n}=\begin{bmatrix}1&1&1&...&1&1\\\ 1&0&0&...&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&0&...&0&0\\\
0&0&0&...&1&0\end{bmatrix}_{n\times n},$ (2.5)

where $F_{n}^{0}=I_{n}$ gives identity matrix of order n and $t_{k}$
represents the $k^{th}$ term of multinacci sequence.
The determinant of $F_{n}^{k}$ is $det(F_{n}^{k})$ = $(-1)^{k(n-1)}$ which is
non-zero for all $k$, $n\in\mathbb{N}$.

And inverse of GFM is given by,

$(F_{n}^{k})^{-1}=F_{n}^{-k}=\begin{bmatrix}t_{-k+n-1}&t_{-k+n-2}+t_{-k+n-3}+...+t_{-k}&...&t_{-k+n-2}\\\
t_{-k+n-2}&t_{-k+n-3}+t_{-k+n-4}+...+t_{-k-1}&...&t_{-k+n-3}\\\
\vdots&\vdots&\ddots&\vdots\\\
t_{-k+1}&t_{-k}+t_{-k-1}+...+t_{-k-n+2}&...&t_{-k}\\\
t_{-k}&t_{-k-1}+t_{-k-2}+...+t_{-k-n+1}&...&t_{-k-1}\end{bmatrix}_{n\times
n}.$ (2.6)

$i.e.$ to calculate inverse of GFM, one doesn’t need to follow usual method,
simply replace $k$ by $-k$ in (2.4).
This is the main motivation to consider generalized Fibonacci matrices for
encryption-decryption which help us in reducing time complexity and able to
perform recursively.

##  3 Proposed scheme

Multinacci matrices are rich in many sense like multiplication and finding
inverse. As we know that for fast and secure communication, we need an
efficient algorithm which can generate and verify key quickly. So to make more
efficient and fast encryption in ECC, we are taking in account multinacci
matrices for key generation, for exchange of parameters ElGamal technique[3]
and an encryption scheme analogous to affine hill cipher.
Our proposed method is defined in three part,

  * •

Construction of a public key

  * •

An algorithm for key generation

  * •

An encryption scheme and decryption scheme

which are discussed below step by step.

#### Construction of public key:

Let $y^{2}\equiv x^{3}+ax+b\pmod{p}$ such that $4a^{3}+27b^{2}\pmod{p}\neq 0$
be an Elliptic Curve over the finite field $\mathbb{F}_{p}$ denoted by
$E_{\mathbb{F}_{p}(a,b)}$ and $G$ be a cyclic subgroup of $\mathbb{F}_{p}$
with a generator point $E$ . For better understanding, let two entities Alice
and Bob want to communicate with each other. So, to construct public Key Alice
have to do following steps.
Let us consider $S$={$F_{n}^{k}|F_{n}$ is a generalized Fibonacci matrix of
order n and $k\in\mathbb{N}$} over finite field $\mathbb{F}_{p}$.

  1. 1.

First Alice chooses a primitive element (say $\beta$) of $p$ and a secret
number $r$ such that $1<r<p-1$.

  2. 2.

Calculate, $E_{1}\equiv\beta^{r}\pmod{p}.$

  3. 3.

Now, $(\beta,E_{1})$ is Alice’s public key and $(r)$ is her secret key.

#### Key Generation and Encryption:

Now, to send message $P$ to Alice, Bob first compute encryption key using
Alice’s public key $(\beta,E_{1})$ and encrypts his message $P$ as follows:

  1. 1.

Bob chooses a secret number $e$ such that $1<e<p-1$.

  2. 2.

Next, compute

$\displaystyle a\equiv\beta^{e}\pmod{p},$ $\displaystyle k\equiv
E_{1}^{e}\pmod{p}.$

  3. 3.

Compute key matrix 333$F_{n}^{k}$ is a multinacci matrix of order n which can
be directly calculated using multinacci sequence not as usual multiplication.
(say$K$) as $K\equiv F_{n}^{k}\pmod{p}.$

  4. 4.

Convert plain text $P$ in the points of $E_{\mathbb{F}_{p}}(a,b)$, say the
points are $P_{1},P_{2},P_{3},...,P_{m}$. Now construct a matrix of order
$n\times n$ as

$\begin{bmatrix}P_{1}&P_{n+1}&...&P_{2n-1}\\\ P_{2}&P_{n+2}&...&P\\\
\vdots&\vdots&\vdots\\\ P_{n}&P_{2n}&...&P_{n^{2}}\\\ \end{bmatrix}_{n\times
n}.$

  5. 5.

Encryption: Now encryption of plain text takes place as follow,
$C\equiv\left[K_{n\times n}(P_{n\times n}+kEJ_{n\times n})\right]\pmod{p}$,
where $J=\begin{bmatrix}1&...&1\\\ \vdots&\ddots&\vdots\\\
1&...&1\end{bmatrix}_{n\times n}$ .

  6. 6.

Now, Bob will send $(a,C)$ to Alice.

#### Decryption:

After receiving $(a,C)$ from Bob, Alice perform following operations to
recover plaintext:

  1. 1.

Alice with her secret key($r$), first calculate $k$ as,

$\displaystyle k\equiv a^{r}\pmod{p}.$

  2. 2.

Compute decryption key (say D),

$\displaystyle D\equiv F_{n}^{-k}\pmod{p}$

Where $F_{n}^{-k}\pmod{p}$ can be directly calculated (see equation(2.6)) with
multinacci sequence.

  3. 3.

Calculate ’$-E$’ where $-E$ is a point with the same x-coordinate but negative
y-coordinate of $E$ $i.e.$ if $E=(x,y)$, then $-E=-(x,y)=(x,-y)$ which also
lies on $E_{\mathbb{F}_{p}}(a,b)$.

  4. 4.

Decrypt the ciphertext as

$\displaystyle P$ $\displaystyle\equiv$ $\displaystyle(D_{n\times n}C_{n\times
n}+k(-E)J_{n\times n})\pmod{p}$ $\displaystyle\equiv$
$\displaystyle(D_{n\times n}C_{n\times n}-kEJ_{n\times n})\pmod{p}$

where $J$ is given by (5).

###  3.1 Algorithm

Let E be a generator point of a cyclic subgroup of $E_{\mathbb{F}_{p}(a,b)}$
and $S$={$F_{n}^{k}|F_{n}$ is a generalized Fibonacci matrix of order n and
$k\in\mathbb{N}$} over finite field $\mathbb{F}_{p}$.

#### Algorithm for Generating Public Key

  1. 1.

$\beta$ $\leftarrow$ a primitive element of $p$ .

  2. 2.

Secret Key(r) $\leftarrow$ $r$ such that $1<r<p-1$.

  3. 3.

Public Key: $E_{1}\leftarrow\beta^{r}\pmod{p}.$

  4. 4.

Publish $(\beta,E_{1})$ publicly.

Encryption Algorithm

  1. 1.

Private Key($e$) $\leftarrow e$ such that $1<e<p-1$.

  2. 2.

$a\leftarrow\beta^{e}\pmod{p}$ and $k\leftarrow E_{1}^{e}\pmod{p}.$

  3. 3.

Key Matrix: $K\leftarrow F_{n}^{k}\pmod{p}.$

  4. 4.

Encryption: $C\leftarrow\left[K_{n\times n}(P_{n\times n}+k\times EJ_{n\times
n})\right]\pmod{p}$, ,where $J$ is given by (5).

  5. 5.

Transfer $(a,C)$.

Decryption Algorithm
After receiving $(a,C)$,

  1. 1.

$k\leftarrow a^{r}\pmod{p}.$

  2. 2.

Decryption Key: $D\leftarrow F_{n}^{-k}\pmod{p}$.

  3. 3.

Decryption: $P\leftarrow(D_{n\times n}C_{n\times n}-k\times EJ_{n\times
n})\pmod{p}$.

###  3.2 Example

######  Example 1.

Encrypt the plaintext COVID-19 with above proposed scheme.

###### Solution:.

Let $y^{2}=x^{3}+3x+41\pmod{47}$ be a elliptic curve. We denote it as
$E_{\mathbb{F}_{47}}(3,41)$ and $|E_{\mathbb{F}_{47}}(3,41)|=47$.
Now, points of $(E_{\mathbb{F}_{47}}(3,41))$ are :
(2,14) (2,33) (10,15) (10,32) (11,18) (11,29) (13,16) (13,31) (14,17) (14,30)
(16,7) (16,40) (19,1) (19,46) (20,8) (20,39) (21,23 (21,24) (24,5) (24,42)
(27,21) (27,26) (28,9) (28,38) (30,23) (30,24) (33,13) (33,34) (34,22) (34,25)
(35,4) (35,43) (38,15) (38, 32) (40,10) (40,37) (41,18) (41,29) (42,18)
(42,29) (43,23) (43,24) (45,11) (45,36) (46,15) (46,32) $\mathcal{O}$
Let $E=(2,14)$ be the generator point of $E_{\mathbb{F}_{47}}(3,41)$. We map
the letters, symbols, numbers, and special characters as follows:
A B C D E F G H I J K L (2,14) (28,9) (21,24) (33,34) (40,10) (11,29) (42,29)
(45,11) (27,26) (35,4) (46,15) (20,39) M N o P Q R S T U V W X (41,18) (16,40)
(43,24) (10,15) (24,42) (30,23) (19,46) (38,15) (14,17) (34,25) (13,16)
(13,31) Y Z 0 1 2 3 4 5 6 7 8 9 (34,22) (14,30) (38,32) (19,1) (30,24) (24,5)
(10,32) (43,23) (16,7) (41,29) (20,8) (46,32) ~ ! @ # $ % ^ & * - , (35,43)
(27,21) (45,36) (42,18) (11,18) (40,37) (33,13) (21,23) (28,38) (2,33)
$\mathcal{O}$

#### Construction of Public key:

Consider $S$={$F_{2}^{k}|k\in\mathbb{N}$} over finite field $\mathbb{F}_{47}$.

  1. 1.

Alice chooses a primitive element ($\beta$) 31 and her secret key ($r$) 14.

  2. 2.

Alice’s public key

$\displaystyle E_{1}\equiv\beta^{r}\pmod{p}\equiv 31^{14}\pmod{47}\equiv
37\pmod{47}.$ (3.1)

Here, Alice publish $(\beta,E_{1})$=$(31,37)$ publicly and $r=14$ is her
secret key.

#### Key Generation and Encryption:

Using Alice’s public key $(\beta,E_{1})$=$(31,37)$, Bob will generate
encryption key and then encrypts his plaintext as follows:

  1. 1.

Bob chooses his private key such that $1<e<46$, say $e=21$ .

  2. 2.

Next, compute

$\displaystyle a$ $\displaystyle\equiv$ $\displaystyle\beta^{e}\pmod{p}\equiv
31^{21}\pmod{47}\equiv 38\pmod{47},$ $\displaystyle k$ $\displaystyle\equiv$
$\displaystyle E_{1}^{e}\pmod{p}\equiv 37^{21}\pmod{47}\equiv 8\pmod{47}.$

  3. 3.

Now, calculate key matrix

$\displaystyle K$ $\displaystyle\equiv$ $\displaystyle
F_{2}^{8}\pmod{47}\equiv\begin{bmatrix}f_{9}&f_{8}\\\ f_{8}&f_{7}\\\
\end{bmatrix}\pmod{47}$ $\displaystyle\equiv$
$\displaystyle\begin{bmatrix}34&21\\\ 21&13\\\ \end{bmatrix}\pmod{47}.$

  4. 4.

Given plaintext is ’COVID-19’.
Now mapping letters of plaintext to the point of $(E_{\mathbb{F}_{47}}(3,41))$
which is given by,

C O V I D - 1 9 (21,14) (43,24) (34,25) (27,26) (33,34) (2,33) (19,1) (46,32)

  5. 5.

Now constructing plaintext matrices,
$P1=\begin{bmatrix}C&V\\\ O&I\\\ \end{bmatrix}$
=$\begin{bmatrix}(21,24)&(34,25)\\\ (43,24)&(27,26)\\\ \end{bmatrix}$ and
$P2=\begin{bmatrix}D&1\\\ -&9\\\ \end{bmatrix}$
=$\begin{bmatrix}(33,34)&(19,1)\\\ (2,33)&(46,32)\\\ \end{bmatrix}.$
At last encryption takes place as,

$\displaystyle C1$ $\displaystyle\equiv$
$\displaystyle\left[K(P1+kEJ)\right]\pmod{p}$ $\displaystyle\equiv$
$\displaystyle\begin{bmatrix}34&21\\\ 21&13\\\
\end{bmatrix}\left(\begin{bmatrix}(21,24)&(34,25)\\\ (43,24)&(27,26)\\\
\end{bmatrix}+(45,11)\begin{bmatrix}1&1\\\ 1&1\\\
\end{bmatrix}\right)\pmod{47}$ $\displaystyle\equiv$
$\displaystyle\begin{bmatrix}(46,15)&(16,40)\\\ (41,18)&(40,10)\\\
\end{bmatrix}\pmod{47}\equiv\begin{bmatrix}K&N\\\ M&E\\\ \end{bmatrix}.$
$\displaystyle C2$ $\displaystyle\equiv$
$\displaystyle\left[K(P2+kEJ)\right]\pmod{p}$ $\displaystyle\equiv$
$\displaystyle\begin{bmatrix}34&21\\\ 21&13\\\
\end{bmatrix}\left(\begin{bmatrix}(33,34)&(19,1)\\\ (2,33)&(46,32)\\\
\end{bmatrix}+(45,11)\begin{bmatrix}1&1\\\ 1&1\\\
\end{bmatrix}\right)\pmod{47}$ $\displaystyle\equiv$
$\displaystyle\begin{bmatrix}(27,21)&(16,7)\\\ (16,40)&(20,39)\\\
\end{bmatrix}\pmod{47}\equiv\begin{bmatrix}!&6\\\ N&L\\\ \end{bmatrix}.$

Thus $C=\begin{bmatrix}K&N&!&6\\\ M&E&N&L\\\ \end{bmatrix}$.

Here, Plaintext($P$) = $COVID-19\rightarrow KMNE!N6L$ = Ciphertext($C$).

  6. 6.

Now, Bob can share $(a,C)=(38,15,KMNE!N6L)$ with Alice.

#### Decryption:

After receiving $(a,C)=(38,KMNE!N6L)$ from Bob, Alice perform following
operations to recover plaintext:

  1. 1.

Alice calculates,

$\displaystyle k$ $\displaystyle\equiv$ $\displaystyle a^{r}\pmod{p}\equiv
38^{14}\pmod{47}\equiv 8\pmod{47}.$

  2. 2.

Calculate Decryption Key$(D)$,

$\displaystyle D$ $\displaystyle\equiv$ $\displaystyle
F_{2}^{-8}\pmod{47}\equiv\begin{bmatrix}f_{-7}&f_{-8}\\\ f_{-8}&f_{-9}\\\
\end{bmatrix}\pmod{47}$ $\displaystyle\equiv$
$\displaystyle\begin{bmatrix}13&26\\\ 26&34\\\ \end{bmatrix}\pmod{47}.$

  3. 3.

Decryption of ciphertext

$\displaystyle P1$ $\displaystyle\equiv$ $\displaystyle(DC1-kEJ)\pmod{47}$
$\displaystyle\equiv$ $\displaystyle\begin{bmatrix}13&26\\\ 26&34\\\
\end{bmatrix}.\begin{bmatrix}(46,15)&(16,40)\\\ (41,18)&(40,10)\\\
\end{bmatrix}+\begin{bmatrix}(45,36)&(45,36)\\\ (45,36)&(45,36)\\\
\end{bmatrix}\pmod{47}$ $\displaystyle\equiv$
$\displaystyle\begin{bmatrix}(21,24)&(34,25)\\\ (43,24)&(27,26)\\\
\end{bmatrix}\pmod{47}\equiv\begin{bmatrix}C&V\\\ O&I\\\ \end{bmatrix}.$
$\displaystyle P2$ $\displaystyle\equiv$ $\displaystyle(DC2-kEJ)\pmod{47}$
$\displaystyle\equiv$ $\displaystyle\begin{bmatrix}13&26\\\ 26&34\\\
\end{bmatrix}.\begin{bmatrix}(27,21)&(16,7)\\\ (16,40)&(20,39)\\\
\end{bmatrix}+\begin{bmatrix}(45,36)&(45,36)\\\ (45,36)&(45,36)\\\
\end{bmatrix}\pmod{47}$ $\displaystyle\equiv$
$\displaystyle\begin{bmatrix}(33,34)&(19,1)\\\ (2,33)&(46,32)\\\
\end{bmatrix}\pmod{47}\equiv\begin{bmatrix}D&1\\\ -&9\\\ \end{bmatrix}.$

Thus $P=\begin{bmatrix}C&V&D&1\\\ O&I&-&9\\\ \end{bmatrix}$.

So, KMNE!N6L $\rightarrow$ COVID-19.

∎

##  4 Analysis of Key space

In group theory, general linear group $GL_{n}(\mathbb{F}_{p})$ denotes the
group of invertible matrices of order $n$ over the finite field
$\mathbb{F}_{p}$ where p is prime and it’s order[2] is given by

$|GL_{n}(\mathbb{F}_{p})|=(p^{n}-p^{n-1})(p^{n}-p^{n-2})\cdots(p^{n}-p^{1})(p^{n}-1).$
(4.1)

In our work, we consider the set of generalized Fibonacci matrices over finite
field $\mathbb{F}_{p}$ and these matrices are invertible. Here we have
presented a table of possible key-spaces for our proposed scheme based on
general linear group over a finite field $\mathbb{F}_{p}$ in particular for
$n=3$ and $n=4$.

Prime(p) |  Possible Key spaces on $GL_{3}(\mathbb{F}_{p})$ |  Possible Key spaces on $GL_{4}(\mathbb{F}_{p})$
---|---|---
29 |  1.3989$\times 10^{13}$ |  2.4131$\times 10^{23}$
31 |  2.5559$\times 10^{13}$ |  7.0320$\times 10^{23}$
37 |  1.2635$\times 10^{14}$ |  1.1995$\times 10^{25}$
41 |  3.1920$\times 10^{14}$ |  6.2166$\times 10^{25}$
43 |  4.9063$\times 10^{14}$ |  1.3336$\times 10^{26}$
47 |  1.0948$\times 10^{15}$ |  5.5465$\times 10^{26}$
53 |  3.2363$\times 10^{15}$ |  3.8017$\times 10^{27}$
59 |  8.5136$\times 10^{15}$ |  2.1187$\times 10^{28}$
61 |  1.1499$\times 10^{16}$ |  3.6139$\times 10^{28}$
67 |  2.6794$\times 10^{16}$ |  1.6239$\times 10^{29}$
⋮ | ⋮ | ⋮
Table 1: Possible key spaces of order 3 & 4.

From table we conclude that increase in value of $p$ results a large key
space. Simultaneously, increase in size of matrix also corresponds to a large
key space which can be easily observed in above table. Thus, it is impractical
to recover the key by an intruder by brute force attack. In such case,
intruder may try some other attacks.

### Brute Force Analysis

An intruder can not uncover plaintext until and except if, he has not private
key for the beneficiary. Also in case of large prime number, the keyspace will
be quite large which makes a brute force for finding private key impossible
for a intruder. In the following table, we have shown the probability of
retrieving encryption key matrix in particular for $n=3~{}\&~{}n=4$ by brute
force.

Prime(p) |  Probability on $GL_{3}(\mathbb{F}_{p})$ |  Probability on $GL_{4}(\mathbb{F}_{p})$
---|---|---
29 | $7.15\times 10^{-14}$ | $4.14\times 10^{-24}$
31 | $3.91\times 10^{-14}$ |  1.42$\times 10^{-24}$
37 |  7.91$\times 10^{-15}$ |  8.33$\times 10^{-26}$
41 |  3.13$\times 10^{-15}$ |  1.60$\times 10^{-26}$
43 |  2.03$\times 10^{-15}$ |  7.50$\times 10^{-27}$
47 |  9.13$\times 10^{-16}$ |  1.80$\times 10^{-27}$
53 |  3.09$\times 10^{-16}$ |  2.63$\times 10^{-28}$
59 |  1.17$\times 10^{-16}$ |  4.72$\times 10^{-29}$
61 |  8.70$\times 10^{-17}$ |  2.77$\times 10^{-29}$
67 |  3.73$\times 10^{-17}$ |  6.16$\times 10^{-30}$
⋮ | ⋮ | ⋮
Table 2: Probability of retrieving key matrix.

From the table, we observe that if we take parameters $n$ and $p$ sufficiently
large, the probability of getting the key matrix is negligible which makes
this cryptographic scheme secure against brute force attack.

Some times intruder performs chosen-plaintext attack, where he used to choose
a plain text and try to get corresponding ciphertext. With the help of that
information intruder try to get encryption key and other relevant information
regarding encryption.
In our proposed method, ciphertext C is given by

$C\equiv K(P+kEJ)\pmod{p}.$ (4.2)

In equation (4.2) it is almost impossible to calculate K even though C and P
is known because of the elliptic curve discrete logarithm problem (ECDLP)(see
[5]). So in this context again our proposed methodology is secure against CPA.

##  5 Conclusion

In this paper, we have proposed a modified public key cryptography along with
Elliptic curve cryptography and Elgamal using multinacci matrices over a
finite field $\mathbb{F}_{p}$. With the help of multinacci matrices, we reduce
time as well as space complexity of computation. We have used recursive nature
of direct calculation of inverse matrix and $n^{th}$ power of a matrix for
fast computation. Also, we have observed that if we increase the prime number,
keyspace increases as well and size of key matrix do not follow primes which
results randomness in size. The security of our proposed cryptography depends
upon the discrete logarithm problem of ECC which is a hard problem in number
theory. In our analysis, we found that our proposed method has large key
space, quite robust, and can be implemented easily.

### Acknowledgment

The authors are thankful to anonymous reviewer for their care and advice. The
first author acknowledge the University Grant Commission(UGC), India for
providing fellowship for this research work.

## References

  * [1] Balamurugan, R., Kamalakannan, V., Rahul, G. D., and Tamilselvan, S. Enhancing security in text messages using matrix based mapping and elgamal method in elliptic curve cryptography.  In 2014 International Conference on Contemporary Computing and Informatics (IC3I) (2014), IEEE, pp. 103–106.
  * [2] Dummit, D. S., and Foote, R. M. Abstract algebra, vol. 3.  Wiley Hoboken, 2004.
  * [3] ElGamal, T. A public key cryptosystem and a signature scheme based on discrete logarithms.  IEEE transactions on information theory 31, 4 (1985), 469–472.
  * [4] Geetha, G., and Jain, P. Implementation of matrix based mapping method using elliptic curve cryptography.  International Journal of Computer Applications Technology and Research 3, 5 (2014), 312–317.
  * [5] Hankerson, D., Menezes, A. J., and Vanstone, S. Guide to Elliptic Curve Cryptography.  Springer Science & Business Media, 2004.
  * [6] Hoffstein, J., Pipher, J., Silverman, J. H., and Silverman, J. H. An introduction to mathematical cryptography, vol. 1.  Springer, 2008.
  * [7] Johnson, R. C. Fibonacci numbers and matrices.  manuscript available at http://www. dur. ac. uk/bob. johnson/fibonacci (2008).
  * [8] Koblitz, N. Elliptic curve cryptosystems.  Mathematics of computation 48, 177 (1987), 203–209.
  * [9] Koshy, T. Fibonacci and Lucas numbers with applications.  John Wiley & Sons, 2019.
  * [10] Paar, C., and Pelzl, J. Understanding cryptography: a textbook for students and practitioners.  Springer Science & Business Media, 2009.
  * [11] Prasad, K., and Mahato, H. Cryptography using generalized fibonacci matrices with affine-hill cipher.  Journal of Discrete Mathematical Sciences and Cryptography (2021), 1–12.
  * [12] Priyatharsan, U., Rupasinghe, P. L., and Murray, I. A new elliptic curve cryptographic system over the finite fields.  In 2017 6th National Conference on Technology and Management (NCTM) (2017), IEEE, pp. 164–169.
  * [13] Silverman, J. H., and Tate, J. T. Rational points on elliptic curves, vol. 9.  Springer, 1992.
  * [14] Singh, L. D., and Debbarma, T. A new approach to elliptic curve cryptography.  In 2014 IEEE International Conference on Advanced Communications, Control and Computing Technologies (2014), IEEE, pp. 78–82.
  * [15] Singh, S. R., Khan, A. K., and Singh, T. S. A critical review on elliptic curve cryptography.  In 2016 International Conference on Automatic Control and Dynamic Optimization Techniques (ICACDOT) (2016), IEEE, pp. 13–18.
  * [16] Stallings, W. Cryptography and network security: principles and practice.  Pearson Upper Saddle River, 2017.
  * [17] Stinson, D. R. Cryptography: theory and practice.  Chapman and Hall/CRC, 2005.


#  Predictions on the execution of a CNOT gate of the reverse of the arrow of
time

G. Morales
M. Ávila
Centro Universitario UAEM Valle de Chalco, UAEMex
María Isabel, Valle de Chalco
Estado de México, CP 56615.
F. Soberanes
Tecnologico de Estudios Superiores de Chalco
Tlapala, Chalco
Estado de México, CP 56641<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Recently it has been pointed out that an outstanding application of an IBM
quantum computer is to reverse the arrow of time [Lesovik et al. Sci. Rep. 9,
1 (2019)]. The issue of the consequences of the reversal of the arrow of time
on the execution of a CNOT gate by a quantum device is addressed. It is
predicted that if the CNOT gate is executed towards the future then this was
previously executed in the past. The above might confirm the paradigm that an
event in the present time influences another event in the past time [2]. Such
a physical phenomena is called retrocausality.

A considerable amount of interest has been paid to the crucial observation
done by Lesovik et al [1] in the sense that the arrow of time can be inverted
in an IBM quantum computer. Undoubtedly the above is one of the most
outstanding application of a quantum computer. It is worth to observe also
that the result of Ref. [1] sheds light on the enigma of the correlation
between time-symmetric fundamental laws of Physics and irreversibility of the
world [3]-[4]. Furthermore, the above pave the way for a further revolutionary
technological applications of a quantum computer. However, so far it has not
been explored the issue of the consequences on the execution of a basic
quantum gate by a quantum device of the reverse of the arrow of time. In the
present work it is addressed such an issue. In order to proceed, we consider
such a quantum device as the diamond quantum computer. It is worth to observe
that a diamond quantum computer is a very promising technology with
outstanding capabilities [7]-[8]. Then it is verified first, that this quantum
computer executes the CNOT gate towards the future. After that, it is inverted
the time towards the past and studied the consequence of the above on the
execution of the CNOT gate. It is predicted that such a quantum gate was
previously executed in the past. At this stage it result important to observe
that the above result might confirm the old paradigm of retrocausality.

A quantum computer must work by executing of a primitive operations named
quantum gates. A CNOT gate [5] is one of the the most primitive operation that
can be performed by a quantum computer. At this stage it is worth to observe
that a quantum computer architecture is often described by a Schröedinger
equation with a suitable Hamiltonian [6]-[10]. In particular, the execution of
several different quantum protocols in a diamond quantum computer can be
performed with the use of a Schroedinger equation with a RF based Hamiltonian
[7]-[8]. Within the above approach we first verify that a diamond quantum
computer can execute a CNOT gate towards the future in the sense of the Second
Law of Thermodynamics [11]. Then, it is inverted the time and studied the
consequences of the above on the execution of the CNOT gate. The present work
is organized as follows: it is first introduced the Hamiltonian describing a
diamond quantum computer. Then it is proved that a diamond quantum computer
executes a CNOT gate from the present time towards the past time. Finally a
series of conclusions are given.

The corresponding Schröedinger equation associated the diamond quantum
computer is [7]

$\displaystyle i\hbar\frac{\partial}{\partial t}\mid\psi(t)\rangle$
$\displaystyle=$
$\displaystyle\Bigl{\\{}-\hbar\left(w_{1}S_{1}^{Z}+w_{2}S_{2}^{Z}\right)-\frac{J}{\hbar}\left(S_{1}^{Z}S_{2}^{Z}\right)+$
(1)
$\displaystyle\frac{\Omega}{2}\Bigl{[}\left(e^{i\theta_{1}}S_{1}^{-}+e^{-i\theta_{1}}S_{1}^{+}\right)+$
$\displaystyle\left(e^{i\theta_{2}}S_{2}^{-}+e^{-i\theta_{2}}S_{2}^{+}\right)\Bigr{]}\Bigr{\\}}\mid\psi(t)\rangle,$

where $\hbar=1$ is Planck’s constant, $w_{1}$ ( $w_{2}$) are Larmor’s
frequencies, $S_{1}^{Z}$ ($S_{2}^{Z}$) are the $z$-components of the spin of
qubit 1 (qubit 2), $S_{1}^{-}$ ($S_{2}^{-}$) are the lowering spin operator of
the qubit 1 (qubit 2), $S_{1}^{+}$ ($S_{2}^{+}$) are the raising spin operator
of the qubit 1 (qubit 2), $J$ is a coupling constant111If $J>0$ the diamond
quantum computer is in an antiferromagnetic regime but if $J<0$ this is in a
ferromagnetic regime [12]., $\Omega$ is Rabi’s frequency, and
$\theta_{i}=w_{i}t+\varphi_{i}$ ($i=1,2$) being $\varphi_{i}$ ($i=1,2$) an
arbitrary phases.

By observing that a general two-qubit state can be written as

$\displaystyle\mid\psi(t)\rangle=C_{0}(t)\mid 00\rangle+C_{1}(t)\mid
01\rangle+C_{2}(t)\mid 10\rangle+C_{3}(t)\mid 11\rangle,$ (2)

where

$\displaystyle\mid C_{0}(t)\mid^{2}+\mid C_{1}(t)\mid^{2}+\mid
C_{2}(t)\mid^{2}+\mid C_{3}(t)\mid^{2}=1,$ (3)

then Eq. (1) can also be written as

$\displaystyle
i\frac{dC_{0}(t)}{dt}={\left[-\left(w_{1}+w_{2}\right)-J\right]C_{0}(t)+\left(\frac{\Omega}{2}\cdot
e^{-i\theta_{2}}\right)C_{1}(t)+\left(\frac{\Omega}{2}\cdot
e^{-i\theta_{1}}\right)C_{2}(t)},$ $\displaystyle
i\frac{dC_{1}(t)}{dt}={\left(\frac{\Omega}{2}\cdot
e^{i\theta_{2}}\right)C_{0}(t)+\left[-(w_{1}-w_{2})+J\right]C_{1}(t)+\left(\frac{\Omega}{2}\cdot
e^{-i\theta_{1}}\right)C_{3}(t)},$ (4) $\displaystyle
i\frac{dC_{2}(t)}{dt}={\left(\frac{\Omega}{2}\cdot
e^{i\theta_{1}}\right)C_{0}(t)+\left[-(-w_{1}+w_{2})+J\right]C_{2}(t)+\left(\frac{\Omega}{2}\cdot
e^{-i\theta_{2}}\right)C_{3}(t)},$ $\displaystyle
i\frac{dC_{3}(t)}{dt}={\left(\frac{\Omega}{2}\cdot
e^{i\theta_{1}}\right)C_{1}(t)+\left(\frac{\Omega}{2}\cdot
e^{i\theta_{2}}\right)C_{2}(t)+\left[-(-w_{1}-w_{2})-J\right]C_{3}(t)}.$

\- Execution of a CNOT gate towards the future

In this case the arrow of time is taken according to the Second Law of
Thermodynamics i.e. from the past towards the future.

Given the initial conditions

$\displaystyle C_{0}(t=0)=0,$ $\displaystyle C_{1}(t=0)=0,$ (5) $\displaystyle
C_{2}(t=0)=1,$ $\displaystyle C_{3}(t=0)=0.$

It is said that the diamond quantum computer described by Eq. (1) executes a
CNOT gate in a scale of time $t=T$ ($T>0$) if

$\displaystyle\mid C_{0}(t=T)\mid^{2}=0,$ $\displaystyle\mid
C_{1}(t=T)\mid^{2}=0,$ (6) $\displaystyle\mid C_{2}(t=T)\mid^{2}=0,$
$\displaystyle\mid C_{3}(t=T)\mid^{2}=1.$

In order to verify the conservation of probability of Eq. (3) towards the
future ($t>0$), it is first solved numerically Schröedinger equation. The
results are shown in Figure 1. Together with the above, it is also verified
that a diamond quantum computer executes the CNOT gate of Eq. (6) towards the
future. The above is shown in Figures 2, 3, 4, and 5. The employed values for
the constants are $J=0.0015$, $\Omega=0.01$, $\varphi_{1}=\pi/2$,
$\varphi_{2}=\pi/4$, $w_{1}=0.2$, and $w_{2}=0.0015$.

\- Consequences of the reverse of the arrow of time on the execution of a CNOT
gate

It is said that the diamond quantum computer executes the CNOT gate towards
the past if given the initial conditions of Eq. (5) then 222It is clear that
negative times do not exist in nature. We employ mathematically this notation
as a way of expressing the reverse of the arrow of time.

$\displaystyle\mid C_{0}(t=-T)\mid^{2}=0,$ $\displaystyle\mid
C_{1}(t=-T)\mid^{2}=0,$ (7) $\displaystyle\mid C_{2}(t=-T)\mid^{2}=0,$
$\displaystyle\mid C_{3}(t=-T)\mid^{2}=1.$

By solving numerically Schröedinger equation of Eq. (4) for a negative times,
it is verified that the conservation of probability of Eq. (3) was also
preserved in the past. The respective results are shown in Figure 1. It is
also shown that the diamond quantum computer executed the CNOT gate of Eq. (7)
in the past. The above can be seen from Figures 2, 3, 4, and 5. The employed
values for the constants are $J=0.0015$, $\Omega=0.01$, $\varphi_{1}=\pi/2$,
$\varphi_{2}=\pi/4$, $w_{1}=0.2$, and $w_{2}=0.0015$.

To be one of the most promising quantum technologies for a quantum computer,
it has been considered a diamond quantum computer as the basis of our study.
It has been checked first that such a computer executes a CNOT gate with the
arrow of time taken conventionally according to the Second Law of
Thermodynamics. After that it is inverted the arrow of time and shown that the
CNOT gate was executed in the past providing this was executed towards the
future. From present findings it is predicted that if a CNOT gate is executed
towards the future then this was previously executed in the past. Such a
result might confirm the physical phenomenon of retrocausality.

Figure 1: Conservation of the probability of Eq. (3) for both cases: Towards
the future ($t>0$) and Towards the past ($t<0$). Figure 2: The coefficient
$C_{0}(t)$ satisfies the conditions of a CNOT gate of Eqs. (6) and (7) for
both cases towards the future ($t>0$) and towards the past ($t<0$). Figure 3:
The coefficient $C_{1}(t)$ satisfies the conditions of a CNOT gate of Eqs. (6)
and (7) for both cases towards the future ($t>0$) and towards the past
($t<0$). Figure 4: The coefficient $C_{2}(t)$ satisfies the conditions of a
CNOT gate of Eqs. (6) and (7) for both cases towards the future ($t>0$) and
towards the past ($t<0$). Figure 5: The coefficient $C_{3}(t)$ satisfies the
conditions of a CNOT gate of Eqs. (6) and (7) for both cases towards the
future ($t>0$) and towards the past ($t<0$).

##  Acknowledgments

We thank SNI-Conacyt grant.

## References

  * [1] G. B. Lesovik, I. A. Sadovskyy, M. V. Suslov, A. V. Lebedev, and V. M. Vinokur Sci. Rep. 9, 1 (2019).
  * [2] H. Schmidt, Foundations of Physics 8, 463 (1978).
  * [3] S. Lloyd, On the spontaneous generation of complexity in the universe in Complexity and the arrow of time, ed. C. H. Lineweaver, P. C. W. Davies, and M. Ruse (Cambridge University Press, 2013).
  * [4] E. Wigner, Nachr. Ges. Wiss. Götingen, Math. Phys., K1 1932, 546 (1932).
  * [5] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2000).
  * [6] J. Majer, I. M. Chow, I. M. Gambetta et al., Nature 449, 443 (2007).
  * [7] G. Lopez, J. Lizarraga, J. of Mod. Phys. 11, 1123 (2020).
  * [8] G. Lopez, G. LOpez, J. of Mod. Phys. 5 55 (2014).
  * [9] A. Blais, R. -Sh. Huang, A. Wallraff, et al., Phys. Rev. A 75, 032329 (2007).
  * [10] Y. Yu, S. Han, et al., Science 296, 889 (2002).
  * [11] P. Coveney, R. Highfield, The arrow of time, Ed. Ballantine Books (1992).
  * [12] F. Bonechi, E. Caleghini, R. Giachetti, E. Sorace, M. Tarlini, J. of Phys. A 25 L939 (1992).