A Post-Quantum Authenticated Key Agreement Scheme
Abstract
We know that photons are basis of Quantum computers. These computers with fiber optic–based telecommunication infrastructures will make a suitable networks. Despite such powerful computers and networks, existing cryptographic systems quickly lose their security. Therefore we have to design several new cryptographic algorithms against the quantum computer attacks. In this paper, we present a new suitable scheme for key exchange in a post-quantum cryptography. Our protocol is quantum-resistant public key cryptosystems and based on super-singular isogeny Diffie-Hellman (SIDH).
Keywords: Quantum Computers, Photon, Cryptographic Algorithms, Super-singular Isogeny Diffie-Hellman (SIDH).
1. Introduction
The computers we have, use ordinary silicon chips, which we call classic computers. Scientists are researching to build high-performance computers. They have succeeded in inventing quantum photonic chips by manipulating the silicon photons of chips to create quantum computers.
Photon is a type of elementary particle. The new photon idea originated during the first two decades of the 20th century with the work of Albert Einstein [1]. “Photonic Computing” benefit photons manufactured by lasers or photonic processor for calculation. As mentioned above, to build quantum computers, scientists have used the properties of photons to create powerful computers. Quantum computers carry out computations based on the probability of an object’s state before it is measured.
Despite the mentioned processing power, the public key cryptographic algorithms, such as ordinary ECC and RSA, are no longer efficient and quickly lose their security against quantum computers. Therefore, we must look for methods that are resistant to the quantum computer attacks and can be a good alternative to current cryptographic algorithms. As Institute of Standards and Technology (NIST) said [2].
Until now numerous schemes were presented that they can be classified into five categories: lattice based algorithms, code based algorithms, multivariate equation based algorithms, hash based algorithms and Super-singular Isogeny Key Exchange algorithm (SIKE).
A good post-quantum cryptographic algorithm must be able to resist the classical computer and quantum computer attacks. Based on the information we already have for building this efficient algorithm, we can use symmetric cryptosystem, public key encryption as a key exchange, Diffie-Hellman (DH) key exchange or elliptic-curve Diffie–Hellman (ECDH). One of the reasons we chose DH-based as main part of our scheme that is DH has an advantage over other one for producing ephemeral keys: producing a new DH key pair is extremely fast.
Between the NIST schemes, there is one that resembles Diffie-Hellman schemes: super-singular isogeny Key Exchange (SIKE). SIKE which is based on Super-singular isogeny Diffie–Hellman key exchange SIDH. Using super-singular isogeny (SI) based cryptosystem is easier than other post-quantum algorithms. Among all the post-quantum public key crypto systems, SIKE has the smallest key size. To provide 124 bit security, the public key size of SIKE is 564 bytes only [3].
The paper is structured as follows. In Section 2 we provide an overview of ordinary ECC and ECDH and express its weaknesses against the quantum computer attacks. In the following of this section, we will state the super-singular isogeny key exchange cryptography that will be the basis of our original design. In Section 3, we present our design as a post-quantum authenticated key agreement system. In Section 4, software analysis of proposed scheme will be done and it will be checked that this plan has good security features against the quantum and classical computers attacks and finally a conclusion will be made.
2. Preliminaries
In this section, we want to present a summary of ordinary ECC and SIDH so that we can use them in our design.
2.1. Elliptic Curve Cryptography
Elliptic-curve-based protocols, the base assumption is that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is infeasible: this is the “elliptic curve discrete logarithm problem” (ECDLP). Elliptic Curve Cryptography (ECC) developed as an alternative to RSA encryption. The idea of using elliptic curves for a new type of cryptosystem first proposed in 1985 by Neal Koblitz and Victor Miller. The Elliptic Curve Cryptosystem has a high-level security between public key schemes. In the other hand elliptic curve encryption requires a smaller key size than other public key encryption methods for the same level of security. In fact, it can be said that the elliptic curve cryptography requires smaller numbers to produce a common secret key between two parties participating in a relationship. ECC computation constructed on finite fields, which can either choose a prime field or a binary field. Point addition is the fundamental arithmetic of ECC and the basic operations of scalar point multiplication Q = kP, where k ∈ Z, point Q,P ∈ E(Fq), Fq is a prime finite field.
An elliptic curve is a cubic equation of the form E: y2 + a1xy + a2y = x3 + a3x2 + a4x + a5. Where, a1, a2, a3, a4 and a5 are real numbers. The singular elliptic curve can be of the form Ep(m, n): y2 = x3 + ax + b (mod p) over a prime finite field Fp, where a, b ∈ Fp, p > 3, and 4a3+ 27b2≠0 (mod p). We can see the singular elliptic curve in figure1.
The security of elliptic curve cryptography depends on the inability of the attacker to calculate the desired point according to the multiplicative player at his disposal. The size of the elliptic curve determines the difficulty of the problem.
Several discrete logarithm-based protocols have been adapted to elliptic curves but we demonstrate two important problems here.
Problem 1: Let E be an elliptic curve defined over a finite field Fq. P and Q be points in E(Fq), and suppose that P has prime order n, assuming that Q = dP, where d is an integer from the interval [1, n-1]. The problem of determining d given the domain parameters and Q is the elliptic curve discrete logarithm problem (ECDLP).
Problem 2: The elliptic curve Diffie-Hellman problem (ECDHP) is: given an elliptic curve E defined over a finite field Fq, a point P ∈ E(Fq) of order n, and points A = aP, B = bP ∈<P>, find the point C = abP [4].
2.2. DH & ECDH
In this section, we briefly describe the Diffie-Hellman (DH) and elliptic curve Diffie-Hellman (ECDH).
2.2.1. Diffie-Hellman (DH)
The Diffie–Hellman problem (DHP) is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography.
For x ∈(Z/pZ)× the function x →rx is easy to compute but hard to invert. Here the exponent x is secret; the base r ((ra,rb) →rab) and modulus p are public. The inverse of the function x →rx is the discrete logarithm y →logry [5].
2.2.2. Elliptic curve Diffie-Hellman (ECDH)
Elliptic-curve Diffie–Hellman (ECDH) is a key exchange protocol that allows two section to establish a shared secret over an unsure channel. This value shared between the two parties can be used in two ways: direct and indirect. From this key and in the next step using symmetric encryption such as AES can be used to encrypt the desired information. It is a variant of the Diffie–Hellman protocol using elliptic-curve cryptography [6].
One of the parties (A) chooses a random ra∈[1,p] and sends raP=P +···+P to other party (B). B chooses a random rb ∈[1,p] and sends rbP to A. A authenticates rbP and computes ra.rb.P and B computes rb.ra.P.
E/Fp and point P ∈E(Fp) are public. ECDH is used in important parts of the Internet. One of its most important uses is in TLS.
2.3. Advantages and disadvantages of ECC-based protocol
We demonstrate advantages and disadvantages of practical using from ECC-based protocol and state that why we must use a new framework for our designing.
2.3.1. Advantages
Important advantages for ECC and ECDH can be considered, the most important of which is that for the same level of security ECC and ECDH requires less key size. The ordinary ECC key size of 256 bits is equivalent to a 3072-bit RSA key. We show that advantages of ECC in comparison with RSA in table1. The second advantage of ECC over RSA is again their key size. It can be said that because ECC has a smaller key size, it requires less memory to store the key than the other public key encryption methods. On the other hand, it has less processing power than RSA.
2.3.2. Disadvantages
Due to the high processing power mentioned in the previous sections, quantum computers can solve mathematical problems easily that classical computers cannot solve them. Unfortunately, this concepts includes many mathematical hard problems which form the basis of several existing public key cryptographic algorithms. In other words, Ordinary ECC and ECDH will be easily broken by quantum computers, which will have an important impact on current communications and network security.
With the presence of quantum computers, the side-channel attacks are convenient on the ordinary ECC-based protocol. Therefore we must change our designing to modern one [7].
Super-singular Isogeny Diffie–Hellman (SIDH) Key Exchange provides a post-quantum secure is formed of elliptic curve cryptography by using isogenies to implement Diffie–Hellman key exchanges. SIKE takes advantage of ECC and new features to improve public key cryptography schemes. In the next part, we will demonstrate the basic concepts needed to design a post-quantum authenticated key agreement protocol.
2.4. Super-singular Isogeny Diffie–Hellman (SIDH)
As mentioned above, quantum computers, given their processing power, can easily destroy the security of existing public key cryptographic algorithms and reveal their basic information, which must be kept secret. For these reasons we describe Super-singular Isogeny Diffie–Hellman for key agreement.
Super-singular Isogeny Diffie–Hellman (SIDH) was created in 2011 by De Feo, Jao, and Plut [8]. It uses conventional elliptic curve operations. SIDH provides perfect forward secrecy. Forward secrecy improves the long-term security of encrypted communications.
We are interested in the set of super-singular curves (up to isomorphism) over a specific field and the public keys defined in form of: PK = (E,P,Q), The public keys of SIDH consist of the codomain of a secret isogeny and the image points of certain public points under that isogeny, and E/Fp2 : y2 = x3 + ax + b is a super-singular elliptic curve, p = 2eA .3eB ±1 is a large prime, the cardinality of E is #E(Fp2) = (p∓1)2 , j(E)=1728 *(4a3/ ( 4a3 +27b2) ∈k and super-singular j-invariants: #SP2=|P/12| .
Elliptic curves with the identical j-invariant are isomorphic over a finite extension of k, and have isomorphic endomorphism rings End(E). It thus makes sense to refer to j-invariants as ordinary or super-singular.
A morphism ϕ: E1 →E2 is a map defined by a specific function that sends the distinguished point of E1 to the distinguished point of E2. Finding ϕ in isogeny-based protocol is a hard problem for adversary. Morphisms that are not the zero map are called isogenies. The kernel of the isogeny is R=ker(ϕ)=<Pi +[Si]Qi> where Pi and Qi are public key and Si is secret key of parties [9].
We want to show isogeny walks on the graphs. Therefore we must firstly get isogeny kernel [le-i-1]Ri, we perform these steps:
a. Compute isogenies ϕi =Ei / <[le-i-1]Ri>.
b. Compute Ei+1 = ϕi (Ei).
c. Push points to new curve Ri+1 = ϕi (Ri). We show the isogeny walks in figure3.
In the following, we want to demonstrate the SIDH protocol based on the contents mentioned. Alice first selects a random number nA ∈ Z/lA eA Z and obtains the mapping function according to the following equation. Also Alice obtains the images of P and Q points under ϕA (ϕ (PB), ϕ (QB)).
ϕA: E0 →EA = E/ <PA + [nA]QA>, where PA and QA are public A’s parameters.
Bob selects a random number nB ∈ Z/lB eB Z and obtains the mapping function Ψ=ϕB: E0 →EB = E/ <PA + [nB]QA> and Bob obtains the images of P and Q points under ϕB (Ψ (PA), Ψ (QA)).
Alice send the {A, ϕ (PB), ϕ (QB ), EA } to Bob and Bob also sends the message {B, Ψ (PA), Ψ (QA), EB}.
After receiving the above messages, the parties computes j(EAB) to find the common key. Figure 4 shows the summary of SIDH (10).
Alice: j(EBA)= EB / Ψ (PA) +[ nA] Ψ (QA)
&
Bob: j(EAB)= EA / ϕ (PB) +[ nB] ϕ (QB)
K := j-inv(EAB)=j-inv(EBA)
In the table below, we describe the private values and show the hard problem for DH, ECDH and SIDH.
In the original SIDH, we face a challenge to implement with existing APIs. It is expensive to implement with existing IT (11). Due to network implementation delays, using MAC is one of the most appropriate ways to implement better with a lower cost. Therefore we will propose a new scheme that has suitable features.
3. Proposed protocol
We use the concepts mentioned in the previous sections to design a key agreement protocol that is resistant to quantum computer attacks. In addition, our scheme does not have the problem of costly implementation with existing infrastructure. We also claim that our scheme has important security features that a key agreement protocol should have. In Table 3, we describe the symbols used in our Authentication Protocol.
Alice and Bob have already shared a secure amount, PW, that contains some of their secret information. Alice chooses a random number nA ∈ Z/lA eA Z and computes ϕA, it’s kernel (ker(ϕA)=(PA + [nA]QA)) and EA=E0 / ker (ϕA). Alice also gets the image of Bob’s point ((ϕA (PB), ϕA (QB)). In the following, Alice computes the key, K0= H (PW + A + B), and prepares the message {EA, ϕA (PB), ϕA (QB), A, B, MACK0 (EA, ϕA (PB), ϕA (QB), A, B) } for sending to Bob.
Bob at the same time, chooses a random number nB ∈ Z/lB eB Z and computes the parameter, ϕB, it’s kernel (ker(ϕB)=(PB + [nB]QB)) and EB=E0 / ker (ϕB). The image of Alice’s point (ϕB (PA), ϕB (QA)). After receiving the message, Bob first forms the K0 and then checks the integrity of the message with checking MACK0. If the conditions are right, Alice will be authenticated to Bob and Bob prepares PKB={EB, ϕB (PA), ϕB (QA)}.
In the following, Bob prepares EAB= EA / ϕA (PB) + [nB] ϕA (QB) and computes the key, K1= H (j (EAB) + PW + A+ B). Finally Bob prepares the message {EB, ϕB (PA), ϕB (QA), B, MACK1 (EB, ϕB (PA), ϕB (QA), B)} to send to Alice.
After receiving the message, Alice prepares EBA= EB / ϕB (PA) + [nA]ϕB (QA) and computes K1'= H(j(EBA) + PW + A + B) and MACK1'. Then Bob checks MACK1' ?= MACK1. If the conditions are ok, Bob will be authenticated to Alice.
Finally Alice and Bob can form the shared key as below.
SK= H (H (j(EAB) + PKA + PKB + A + B)). You can see the summary of the proposed scheme in Figure 5. It should be noted that the value of PW is updated for each running.
4. Analysis
In this section, we first demonstrate the security features of the proposed scheme and then present the results of the software analysis.
4.1. Security features
a. Mutual authentication
Mutual authentication in this protocol occurs. All two sides will be authenticated. Alice authenticates Bob by checking the K1 and MACK1. Because there is their secret parameter in PW. On the other hand Bob can authenticate Alice by checking K0 and MACK0.
b. Anonymity
In the proposed protocol, we have complete anonymity. Because of using one-way hash function, all of the parties are unrecognizable.
c. Forward/Backward secrecy
This scheme has forward / backward secrecy. A process will have forward and backward security of session key, if getting a session key, does not affect the security of the previous and the next keys. The proposed authentication scheme has forward secrecy because our protocol uses random numbers and PW that they will be updated in each round, we have used the one-way hash function in the session key and we have not sent the session key directly.
d. Known session key attack
In our authentication scheme, the session is based on SIDH, and the key of this session is a short key, so known session key attack will not work on this protocol.
e. Resistant to man-in-the-middle attack
This attack can’t be implemented because the proposed scheme provides mutual authentication between all participating members.
f. Side channel attack
An attacker can access to the important information by eavesdropping and monitoring the traffic of messages exchanged between the parties and monitoring the power consumption for implementation. The achieved information can be used to recover the secret key. These kinds of attacks are known as side-channel attacks. Side channel attack can be done in different ways. For example, by placing the antenna near the sensors of a network, the information mentioned above can be achieved.
Side channel attacks can occur on ECC in a variety of ways, one of them is the unintended leakage of important information. But for isogeny-based schemes, our proposed scheme, a secret isogeny can’t be computed easily. Because we know that a secret isogeny can be computed for the other party’s basis points. Therefore SIDH-based protocols are resistant to side-channel attack.
g. Non-repudiation
Non-repudiation of the parties is one of the issues that should be considered in security protocols. This means that none of them should ignore receiving and sending messages. In proposed scheme, because MAC is used, it allows the parties to make sure that the other party is true.
4.2. Software analysis
It is difficult to analyze the security protocols by humans, because human mind can’t consider all attack scenarios. In order to we usually look for software that makes it easy for us. One of these software is SKYTHER. The advantage of SKYTHE over other software is that it does not need to define a scenario for the application, while SKYTHER considers all different modes of attack on a protocol (12). The simulation results are shown in table4. Some of the security features of this software are as follows:
Alive: One kind of authentication is to create a communication partner that it will claim the other party is alive. This proves that the existence of a two-way authentication.
Niagree: An authentication type that claims the sender and receiver of the message agree on the exchanged values, and that no information was received by an attacker.
WeakAgree: This feature means that there is a strong authentication, which the receiver is sure that all messages received from the sender are valid.
Nisynch: This feature indicates that the parties are certain this message was sent only by the authenticated person.
Secret x: This feature means that the parameters of this protocol have not been manipulated by an attacker.
We also introduce a summary of aspects of SIDH and ECC cryptography in table.5.
5. Conclusion
In this article, we first summarize the construction of quantum computers and photons. Then we demonstrate how existing public key cryptographic algorithms easily lose their security against quantum computer attacks.
Next, we introduce the isogeny-based key agreement protocols and present an isogeny-based key agreement protocol that has good security features.
If you find this article helpful please follow our Medium account and share this page with your friends to improve the SEO of our article.
References:
[1] Joos, George. “Theoretical Physics”. London and Glasgow: Blackie and Son Limited. p. 679, 1951.
[2] The National Institute of Standards and Technology (NIST). Post-quantum cryptography standardization, 2017–2018. “https://csrc.nist.gov/projects/post-quantum-cryptography/ post-quantum-cryptography-standardization”.
[3] D. Jao, R. Azarderakhsh, M. Campagna, C. Costello, L. De Feo, B. Hess, A. Jalali, B. Koziel, B. LaMacchia, P. Longa, M. Naehrig, J. Renes, V. Soukharev, and D. Urbanik. “Supersingular Isogeny Key Encapsulation”. Submission to Post-Quantum Cryptography Standardization Process, 2017.
[4] R. A. Goutham, G.-J. Lee , K.-Y. Yoo “An anonymous id-based remote mutual authentication with key agreement protocol on ecc using smart cards,” in Proceedings of the 30th Annual ACM Symposium on Applied Computing. ACM, P.169–174, 2015.
[5] B. den Boer, “Diffie–Hellman is as strong as discrete log for certain primes in Advances in Cryptology” — CRYPTO 88, Lecture Notes in Computer Science 403, Springer, p. 530, 1988.
[6] NIST, Special Publication 800–56A, “Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography”, March, 2006.
[7] Yan Bo Ti. “Fault Attack on Super-singular Isogeny Cryptosystems”. In Tanja Lange and Tsuyoshi Takagi, editors, Post-Quantum Cryptography, pages 107–122, Cham, 2017. Springer International Publishing.
[8] De Feo, Luca; Jao, Plut. “Towards quantum-resistant cryptosystems from super-singular elliptic curve isogenies” (PDF). PQCrypto 2011. Springer. Retrieved 4 May 2014.
[9] Doliskani ,Javad, Geovandro C. C. F. Pereira, and Paulo S. L. M. Barreto. “Faster Cryptographic Hash Function From Supersingular Isogeny Graphs”. Cryptology e Print Archive , Report 2017/1202. https://eprint.iacr.org/2017/1202.
[10] Costello, Craig, P. Longa, and M. Naehrig. “Efficient Algorithms for Supersingular Isogeny Diffie-Hellman.” In: Advances in Cryptology– CRYPTO2016:36th Annual International Cryptology Conference, 2016.
[11] V. Soukharev, B. Hess “ PQDH: A Quantum-Safe Replacement for Diffie-Hellman based on SIDH “, ia.cr/2019/730.
[12] J.C.M. Baeten, “Scyther — Semantics and Verification of Security Protocols”, ISBN 90–386–0804–7. — ISBN 978–90–386–0804–4 NUR 993, 2006.
Writer: Reza Semyari
Contact: LinkedIn
