Diffie and Hellman [1] introduced the concept of public key cryptography. Since then, several attempts have been made to provide practical public key systems. For instance, [2-4] depends on the difficulty of solving some discrete logarithm problems. Also, the Rives Shamir- Adleman (RSA) system [4] depends on the difficulty of factoring large integers.

In fact, there are three types of currently inflexible mathematical problems which are widely used in practical cryptographic schemes. They are the Integer Factorization Problem, the Discrete Logarithm Problem, and the Elliptic Curve Discrete Logarithm Problem. No polynomial time solution is known to exist [5] for these mathematical problems.

The discrete logarithm problem is frequently used in public-key cryptosystems to provide security. Considering working with the real numbers,log_by  is the value x, such that b^x=y. Given integers b and n, with b<n, the discrete logarithm of an integer y to the base b is an integer x, such that: 

b^x=y mod n

The discrete logarithm is also called index, and so:

x=ind_b,n,y

While it is quite efficient to raise numbers to large powers modulo p, the inverse computation of the discrete logarithm is much harder [6]. The ElGamal system relies on the difficulty of this computation. It is well known that this progress in the discrete logarithm problem forces the users of the basic ElGamal public key cryptosystem, working in a multiplicative group of GF(p), to permanently increase a prime modulus p in order to ensure the desired security. 

The power of the security of these cryptosystems is based on algorithmic complexity. That is, it is difficult in practice to deduce the secret key from the public key in a reasonable delay. Nothing proves however that this security is not compromised in a near future because there is an accelerated evolution of the software and the specific hardware. So, many cryptographic schemes in use today would be broken with either unanticipated advances in hardware and algorithm or the advent of quantum computers.

In addition, Key distribution is the strength of any cryptographic system as the security of any communication is totally depends on the secret key. Therefore, it is important to have secure key distribution system because if the key get compromised then whole system will get compromised. Classical cryptography is based on a combination of guess work and mathematics. Security depends on the difficulty of computational complexity which is not enough as the fast growing methods to calculate the secret key that will compromise the security.

Another solution to these problems in cryptography now consists of using the laws of the quantum physics. It is precisely involves the use of Quantum Cryptography protocols in order to carry out a task of exchanging keys with a great security. Quantum Cryptography has been proven secure even against the most general attack allowed by the laws of physics and is a promising technology for adoption in realistic cryptographic applications.

This research proposed an Elgamal cryptographic scheme based on Quantum key distribution (QKD). Instead of Diffie-Hellman key exchange initially employed by Elgamal, QKD is used. The QKD is used to generate and distribute the quantum key to be used by the receiver (Fatima) to encrypt the public key to be sent to sender (Abubakar) using Blowfish algorithm. This public key is used in the encrypt of the message M that will be sent to the receiver (Fatima). The security of the proposed system is also discussed in section IV of this research.

Related Works

Cryptography has been around for several centuries as complex algorithms, which are based on either exchanging of characters or use of complex mathematical functions. Nowadays, the classical cryptography is the most used in a security system that depends upon public and private keys, which are initiated into difficult algorithms such as RSA [4], El-Gamal [7], etc. All these scenarios have been proving to be secure. But will no longer be secure if the scientists reached to establish quantum computer that will break all the previous algorithms just in seconds. As such, many of the computer scientists and physicians have been working on how to create a secret key in a quantum system. This is the so-called Quantum Key Distribution [8-9]. The first QKD protocol was announced in 1984 by Bennett and Brassard which is still the background point to come up with a new quantum protocol scheme [10]. A lot of researches have been conducted on the field of QKD and Elgamal which are going to be discussed in the remaining part of this section.

Mink in [11] present an overview of quantum key distribution, a secure key exchange method based on the quantum laws of physics rather than computational complexity. They consider two most widely used commodity security protocols, Internet Protocol Security (IPsec) and Transport Layer Security (TLS). Pursuing a key exchange model, they propose how QKD could be integrated into these security applications. For such a QKD integration they propose a support layer that provides a set of common QKD services between the QKD protocol and the security applications. 

Ahmed in [12] implements quantum cryptography in wireless communication systems using a quantum key distribution protocol which is named as SARG04. The protocol implemented on wireless LAN. They have found that IEEE 802.11 family (Wi-Fi) suits best to get married with QKD, the environmental changes impacting quantum missions in Wi-Fi networks can be minimized as the standard area is very small. The general communication of this new protocol takes two channels: wireless channel (Wi-Fi) and Quantum channel.

