Abstract
Password authenticated key establishment (PAKE) is a cryptographic primitive that allows two parties who share a low-entropy secret (a password) to securely establish cryptographic keys in the absence of public key infrastructure. We propose the first quantum-resistant password-authenticated key exchange scheme based on supersingular elliptic curve isogenies. The scheme is built upon supersingular isogeny Diffie-Hellman [15], and uses the password to generate permutations which obscure the auxiliary points. We include elements of a security proof, and discuss roadblocks to obtaining a proof in the BPR model [1]. We also include some performance results.
1 Introduction
Many current cryptographic schemes are based on mathematical problems that are considered difficult for classical computers, but can easily be solved using quantum algorithms. To prepare for the emergence of quantum computers, we aim to design cryptographic primitives which will resist quantum attacks. One family of such primitives, proposed by Jao and De Feo [15]—commonly referred to as SIDH—uses isogenies between supersingular elliptic curves to construct quantum-resistant cryptographic protocols for public key cryptography. Subsequent work by Costache et al. [8] has shown that the security of SIDH reduces to the Supersingular Isogeny Graph problem originally proposed by Charles et al. [7].
Password-Authenticated Key Establishment (PAKE) is a primitive in which parties securely establish a common cryptographic key over an insecure channel using a password (modelled as a low-entropy secret). The first PAKE protocol was designed by Bellovin and Merritt in 1992 [3]. Today, many protocols of this type exist—most are based on the discrete logarithm problem in subgroups of
In particular, in SIDH, parties exchange elliptic curves which are images of a fixed public curve under ephemeral secret isogenies; then, each party computes the image of their peer’s curve under a related isogeny. Parties also exchange certain points on their ephemeral curves to aid in the computation. In our PAKE protocol, these so-called “auxiliary points” are obfuscated by transforming them according to a certain group action, described in Section 2. The passive security of this protocol comes from the difficulty of finding the correct points (preventing offline dictionary attacks) or performing the computation without them, while the active security from the fact that the adversary needs to “commit,” in a sense, to a group element in order to actively attack the protocol (preventing all but the most basic online dictionary attacks).
2 Background
2.1 Password-Authenticated Key Establishment
The PAKE security model of Bellare, Pointcheval, and Rogaway (BPR) [1] is very similar to the Canetti-Krawczyk (CK) security model [5] for authenticated key establishment. The complete model specification appears in Appendix A; here we only point out the major differences between the two. While the CK security model includes public-key infrastructure (i.e., each party registers a keypair, and the public keys are published), in the BPR model there are two kinds of parties—clients and servers—and clients choose passwords according to some distribution on a dictionary and share them with the servers. Of course, in the real world, passwords are low-entropy secrets; this is typically modelled by having passwords be chosen by parties uniformly from a set called the password dictionary which is small enough that it can be enumerated efficiently. In particular, attacks which involve “checking all passwords” are feasible. The examples in the following section illustrate this concept.
Two Insecure PAKEs
To illustrate the consequences of the low-entropy nature of passwords, we present two protocols which admit attacks that exploit it.
Diffie-Hellman + MAC Let MAC be a message authentication code protocol. Augment the Diffie-Hellman protocol by having each party send a MAC tag on each of their messages, using the password as the key; have the parties abort if any tag they receive is not consistent with the password and incoming message. Though this is reminiscent of the SIG-DH protocol of [5] (which is secure in the CK model), the low entropy of the password distribution means that it is susceptible to a straightforward offline dictionary attack: upon seeing a single message and tag (m, t), an adversary can simply check whether t = MACπ(m) for each password π in the dictionary. With overwhelming probability equality will hold for exactly one password π*, which is the party’s true password. Once the password is recovered, the adversary can successfully mount a man-in-the-middle attack.
Randomized-base Diffie-Hellman Consider a modified version of Diffie-Hellman in a group G = 〈g〉 of order N as follows. Let H be a hash function which maps the password dictionary into (ℤ/Nℤ)*. Instead of using the fixed base g, parties use base gH(π) when constructing their messages, so that if the ephemeral secret is a, the message is m = gaH(π). The shared secret is constructed as in Diffie-Hellman: if the messages are m = gaH(π) and m′ = gbH(π), the shared secret is (m′)a = gabH(π) = mb. An adversary can attack the protocol by intercepting a message m = gaH(π) from Alice and inserting their own message m′′ = gc. Alice will compute a shared secret s = gac, while the adversary can compute a “potential” shared secret
2.2 Isogenies
We provide a brief review of the background information. For further details on the mathematical foundations of isogenies, we refer the reader to [15, 25]. Given two elliptic curves E1 and E 2 over some finite field 𝔽q of size q, an isogeny
2.3 Isogeny-Based Cryptography
The first cryptographic construction to use supersingular elliptic curve isogenies is the hash function construction of Charles et al. [7], based on the isogeny graph path-finding problem. Public key cryptography based on isogenies was first introduced by Couveignes [10] and Rostovtsev & Stolbunov [23] using ordinary elliptic curves. Jao and De Feo [15] proposed the first public-key cryptosystem based on supersingular elliptic curve isogenies, along with a new assumption which was subsequently shown [8] to reduce to the path-finding assumption originally proposed in [7]. We review here the operation of the Jao and De Feo key exchange protocol SIDH, which is the foundation for our PAKE.
Fix a prime p of the form
With almost no loss in generality, private ephemeral keys with m = 1 can be used [9]. In this work we follow that convention.
2.4 The Möbius Action and Auxiliary Point Obfuscation
For a prime ℓ and an integer e, we define
to be the special linear and special reduced upper triangular groups modulo ℓe, respectively. If
In the context of isogeny computations, this (left) action of 2(ℓA, eA) induces a new (right) action (the Möbius action) on
thus we define the right action
Note that given EA with EA = EK/〈PA + mAQA〉 and
2.5 Computational Assumptions
For brevity, the standard assumptions of SIDH appear in Appendix B.
As noted in Section 2.3, to compute the shared secret in SIDH the parties must have the images of the public torsion bases under the secret isogenies. While previous works ignored these “auxiliary points” in favour of standard authentication methods, such as signature schemes [18] or generic transforms [14] to add authentication, here we focus on how we can disrupt man-in-the-middle attacks by obfuscating them. In this section we define a new computational assumption related to computing these auxiliary points. We use the notation of Section 2.3 for our global parameters, and define the security parameter λ = ⌈log2 p⌉. When P is a computational problem with some global parameters (such as the prime p and global curves and torsion points used in SIDH), we denote by InsP(γ) the set of all instances of problem P with global parameters γ. When A is an algorithm for a problem P and
The asymmetry of the isogeny computations requires us to consider two variants of each of the computational problem: one for
Definition 2.1
(Auxillary Point Computation–A (SI-APCA)). Let ϕA : E → E A be an
With the notation above, we define
and
The SI-APC assumption is that for t and n polynomial in λ,
Of course, the MOV attack [20] attack using the Pohlig-Hellman algorithm [22] can be used to solve extended discrete logarithms in supersingular elliptic curves, and so the SI-APC problem is equivalent to asking the adversary to find the image of any
The hardness of Problem 2.1 has not been thoroughly studied; however, we note that if the problem could be solved efficiently, the auxiliary points needed in SIDH [11] would not have to be sent, and thus the bandwidth of SIDH could be reduced by omitting them. So far, there are no proposals for how to do away with auxiliary points in SIDH, and no known solutions to the SI-APC problems. Notably, however, it is shown in [21] that, under some heuristics, SI-APC is equivalent to the corresponding isogeny problems for some nonstandard variant SIDH parameter sets (e.g., when
3 Our Protocol
The protocol builds on the SIDH scheme of Jao and De Feo [15]. Suppose a client
A chooses an ephemeral key and a message to B. In particular, A:
Chooses
Defines EA = EK/〈GA〉 and ϕA to be the isogeny with kernel 〈GA〉;
Defines
Sends (EA, XA, YA) to B.
Upon receiving (EA, XA, YA) from A, B:
Checks that
Computes AB = HA(j(EA)||πA);
Chooses
Defines EB = EK/〈GB〉 and ϕB to be the isogeny with kernel 〈GB〉;
Computes ΨB = HB(j(EB)||πA) and sets
Sends (EB, XB, YB) to A; and,
Constructs the key KB, which is given by
Upon receiving (EB, XB, YB) from B, A:
Checks that
Computes BA = HB(j(EB)||πA); and,
Constructs the key KA, given by
From the definitions of KA and KB, the correctness of the protocol follows if
so that
4 Progress Toward—and Roadblocks to—a Security Theorem
Ideally, we would like a security theorem of the following form: for all adversaries A which run in time t and use nS, nE, n0 queries to Send, Execute, and the random oracles respectively, we have
where α ≥ 1, the terms AdvPj (poly(t, nS , nE, nO)) encode the success probability in solving the underlying computational problems. Intuitively, this says “the protocol is secure, up to terms related to an adversary’s ability to solve the underlying computational problems plus a negligible probability, and up to online dictionary attacks which allow α password guesses per online session on average.”
In this section we present partial results toward a security theorem of this form for the protocol of Section 3, and discuss the roadblocks that have prevented us from establishing a complete security proof.
4.1 Successes
A birthday-type bound
The adversary can break the security of the protocol if, by chance, two sessions use the same ephemeral secret key. A straightforward birthday bound argument demonstrates that this occurs with probability at most
Preventing offline dictionary attacks from SIDH public key validation
The auxiliary points (ϕA(PB), ϕA(QB)) (respectively, (ϕB(PA), ϕB(QA))) used in SIDH are determined by the ephemeral secret key, and hence are information-theoretically determined by the public ephemeral curve E A (respectively, E B). In [13], the authors demonstrate an attack on static-ephemeral SIDH which uses maliciously-generated false auxiliary points to determine one party’s static public key; in response, auxiliary point verification procedures have been developed. The most robust known verification measure—present in [9]—ensures that the Tate pairing of the auxiliary points is correct; that is, one checks whether
This has the potential to yield an offline dictionary attack against protocols which obfuscate auxiliary points, as follows: upon receiving (EA, X A, YA) from a client whose password is π, the adversary constructs
for each password π′. For any π′ for which Equation 2 does not hold, the adversary is certain that the client’s password is not π′, since the true auxiliary points R A(π) and S A(π) will satisfy it. This could allow the adversary to cut down the set of “possible passwords,” without needing to launch an active attack.
Our choice of auxiliary point obfuscation method is not susceptible to this attack since for all
in particular, the pairing value is the same for each pair of points
Enforcing knowledge of the auxiliary points
In SIDH, the shared secret is j(E/ 〈GA, GB〉), where GA and GB are the ephemeral secret kernel generators, and the (passive) security of the protocol is predicated only on an adversary’s inability to compute this quantity from the messages. Notably, the shared secret is determined (information-theoretically) by E A and E B alone; the auxiliary points are required only to make the computation efficient. In contrast, in order for our protocol to be secure against offline dictionary attacks, it is necessary to assume that it is difficult to recover not only the SIDH shared secret from E A and EB, but also the correct auxiliary points. The most natural idea is to make the SI-APC assumption as described in Section 2.5; unfortunately, if the session key depends only on the SIDH shared secret, we cannot extract a solution to an SI-APC instance from an adversary who wins the security game, and thus cannot relate the security of the protocol to the SI-APC assumption directly.
The solution: we must include auxiliary point information in the keying information. By including A and ΨB as arguments to KDF, we can extract auxiliary points from the random oracle inputs of an adversary that wins the security game, and solve an instance of SI-APC. To solve an instance of SI-APCA we can insert the instance into a client’s message, choosing the auxiliary points at random. With probability [SL2(ℓB, eB) : 2(ℓB, eB)]−1 = (ℓB +1)−1 the randomly-chosen points are “valid” (in the sense that there exists an element of 2(ℓB, eB) that takes the true auxiliary points to the randomly-chosen points). Any adversary who wins the game with non-negligible advantage must make a KDF query with the correct
Querying H A and H B on the correct values, or;
Extracting them from the publicly-available, password-related information.
In the second case we can extract solutions to SI-APCA (respectively SI-APCB), by using the
4.2 Roadblocks
Password information in messages
In classical PAKE protocols, the message distribution is typically independent of the users’ passwords; in contrast, in our protocol the password is information-theoretically determined by a given message, but extracting the information from the messages is assumed to be difficult. Nevertheless, the possibility of obtaining partial password information from the messages alone cannot easily be ruled out, and so it is very difficult to quantify the number of passwords that can be eliminated per actively-attacked session (the α in equation (1)). Notably, some other post-quantum PAKEs, such as RLWE-PAK and RLWE-PPK [12] also have message distributions which are not independent of the password. [1]
Password guesses
A typical PAKE security argument defines the notion of “password guess,” and then argues that at most α password guesses can be made per session, under some computational assumption. A password guess on password π is intuitively “a KDF query in which the messages are those messages sent in a pair of matching sessions, the shared secret is the one that would be computed in the pair of matching sessions if the password were π, and the other inputs to KDFare consistent with the password and (if appropriate) have been the output of random oracle queries with password π.”
A natural-seeming notion for password guess on a client is that, for values
Send(A, i, (Initiate, B)) with output (E, X, Y);
Send(A, i, (E′ , X′ , Y′));
where
It is undetectable without knowledge of the ephemeral key nB, and;
It is difficult to formulate a computational problem whose hardness can be used to bound the number of passwords that can be checked per session.
If the “natural” password guess were the only type, under the heuristic assumption that the messages reveal no password information, we can show that only one password can be guessed per session (and, furthermore, that the protocol is secure in the model of [1], under further assumptions) under the assumption that the following computational problem (and its B-type variant) is difficult:
Definition 4.1
(Computational Simultaneous Group Action Problem— (Type A) (C-SGAA)). Let
5 Performance
It is clear from the protocol description in Section 3 that the message sizes in our protocol are identical to those of SIDH [11] for the same parameter set; in particular, the are among the smallest post-quantum message sizes at equivalent security levels. We implemented the scheme for the two parameter sets p434 and p503 from [14] to quantify the additional computational cost due to auxiliary point obfuscation/unobfuscation. Table 1 contains our performance results.
Quantitative results for our protocol compared with unauthenticated SIDH. Results measured on a machine running Ubuntu 18.04 LTS with a 1.6 GHz Intel Core i5-8250U processor.
| Parameter Set | Scheme | Total Clock cycles (×106) |
|---|---|---|
| p434 | SIDH | 65 |
| p503 | SIDH | 116 |
| p434 | Our Protocol | 65 + 77 = 142 |
| p503 | Our Protocol | 116 + 112 = 228 |
6 Conclusion
We have presented a proposal for an isogeny-based password-authenticated key establishment protocol based on supersingular isogeny Diffie-Hellman. Of particular interest is that our protocol explicitly makes use of the auxiliary points for security, rather than efficiency .We hope that the partial results presented here can serve as a stepping stone on the path to provably-secure isogeny-based PAKE.
Acknowledgement
This research was undertaken thanks in part to funding from the Canada First Research Excellence Fund, CryptoWorks21, NSERC, Public Works and Government Services Canada, and the Royal Bank of Canada.
References
[1] Mihir Bellare, David Pointcheval and Phillip Rogaway, Authenticated Key Exchange Secure against Dictionary Attacks, in: Advances in Cryptology— EUROCRYPT 2000 (Bart Preneel, ed.), pp. 139–155, Springer Berlin Heidelberg, Berlin, Heidelberg, 2000.10.1007/3-540-45539-6_11Search in Google Scholar
[2] Mihir Bellare and Phillip Rogaway, Entity Authentication and Key Distribution, in: Advances in Cryptology — CRYPTO ’93 (Douglas R. Stinson, ed.), pp. 232–249, Springer Berlin Heidelberg, Berlin, Heidelberg, 1994.10.1007/3-540-48329-2_21Search in Google Scholar
[3] Steven M. Bellovin and Michael Merritt, Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks, in: IEEE Symposium On Research In Security And Privacy, pp. 72–84, 1992.10.1145/168588.168618Search in Google Scholar
[4] Reinier Bröker, Denis Charles and Kristin Lauter, Evaluating Large Degree Isogenies and Applications to Pairing Based Cryptography, in: Proceedings of the 2nd International Conference on Pairing-Based Cryptography, pp. 100–112, 2008.10.1007/978-3-540-85538-5_7Search in Google Scholar
[5] Ran Canetti and Hugo Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, in: EURO-CRYPT (Birgit Pfitzmann, ed.), Lecture Notes in Computer Science 2045, pp. 453–474, Springer, 2001.10.1007/3-540-44987-6_28Search in Google Scholar
[6] Ran Canetti and Hugo Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, in: Advances in Cryptology—EUROCRYPT 2001 (Birgit Pfitzmann, ed.), pp. 453–474, Springer, Berlin, Heidelberg, 2001.10.1007/3-540-45311-3Search in Google Scholar
[7] Denis Xavier Charles, Kristin E. Lauter and Eyal Z. Goren, Cryptographic Hash Functions from Expander Graphs, Journal of Cryptology 22 (2009), 93–113.10.1007/s00145-007-9002-xSearch in Google Scholar
[8] Anamaria Costache, Brooke Feigon, Kristin Lauter, Maike Massierer and Anna Puskas, Ramanujan graphs in cryptography, Research Directions in Number Theory: Women in Numbers IV, AWM Springer Series (to appear), 2019, https://eprint.iacr.org/2018/59310.1007/978-3-030-19478-9_1Search in Google Scholar
[9] Craig Costello, Patrick Longa and Michael Naehrig, Eflcient Algorithms for Supersingular Isogeny Difle-Hellman, in: Advances in Cryptology – CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I (Matthew Robshaw and Jonathan Katz, eds.), pp. 572–601, Springer Berlin Heidelberg, Berlin, Heidelberg, 2016.10.1007/978-3-662-53018-4_21Search in Google Scholar
[10] Jean-Marc Couveignes, Hard Homogeneous Spaces, 2006, http://eprint.iacr.org/2006/291/Search in Google Scholar
[11] Luca De Feo, David Jao and Jérôme Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol. 8 (2014), 209–247.10.1515/jmc-2012-0015Search in Google Scholar
[12] Jintai Ding, Saed Alsayigh, Jean Lancrenon, Saraswathy RV and Michael Snook, Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-Quantum World, in: Topics in Cryptology – CT-RSA 2017 (Helena Handschuh, ed.), pp. 183–204, Springer, Cham, 2017.10.1007/978-3-319-52153-4_11Search in Google Scholar
[13] Steven D. Galbraith, Christophe Petit, Barak Shani and Yan Bo Ti, On the Security of Supersingular Isogeny Cryptosystems, in: Advances in Cryptology – ASIACRYPT 2016 (Jung Hee Cheon and Tsuyoshi Takagi, eds.), pp. 63–91, Springer Berlin Heidelberg, Berlin, Heidelberg, 2016.10.1007/978-3-662-53887-6_3Search in Google Scholar
[14] David Jao, Reza Azarderakhsh, Matthew Campagna, Craig Costello, Luca De Feo, Basil Hess, Amir Jalali, Brian Koziel, Brian LaMacchia, Patrick Longa, Michael Naehrig, Geovandro Pereira, Joost Renes, Vladimir Soukharev and David Ubanik, Supersingular Isogeny Key Encapsulation, NIST Post-Quantum Cryptography Standardization Process, Report, 2019.Search in Google Scholar
[15] David Jao and Luca De Feo, Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies, in: PQCrypto (Bo-Yin Yang, ed.), Lecture Notes in Computer Science 7071, pp. 19–34, Springer, 2011.10.1007/978-3-642-25405-5_2Search in Google Scholar
[16] David Jao and Vladimir Soukharev, A subexponential algorithm for evaluating large degree isogenies, Algorithmic number theory, Lecture Notes in Comput. Sci. 6197, Springer, Berlin, 2010, pp. 219–233.10.1007/978-3-642-14518-6_19Search in Google Scholar
[17] Brian LaMacchia, Kristin Lauter and Anton Mityagin, Stronger Security of Authenticated Key Exchange, in: Provable Security: First International Conference (Willy Susilo, Joseph K. Liu and Yi Mu, eds.), pp. 1–16, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007.10.1007/978-3-540-75670-5_1Search in Google Scholar
[18] Jason LeGrow, Post-Quantum Security of Authenticated Key Establishment Protocols,Master’s thesis, University ofWaterloo, 2016.Search in Google Scholar
[19] Vadim Lyubashevsky, Chris Peikert and Oded Regev, On Ideal Lattices and Learning with Errors over Rings, in: Advances in Cryptology – EUROCRYPT 2010 (Henri Gilbert, ed.), pp. 1–23, Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.10.1007/978-3-642-13190-5_1Search in Google Scholar
[20] Alfred J. Menezes, Tatsuaki Okamoto and Scott A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inform. Theory 39 (1993), 1639–1646.10.1109/18.259647Search in Google Scholar
[21] Christophe Petit, Faster Algorithms for Isogeny Problems Using Torsion Point Images, in: Advances in Cryptology – ASI-ACRYPT 2017 (Tsuyoshi Takagi and Thomas Peyrin, eds.), pp. 330–353, Springer International Publishing, Cham, 2017.10.1007/978-3-319-70697-9_12Search in Google Scholar
[22] S. Pohlig and M. Hellman, An Improved Algorithm for Computing Logarithms over and Its Cryptographic Significance (Corresp.), IEEE Trans. Inf. Theor. 24 (2006), 106–110.10.1109/TIT.1978.1055817Search in Google Scholar
[23] Alexander Rostovtsev and Anton Stolbunov, Public-key cryptosystem based on isogenies, 2006, http://eprint.iacr.org/2006/145/Search in Google Scholar
[24] Joseph H. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106, Springer, New York, 1986.10.1007/978-1-4757-1920-8Search in Google Scholar
[25] Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics 106, Springer-Verlag, New York, 1992.Search in Google Scholar
[26] Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238–A241.Search in Google Scholar
[27] Jiang Zhang and Yu Yu, Two-Round PAKE from Approximate SPH and Instantiations from Lattices, in: Advances in Cryptology—ASIACRYPT 2017 (Tsuyoshi Takagi and Thomas Peyrin, eds.), pp. 37–67, Springer, Cham, 2017.10.1007/978-3-319-70700-6_2Search in Google Scholar
A The Security Model
PAKE security is commonly proved in the model of Bellare, Pointcheval, and Rogaway [1], which we briefly review here.
Protocols
Fundamentally, a protocol Π is a probabilistic algorithm which maps strings (in this context, concatenations of passwords, randomness, and protocol-specific messages and parameters) to strings (keys).
Parties and Party Identifiers
Participants in protocols are called parties. Parties are either clients 𝒞 or servers S. In this model, protocols are initiated by clients and responded to by servers. All clients are served by all servers. Each party
Passwords
We work in the symmetric password model: each client
Password Initialization
In models of authenticated key establishment, parties establish public-key/private-key pairs and securely publish their public keys (e.g., [2, 6, 17]) in a pre-protocol “initialization” phase. Similarly, in this model there is a pre-protocol initialization phase where users generate passwords and “install” them on servers (i.e., servers get the passwords) securely.
Party Instances
Associated to each party
Acceptance and Termination
A party instance “accepts” when they compute a session key, and “terminates” when it will send no more messages. In our protocol, acceptance is always followed immediately by termination, but termination may occur without acceptance (e.g., in the case of ill-formed incoming messages).
The Security Experiment
Informally, in the security experiment, a new entity (the adversary) attempts to break semantic security of the protocol after interacting with the parties and one additional “formal” party who “administrates” the game (the challenger). The security experiment proceeds in three stages
Initialization: The adversary chooses disjoint sets
Information Gathering: The adversary performs computations and interacts with the parties and challenger. The computational power of the adversary is not fixed in the model, but his interactions are limited to:
Send(U, n, msg): Message M is sent to
Reveal(U, n): The instance
Execute(A, n, B, m): If
Corrupt(U): If
Test(U, n): The challenger C chooses b ∈ {0, 1} uniformly at random; if b = 0, the challenger reveals
Remark A.1
Our definition of Corrupt in item (d) above is known as the weak corruption model [1, Remark 3]. In the strong corruption model, a Corrupt(U) query also reveals the state of each oracle
The Game: To begin, we must define what it means for an oracle
Definition A.2
(Partnered Oracles). A pair of oracles
No other oracle
Definition A.3
(Fresh Oracle). An oracle
Reveal(U, n) has been issued.
Reveal(V, m) has been issued, where
Corrupt(V, i) was issued for some
Now, at any point during the protocol, A may make a Test(U, n) query. If
B Computational Assumptions of SIDH
In this section we present the SIDH and SSI problems [11, Problems 5.1–5.4], whose presumed hardness underlies the security of SIDH (and, by extension, our protocol).
Definition B.1 (Computational Supersingular Isogeny Diffie-Hellman Problem (SIDH)). Let
When the global parameters and auxiliary points are clear from context, we abbreviate this as E AB = SIDH(EA, EB). We also define variants of SIDH:
These arise in SIDH by considering messages which are not well-formed.
For an algorithm A which, given a valid SIDH instance, produces a list of candidate solutions to the instance, define its advantage as
where InsSIDH(p) is the set of all valid SIDH instances defined over GF(p2). Also define
Intuitively, this quantity measures the maximum probability of solving a randomly chosen SIDH instance in time t if you are allowed to make n guesses. The SIDH assumption is that for t, n = poly(),
As in Section 2.5, the asymmetry the isogeny computations requires us to consider there are really
Definition B.2 (Supersingular Isogeny Problem–A (SSIA)). Let ϕA : E → E A be an isogeny with kernel 〈PA + nAQA〉 for
The SIDH problem reduces to both the Type A and type B variants of Problem B.2 by noting that knowledge of ker ϕA, ϕB(PA) and ϕB(QA) allows one to map EB to EAB, and the knowledge of ker ϕB, ϕA(PB) and ϕA(QB) allows one to map E A to E AB similarly. Recent work due to Costache et al. [8, Theorem 3.2] reduces the SIDH problem to the more general isogeny-graph path-finding problem of [7] in a similar fashion.
© 2020 O. Taraskin et al., published by De Gruyter
This work is licensed under the Creative Commons Attribution 4.0 International License.