Charjan and Kulkarni in [13] proposes a QKD system by exploiting public key cryptography in a resource constrained devices. The public key cryptosystem used is elliptic curve cryptography (ECC). They design an algorithm to authenticate the user in QKD without using classical channel. With the use of Public Key Cryptography with ECC it reduces the usage of resources in resource constrained devices and also overcome the overhead caused due to number of rounds required to measure the correct bases and final key. Simulation results are generated by implementing proposed system in Java, which shows the comparison between Rivest, Shamis and Adleman (RSA) and ECC by exploitation in the proposed system using different parameters that are key generation time, key encryption time, key decryption time. The results prove that time required for system to execute using ECC is very less than RSA, so the power consumption is less for computation of key. The proposed algorithm distributes the quantum base before communication start between two parties, the overhead is removed that is caused due to the amount of rounds needed to induce the error free key.

Arboleda in [14] combine two existing encryption schemes to propose an enhanced secure and fast chaotic cryptographic scheme. The existing encryption schemes are secure and fast chaotic, and Elgamal cryptosystems. The production of different cipher text for the same plain text by the secure and fast chaotic cryptography is combined with the power of Elgamal cryptography. 

Asri in [15] proposed the application of split merge method on the Elgamal algorithm to improve its security. It makes it very difficult for an attacker to break the plain text because the combination uses large prime number calculations.

Fang in [16] designed an improve Elgamal digital signature algorithm by increasing the number of random number and introduction of Hash function. The inverse modular operation is reduced by adding auxiliary equations.

Elgamal Cryptography 

Elgamal is an asymmetric key algorithm developed by Taher Elgamal in the year 1984. It is based on Diffie-Hellman key exchange algorithm [17] and works over finite fields [18]. The security of this algorithm is based on Discrete Logarithm Problem (DLP). El Gamal depends on the one way function. This means that the encryption and decryption are done in separate functions.

In ElGamal, only the receiver needs to create a key in advance and publish it [19]. Key generation, encryption and decryption can be discussed as follows [19]:

Key Generator

Bob will take the following steps to generate his key-pair:

• Prime and Group Generation: First, Bob needs to select a large prime p and the generator g of a multiplicative group Z_p of the integers modulo p

• Private Key Selection: Now Bob selects an integer b from the group Z by random and with the constraint 1< b < p-2

• Public Key Assembling: Now, the public key part g^b mod p can be calculated. In ElGamal Cryptosystem, the public key of Bob is the triplet (p,g,g^b) and his private key is b

• Public Key Publishing: Bob has to give the public key to Alice 

Encryption

To encrypt a message M to Bob, Alice first needs to obtain his public key triplet (p,g,g^b) from a key server or by receiving it from him via unencrypted electronic mail. There is no security issue involved in this transmission, as the only secret part,b, is sent in g^b. This is safe because the core assumption of the ElGamal cryptosystem says that it is infeasible to compute the discrete logarithm. For the encryption of the plaintext message M, Alice has to follow these steps:

• Obtain the Public Key: As explain, Alice has to acquire the public key part (p,g,g^b) of Bob from an official and trusted key-server

• Prepare M for Encoding: Write M as set of integers (m₁,m₂...) in the range of1,2,....,p-1. These integers will be encoded one by one

• Select Random Exponent: In this step, Alice will select a random exponent k that takes the place of the second party's private exponent in the Diffe-Hellman key exchange. The randomness here is a crucial factor as the possibility to guess the k gives a sensible amount of the information necessary to decrypt the message to the attacker

• Compute Public Key: To transmit the random exponent k to Bob, Alice computes g^k and combines it with the ciphertext that shall be sent to Bob

• Encrypt the Plain Text: In this step, Alice encrypts the message M to the cipher-text C. For this, she iterates over the set created in step b and calculates for each of the m_i:

The cipher-text C is the set of all c_i with 0<i<∣M∣.

The resulting encrypted message C is sent to Bob together with the public key g^kderived from the random private exponent.

Even if an attacker would listen to this transmission, and in a second step would also acquire the public key part g^b of Bob from a key-server, he would still not be able to derive g^b*k as can be seen from the Discrete Logarithm problem.

Elgamal advises to use a new random k for each of the single message blocks m_i.This greatly improves security, as knowledge of one message block m_j does not lead the attacker to the knowledge of all otherm_i. The reason for this ability is that if 

c_{1 =} m₁ *(g^b)^k mod p and c₂ = m₂ * (g^b)^k mod p, fromknowing only m₁

the next part of the message m₂ can be calculated by the following formula:

Decryption

After receiving the encrypted message C and the randomized public key g^k, Bob has to use the encryption algorithm to be able to read the plaintext M. This algorithm can be divided in a few single steps:

• Compute Shared Key: The El Gamal cryptosystem helped Alice to define a shared secret key without Bob's interaction. This shared secret is the combination of Bob’s private exponent  b and the random exponent k chosen by Alice. The shared key is defined by the following equation:

• Decryption: For each of the cipher-text parts c_i Bob now computes the plaintext using:

After combining all of the m_i back to M he can read the message sent by Alice.

Quantum Key Distribution

Quantum Key Distribution (QKD) [8-9] is a technology, based on the quantum laws of physics, rather than the assumed computational complexity of mathematical problems, to generate and distribute provably secure cipher keys over unsecured channels. The basic model for QKD protocols involves two parties, referred to as Alice and Bob, wishing to exchange a key both with access to a classical public communication channel and a quantum communication channel. This can be shown in Figure 1. The QKD protocol to be used in this research is Benett and Brassard [10] (BB84) protocol.

BB84 is the protocol most widely used for quantum key distribution [10]. It allows two users to establish an identical and purely random sequence of bits at two different locations while allowing revealing any eavesdropping. 

Figure 1: QKD Model [20]

In BB84 protocol, Alice and Bob use a quantum channel to send qubits. They are also connected by a classical channel, which is insecure against an eavesdropper but unjammable. Alice and Bob use four possible quantum states in two conjugate bases (say, the rectilinear basis and the diagonal basis x). We use:

for the classical signal “0,” and we use:

for the classical signal “1.” Note that the two bases are connected by the so-called Hadamard transformation:

The protocol works as follows [4]:

• Alice randomly prepares 2n qubits, each in one of the four states ∣0⟩+​,∣0⟩×​,∣1⟩+​,∣1⟩×​, and sends them to Bob

• For each qubit that Bob receives, he chooses at random one of the two bases (+ or ×) and measures the qubit with respect to that basis. In the case of a perfectly noiseless channel, if Bob chooses the same basis as Alice, his measurement result is the same as the classical bit that Alice prepared. If the bases differ, Bob’s result is completely random

• Alice tells Bob via the classical channel which basis she used for each qubit. They keep the bits where Bob has used the same basis for his measurement as Alice. This happens in about half the cases, so they will have approximately n bits left. These are forming the so-called sifted key

• Alice and Bob choose a subset of the sifted key to estimate the error-rate. They do so by announcing publicly the bit values of the subset. If they differ in too many cases, they abort the protocol, since its security cannot be guaranteed

• Finally, Alice and Bob obtain a joint secret key from the remaining bits by performing error correction and privacy amplification. This can be shown in Table 1

If an eavesdropper is present, even with infinite computa­tional power, the best he could do in an ideal system would be to intercept transmissions from Alice, randomly select a basis for measurement, and retransmit those qubits in the basis that he selected. Since an eavesdropper does not know the basis Alice transmitted in, he would be correct on average only 50% of the time. When he retransmits the qubits, Bob will also select a random basis for measurement and will be correct on average 50% of the time. The combination of these steps will introduce a 25% error into the sifted key. There­fore, if Alice and Bob detect an error rate of 25% or higher in their sifted key, they conclude that there is an eavesdropper present and abandon the key exchange process. This is the basis for the unconditional security that the BB84 QKD pro­tocol achieves because Alice and Bob can always detect the presence of an eavesdropper.

Proposed Elgamal Cryptographic Scheme

Public-key cryptosystems like Elgamal help to solve the key distribution problem by using separate keys for encryption and decryption, and making the encryption key public because key distribution is the strength of any cryptographic system as the security of any communication is totally depends on the secret key. Since security of classical cryptography depends on the difficulty of computational complexity and this is not enough as the fast growing methods to calculate the secret key that will compromise the security. As such, another solution to this problem in cryptography now consists of using QKD that uses the laws of the quantum physics. This is what makes us to propose an improved Elgamal cryptosystem by replacing Diffie-Hellman key exchange with QKD.

Architecture of the Proposed Elgamal Cryptosystem

The proposed Elgamal cryptosystem based on QKD consist four stages. These are: key generation, quantum key distribution and public key encryption, encryption and decryption. The architecture can be shown in Figure 2.

Although r is computed using Abubakar’s private key b and if g^b , g and p are made public as in the initial elgamal cryptosystem, the Abubakar’s private key requires the use of an algorithm which solve discrete logarithm problem. In the proposed Elgamal cryptographic scheme the public key  (p,g,g^b) is to be encrypted using quantum key and shared using QKD.

Stage 2: Quantum Key Distribution and Public Key Encryption

This stage consists of two phases: quantum key distribution and Public key encryption.

The string of bits remaining in d once the bits disclosed in step (V) are removed is the common secret key, k = {0,1}^N (the final key)

Public Key Encryption

The Abubakar’s public key (p,g,g^b) is encrypted using private key cryptographic algorithm called Blowfish. The public key (p,g,g^b) can be denoted by PK. Blowfish is a 64-bit symmetric block cipher with variable length key. The algorithm operates with two parts: a key expansion part and a data encryption part. The role of key expansion part is to converts a key of at most 448 bits into several sub key arrays totaling 4168 bytes. The data encryption occurs via a 16-round Feistel network [19]. Each round consists of a key dependent permutation, and a key- and data-dependent substitution. 

In this research the key is the quantum key (QK) K = {0,1}^N  generated. All operations are XORs and additions on 32-bit words. The only additional operations are four indexed array data lookups per round.

Blowfish uses a large number of subkeys. These keys must be pre-computed before any data encryption or decryption. The algorithm is described below:

• The QK-array consists of 18 32-bit subkeys:

• There are four 32-bit S-boxes with 256 entries each:

• Encryption: As mentioned earlier Blowfish is a Feistel network consisting of 16 rounds. The input is a 64-bit data element, PK

Divide PK into two 32-bit halves: PK_L , PK_R

for i = 1 to 16:

Swap PK_L and PK_R

Swap PK_L and PK_R (Undo the last Swap)

Recombine PK_L and PK_R

Function F Divide PK_L into four eight-bit quarters: a, b, c, and d

• Stage 3: Encryption: Encryption for the proposed Elgamal cryptosystem is performed in five steps as follows:

• Obtain the public key (p,g,g^b) of Abubakar. This can obtained by decrypting the public key encrypted using QKD as follows:

• The input is a 64-bit data element, C(PK).

• Divide PK into two 32-bit halves: 

for i = 18 downto 3:

Function F Divide C(PK)_L into four eight-bit quarters: a, b, c, and d

• Write M as set of integers (m1,m2,...) in the range of 1,2,...,p-1. These integers will be encoded one by one

• Choose a random integer k  , known as an ephemeral key, such that 1< k < p - 1 . This is the private key of Abubakar

• Compute public key

• Compute d_i = m_{i *} (g^b) for each of m_i. Here the message M is encrypted

Once these calculations are complete, then Fatima sends the 2-tuple ( c ,d ) to Abubakar as the cipher-text.

Stage 4: Decryption

Upon receipt of a cipher-text, Abubakar performs the following two steps to recover the original plaintext. But the send public key

• Abubakar uses his private key, b, to compute 

• For each of the cipher-text parts d_i Abubakar now computes the plaintext using

Security of the Proposed Elgamal Cryptographic Scheme 

The security of ElGamal depends on the feasibility of calculating the discrete logarithm. Anyone who is able to compute discrete logarithms can deduce the private ElGamal key from the public one simply by computing log_gb. Thus it is very difficult for an intruder to compute the public key b from g^b mod p. Hence, there is no known method for solving a discrete log problem with a large prime modulus that is sufficiently efficient.

Though, the first possible solution to the key distribution problem is public key cryptography like Elgamal. However, the security of Elgamal is based on unproven computational assumptions as shown in the proposed scheme. Therefore, public key distribution is vulnerable to unanticipated advances in hardware and algorithms. In fact, cryptography relies on the sharing of secret keys between communicating parties, typically named Fatima and Abubakar. One of the major loopholes in classical cryptography is that, in principle, it is always possible to intercept the distribution of the cryptographic key un-noticedly.

Quantum mechanics now provide a solution to the key distribution problem. In quantum key distribution, an encryption key is generated randomly between Fatima and Abubakar by using non-orthogonal quantum states. It is generally based on the impossibility to observe a quantum mechanical system without changing its state. An adversary trying to wiretap the quantum communication between Fatima and Abubakar would thus inevitably leave traces which can be detected.

A big advantage of quantum cryptography is forward security. In conventional cryptography, an eavesdropper Atika has a transcript of all communications. Therefore, she can simply save it for many years and wait for breakthroughs such as the discovery of a new algorithm or new hardware. In contrast, quantum cryptography guarantees forward security.

This research replaces the Diffie-Helman key exchange initially employed by Elgmal with Quantum key distribution. Therefore, the proposed system will have but eliminate key distribution problem of Elgamal public key distribution at the same time having the power of discrete logarithm problem.

This research replaced the Diffie-Hellman key exchange initially employed by Elgamal with QKD. The QKD is used to generate and distribute the quantum key to be used by the receiver (Abubakar) to encrypt the public key that is to be sent to sender (Fatima) using Blowfish algorithm. The Quantum Key (QK) is also the key to be used by Blowfish to decrypt the public key that is going to be used in the encryption of the message M using Elgamal. The security of the proposed system is also discussed in section IV of this research. There is going to be a performance overhead because of the addition encryption and decryption of the public key using Blowfish private key algorithm. This additional performance is caused by the double encryption and encryption that happened in the proposed Elgamal scheme. Even though the private key cryptography is more efficient than public key cryptography but it will still increase the performance time of the proposed Elgamal cryptographic scheme compared to the initial Elgamal scheme. The Quantum key is going to be used during the symmetric encryption and decryption of the public key. 

This research can be extended to use biometric template for the generation of keys. Also, S13 quantum key distribution can be used instead of BB84. So, both secrete and public key can be generated and distributed using S13 quantum key distribution without need for additional encryption and decryption of public key using symmetric cryptography. Lastly, appropriate security verification tools and performance evaluation techniques can be employed to further analyze both its security and efficiency.

1. Diffie, W. and Hellman, M. “New directions in cryptography.” IEEE Transactions on Information Theory, vol. 22, no. 6, 1976, pp. 644-654.

2. Ong, H. and Schnorr, C.P. “Signatures through approximate representations by quadratic forms.” Advances in Cryptology, Springer US, 1984, pp. 117-131.

3. Ong, H. Schnorr, C.P. and Shamir, A. “An efficient signature scheme based on quadratic equations.” Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, ACM, December 1984, pp. 208-216.

4. Rivest, R.L. etal. “A method for obtaining digital signatures and public-key cryptosystems.” Communications of the ACM, vol. 21, no. 2, 1978, pp. 120-126.

5. Nichols, R.K. ICSA Guide to Cryptography. McGraw-Hill Professional, 1998.

6. LaMacchia, B.A. and Odlyzko, A.M. “Computation of discrete logarithms in prime fields.” Designs, Codes and Cryptography, vol. 1, no. 1, 1991, pp. 47-62.

7. ElGamal, T. “A public key cryptosystem and a signature scheme based on discrete logarithms.” Workshop on the Theory and Application of Cryptographic Techniques, August 1984, pp. 10-18. Springer Berlin Heidelberg.

8. Gisin, N. et al. “Quantum cryptography.” Reviews of Modern Physics, vol. 74, no. 1, 2002, pp. 145.

9. Chou, C.W. Laurat, J. et al. “Functional quantum nodes for entanglement distribution over scalable quantum networks.” Science, vol. 316, no. 5829, 2007, pp. 1316-1320.

10. Bennett, C.H. and Brassard, G. “Quantum cryptography: public key distribution and coin tossing.” Conference on Computers, Systems and Signal Processing (Bangalore, India, December 1984), 1984, pp. 175-179.

11. Mink, A. et al. “Quantum key distribution (QKD) and commodity security protocols: introduction and integration.” arXiv preprint, arXiv:1004.0605, 2010.

12. Ahmed, J. et al. “Quantum cryptography implementation in wireless networks.” International Journal of Science and Research, 2014, pp. 129-133.

13. Charjan, S. and Kulkarni, D.H. “Quantum key distribution by exploitation public key cryptography (ECC) in resource constrained devices.” International Journal, vol. 5, 2015.

14. Arboleda, E.R. “Secure and fast chaotic El Gamal cryptosystem.” International Journal of Engineering and Advanced Technology, vol. 8, no. 5, 2019, pp. 1693-1699.

15. Asri, R. et al. “Modification of ciphertext ElGamal algorithm using split merge.” Journal of Physics: Conference Series, vol. 1235, no. 1, June 2019, p. 012054. IOP Publishing.

16. Fang, Y. et al. “Research and design of an improved ElGamal digital signature algorithm.” IOP Conference Series: Materials Science and Engineering, vol. 569, no. 5, July 2019, p. 052041. IOP Publishing.

17. Al Hasib, A. and Haque, A.A.M.M. “A comparative study of the performance and security issues of AES and RSA cryptography.” Convergence and Hybrid Information Technology (ICCIT'08): Third International Conference on, vol. 2, 2008, pp. 505-510. IEEE.

18. Singh, R. and Kumar, S. “Elgamal’s algorithm in cryptography.” International Journal of Scientific & Engineering Research, vol. 3, no. 12, 2012, pp. 1-4.

19. Grewal, J.K. ElGamal: Public-Key Cryptosystem. Unpublished Master’s Thesis, Indiana State University, Terre Haute, IN, USA, 2015.

20. Haitjema, M. “A survey of the prominent quantum key distribution protocols.” 2007.