Patent Publication Number: US-10313124-B1

Title: Public key validation in supersingular isogeny-based cryptographic protocols

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application is a divisional of U.S. patent application Ser. No. 15/887,240, filed Feb. 2, 2018, entitled “Public Key Validation in Supersingular Isogeny-Based Cryptographic Protocols,” which is incorporated herein by reference. 
    
    
     BACKGROUND 
     The following description relates to verifying data in supersingular isogeny-based cryptographic protocols. 
     Cryptography systems are used to communicate securely over public channels. For example, some cryptography systems provide confidentiality by encrypting messages, and some cryptography systems provide authenticity through digital signatures. Some cryptography systems operate using public keys, private keys and shared secrets. 
    
    
     
       DESCRIPTION OF DRAWINGS 
         FIG. 1  is a block diagram showing aspects of an example communication system. 
         FIG. 2  is a flow diagram showing aspects of an example cryptosystem process. 
         FIGS. 3A-3B  are flow diagrams showing an example supersingular isogeny-based cryptographic protocol. 
         FIGS. 4A-4B  are flow diagrams showing another example supersingular isogeny-based cryptographic protocol. 
     
    
    
     DETAILED DESCRIPTION 
     In some aspects of the present disclosure, improved supersingular isogeny-based cryptographic protocols are described. The supersingular isogeny Diffie-Hellman key agreement protocol (SIDH) is an example of a supersingular isogeny-based cryptographic protocol that is believed to be secure against attacks carried out by quantum computers. In some SIDH deployments, if one of the entities reuses its secret key (e.g., as a static private key), then the secret key can be efficiently recovered, for example, with the active attack described by Galbraith et al. (Galbraith, et al., “On the security of supersingular isogeny cryptosystems,”  Advances in Cryptology—ASIACRYPT  2016. Lecture Notes in Computer Science vol. 10031. Springer, Berlin, Heidelberg, pp. 63-91, 2016.) A countermeasure to this attack was described by Kirkwood et al. (Kirkwood, et al., “Failure is not an option: standardization issues for post-quantum key agreement,”  Workshop on Cybersecurity in a Post -Quantum World, 2015.). However, existing countermeasures are computationally expensive and therefore time consuming and less practical. Here we describe supersingular isogeny-based cryptographic protocols that include improved countermeasures, for example, countermeasures that allow faster computations while achieving the same or otherwise acceptable security levels. 
     Accordingly, aspects of the systems and techniques described here can be used to improve the operation of communications systems (e.g., data networks, etc.), computer systems (e.g., network-connected computers, etc.), smart devices (e.g., so-called “Internet-of-Things” (IoT) devices, etc.) and other classes of technology. For example, a wide variety of modern technologies rely on computer-implemented cryptosystems for secure operation, and the techniques described here can improve such computer-implemented cryptosystems, for example, making them more secure, more computationally efficient or providing other advantages in some instances. 
     In some implementations, the techniques described here can be used to neutralize or otherwise reduce exposure to an attack on a supersingular isogeny-based cryptographic protocol, for example, the active attack proposed by Galbraith et al. and potentially other types of attacks. The active attack proposed by Galbraith et al. is performed by one of the two entities (“Alice” and “Bob”) executing an SIDH protocol. In particular, the attack allows Bob to recover Alice&#39;s secret key efficiently one bit a time. In order to determine the i-th bit of Alice&#39;s secret key, Bob sends Alice an incorrect public key (E B , U i , V i ) instead of the correct public key (E B , ϕ B  (P A ), ϕ B (Q A )), where U 1  and V i  are some linear combinations of ϕ B (P A ) and ϕ B (Q A ). In the cryptographic protocols described here, one of the entities (“Alice”) validates the public key of the other entity (“Bob”) in a manner that neutralizes or otherwise reduces exposure to an attack of the type described by Galbraith et al. 
     In some cryptographic protocols (including the example protocol  300  shown in  FIGS. 3A-3B  and variants), Bob sends (an encrypted version of) his secret generator G B  instead of a random seed. By receiving the secret generator G B  from Bob, Alice can validate Bob&#39;s public key without having to duplicate all of Bob&#39;s computations to derive the public key. For example, Alice may avoid the computation of both β′=PRF(r B ′) and G B ′=P B +[β′]Q B , where PRF represents a pseudorandom function that generates the integer β′ from the random seed r B ′. Given that β′ is a number whose magnitude is approximately equal to 3 m , this prevents Alice from computing an expensive operation of scalar multiplication by a large number β′. 
     In addition, the example protocol  300  shown in  FIGS. 3A-3B  is secure, despite the fact that (potentially dishonest) Bob has several options to modify the data sent to Alice. In particular, Bob can provide a generator point G B  that does not have a full order. Or instead of sending the correct generator point G B , Bob can send a different generator of the subgroup (G B ). However, by validating the degree of the isogeny defined by G B  (e.g., validating deg(ϕ B ′)=3 m ), Alice can detect if Bob provides a generator point G B  that does not have a full order. This condition can be verified in the process of isogeny evaluation, and, at least in some cases, does not require any significant additional computational overhead. Further, by verifying certain conditions (e.g., j(E B )≠0, 1728, E B ′=E B , ϕ B ′(P A )=U and ϕ B ′(Q A )=V), Alice can ensure that, by providing alternative generators of  G B   , Bob does not learn any information about Alice&#39;s secret key. 
     In some cryptographic protocols (including the example protocol  400  shown in  FIGS. 4A-4B  and variants), Alice verifies a pairing value and an isogeny evaluation (e.g., e 2     n   (U,V)=e 2     n   (P A ,Q A ) 3     m    and ϕ B ′(Q A )=V in the example shown in  FIGS. 4A-4B ). Using the pairing-based validation allows Alice to validate Bob&#39;s public key using only one isogeny evaluation (e.g., ϕ B ′(Q A )). In addition, Alice can complete the pairing-based validation before computing any isogeny evaluations, which means that Alice can detect some invalid public keys without an isogeny evaluation. In addition, the example protocol  400  shown in  FIGS. 4A-4B  is secure, in the sense that it allows Alice to use a static key and detect if Bob dishonestly modified any of the parameters of his public key (E B , ϕ B (P A ), ϕ B (Q A )). 
     In some cases, the public key validation techniques described here can be used to improve supersingular isogeny-based key agreement protocols (e.g., SIDH), as well as other supersingular isogeny-based cryptographic protocols. For example, the public key validation techniques described here may be applied to supersingular isogeny-based public key encryption schemes, such as, for example, the public key encryption scheme described by De Feo et al. (De Feo, et al., “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies.” Journal of Mathematical Cryptology  8 (3), pp. 209-247, 2014.). As another example, the public key validation techniques described here may be applied to supersingular isogeny-based key encapsulation mechanism (KEM) schemes. 
       FIG. 1  is a block diagram showing aspects of an example communication system  100 . The example communication system  100  shown in  FIG. 1  includes two nodes  102 ,  104 . The nodes  102 ,  104  use a supersingular isogeny-based cryptosystem to communicate with each other over a channel  106 . The nodes  102 ,  104  represent distinct entities in the cryptosystem. 
     In the example shown, a quantum-enabled adversary  108  has access to the channel  106 , information exchanged on the channel  106 , or both. In some instances, the quantum-enabled adversary  108  can transmit or modify information on the channel  106 . The communication system  100  may include additional or different features, and the components in a communication system may be configured to operate as shown in  FIG. 1  or in another manner. 
     In some implementations, nodes in the communication system  100  may have a server-client relationship. For example, the node  102  can be a server and the node  104  can be its client, or vice-versa. In some implementations, nodes in the communication system  100  may have a peer-to-peer relationship. For example, the nodes  102 ,  104  can be peers in a served network, in a peer-to-peer network or another type of network. Nodes may have another type of relationship in the communication system  100 . 
     In the example shown in  FIG. 1 , the example nodes  102 ,  104  each have computational resources (e.g., hardware, software, firmware) that are used to communicate with other nodes. In some implementations, nodes in the communication system  100  can be implemented in various systems, such as, for example, laptops, desktops, workstations, smartphones, tablets, personal digital assistants, servers, server clusters, mainframes, IoT devices, and other types of computer systems. As shown in  FIG. 1 , the example node  102  includes a memory  110 , a processor  112 , and an interface  114 . Each of the nodes  102 ,  104  may include the same, additional or different components. The nodes  102 ,  104  may be configured to operate as shown and described with respect to  FIG. 1  or in another manner. 
     In the example shown in  FIG. 1 , the entities represented by the nodes  102 ,  104  may correspond to a computing device, a computer system, an IP address or other network address, or another type of computer-readable identifier or instance of a computer resource. Accordingly, the computations and other operations of each entity may be performed by one or more processors or other elements of the respective node  102 ,  104 . Similarly, information sent to or received by an entity may be sent to or received by an element (e.g., one or more processors, memories, or interfaces) of the respective node  102 ,  104 . 
     The example memory  110  can include, for example, random access memory (RAM), a storage device (e.g., a writable read-only memory (ROM) or others), a hard disk, or another type of storage medium. The example memory  110  can store instructions (e.g., computer code, a computer program, etc.) associated with an operating system, computer applications and other resources. The memory  110  can also store application data and data objects that can be interpreted by one or more applications or virtual machines running on the node  102 . The node  102  can be preprogrammed, or it can be programmed (and reprogrammed), by loading a program from another source (e.g., from a DVD-ROM, from a removable memory device, from a remote server, from a data network or in another manner). In some cases, the memory  110  stores computer-readable instructions for software applications, scripts, programs, functions, executables or other modules that are interpreted or executed by the processor  112 . For example, the computer-readable instructions can be configured to perform one or more of the operations shown in one or both of  FIG. 2 . 
     In the example node  102  shown in  FIG. 1 , the processor  112  is a data processing apparatus that can execute instructions, for example, to generate output data based on data inputs. For example, the processor  112  can run computer programs by executing or interpreting the software, scripts, programs, functions, executables, or other modules stored in the memory  110 . In some instances, the processor  112  may perform one or more of the operations shown in  FIG. 2 . 
     The example processor  112  shown in  FIG. 1  can include one or more chips or chipsets that include analog circuitry, digital circuitry or a combination thereof. In some cases, the processor  112  includes multiple processor devices such as, for example, one or more main processors and one or more co-processors. For instance, the processor  112  may include a main processor that can delegate certain computational tasks to a cryptographic co-processor, which may be configured to perform the computational tasks more efficiently than the main processor or in parallel with other computational tasks performed by other processor devices. In some instances, the processor  112  coordinates or controls operation of other components of the node  102 , such as, for example, user interfaces, communication interfaces, peripheral devices and possibly other components. 
     In the example node  102  shown in  FIG. 1 , the interface  114  provides communication with other nodes (e.g., via channel  106 ). In some cases, the interface  114  includes a wireless communication interface that provides wireless communication using a wireless protocol or standard. For example, the interface  114  may provide wireless communication via Bluetooth, Wi-Fi, Near Field Communication (NFC), CDMA, TDMA, PDC, WCDMA, CDMA2000, GPRS, GSM, or other forms of wireless communication. Such communication may occur, for example, through a radio-frequency transceiver or another type of component. In some cases, the interface  114  includes a wired communication interface (e.g., USB, Ethernet) that can be connected to one or more input/output devices, such as, for example, a keyboard, a pointing device, a scanner, or a networking device such as a switch or router, for example, through a network adapter. 
     The example channel  106  can include all or part of a connector, a data communication network or another type of communication link. For example, the channel  106  can include one or more wired or wireless connections, one or more wired or wireless networks or other communication channels. The channel  106  may have any spatial distribution. The channel  106  may be public, private, or include aspects that are public and private. For instance, in some examples, the channel  106  includes one or more of a Local Area Network (LAN), a Wide Area Network (WAN), a Virtual Private Network (VPN), the Internet, a peer-to-peer network, a cellular network, a Wi-Fi network, a Personal Area Network (PAN) (e.g., a Bluetooth low energy (BTLE) network, a ZigBee network, etc.) or other short-range network involving machine-to-machine (M2M) communication, or another type of data communication network. 
     In the example shown, the quantum-enabled adversary  108  is a node in the communication system  100  that has access to quantum computational resources. For example, the quantum-enabled adversary  108  can be, include, or have access to a quantum computer, a quantum information processor, a quantum memory, a quantum communication interface or a combination of these and possibly other quantum technologies. In some implementations, the quantum-enabled adversary  108  can include a hybrid computing system, for instance, that includes a quantum processor driven by a classical front end processor, or another type of hybrid computing system. 
     In some examples, the quantum-enabled adversary  108  can store and process information in a quantum system. For instance, the quantum-enabled adversary  108  may encode information as quantum bits (“qubits”) and process the information by manipulating the qubits. The information may be encoded in physical qubits, logical qubits, or a combination of these and other types of qubit encodings. In some implementations, the quantum-enabled adversary  108  can operate in a fault-tolerant regime, or the quantum-enabled adversary may operate below the fault-tolerant regime. 
     Many public key cryptography systems (“cryptosystems”) are known to be insecure against an attacker armed with a scalable quantum computer. For example, the Diffie-Hellman (DH) and elliptic curve Diffie-Hellman (ECDH) key agreement protocols are vulnerable to certain types of attacks by quantum-enabled adversaries. The threat of quantum computers to public key cryptography can be mitigated by switching to other public key cryptography systems that are believed to be invulnerable to quantum attack. For example, supersingular isogeny-based protocols have been proposed as a quantum-resistant replacement for contemporary key agreement protocols such as the Diffie-Hellman (DH) and elliptic curve Diffie-Hellman (ECDH). 
     In some implementations, the example quantum-enabled adversary  108  can perform quantum computing algorithms, execute quantum computing circuits or quantum communication protocols, or perform other types of quantum information processing tasks. In the example shown, the quantum-enabled adversary  108  can perform Shor&#39;s algorithm, which allows the quantum-enabled adversary to efficiently solve problems that are believed to be hard on a classical computer. For example, the quantum-enabled adversary  108  may use Shor&#39;s algorithm to factor large integers, find discrete logarithms or possibly to solve other problems in a computationally-efficient manner. Accordingly, the example quantum-enabled adversary  108  can compromise the security of certain quantum-vulnerable cryptography systems (e.g., by computing a private key of a certificate authority or other entity based on public information). 
     The example quantum-enabled adversary  108  shown in  FIG. 1  can access information exchanged on the channel  106 . For example, the quantum-enabled adversary  108  may access some or all of the information exchanged between the nodes  102 ,  104 . In some instances, the quantum-enabled adversary  108  can directly observe correspondence on the channel  106 ; in some instances, the quantum-enabled adversary  108  indirectly obtains such correspondence, for example, by receiving information observed on the channel  106  by another entity or system. 
     In some implementations, the quantum-enabled adversary  108  can factor integers, compute discrete logarithms, or perform other classically-hard computational tasks fast enough to compromise the security of certain cryptography systems. For example, the quantum-enabled adversary  108  may be capable of computing prime factors fast enough to compromise certain RSA-based cryptography systems or computing discrete logarithms fast enough to compromise certain ECC-based cryptography systems. 
     In the example shown in  FIG. 1 , the nodes  102 ,  104  may use a quantum-resistant cryptography system that cannot be compromised by the example quantum-enabled adversary  108 . For instance, the nodes  102 ,  104  may use a cryptography system that is secure against a quantum computer that can efficiently execute Shor&#39;s algorithm or other types of algorithms that are known to compromise the security of certain conventional cryptography standards. 
     In some implementations, the nodes  102 ,  104  use a digital signature scheme that allows each node to verify the authenticity of messages received from the other node, and the digital signature scheme can be a quantum-resistant scheme that is not vulnerable to the quantum computing resources of the quantum-enabled adversary  108 . In some implementations, the nodes  102 ,  104  use an encryption scheme that allows each node to send confidential messages to the other node, and the encryption scheme can be a quantum-resistant scheme that is not vulnerable to the quantum computing resources of the quantum-enabled adversary  108 . Such digital signature schemes and encryption schemes can include or be used in conjunction with a key agreement protocol or a key encapsulation mechanism that is also secure against attacks by the quantum-enabled adversary  108 . In some examples, the nodes  102 ,  104  can use the example techniques shown in  FIG. 2 , or the nodes  102 ,  104  may use variations of these and other techniques to communicate securely on the channel  106 . 
       FIG. 2  is a flow diagram showing aspects of an example cryptographic process  200 . The example cryptographic process  200  can be performed, for example, by computer systems that can exchange information over a communication channel. For instance, operations in the cryptographic process  200  may be performed by the nodes  102 ,  104  in the example communication system  100  shown in  FIG. 1  or in another type of system. The example process  200  may include additional or different operations, including operations performed by additional or different entities, and the operations may be performed in the order shown or in another order. 
     In some cases, one or more of the operations shown in  FIG. 2  are implemented as processes that include multiple operations, sub-processes or other types of routines. For example, the processes shown in  FIGS. 3A-3B and 4A-4B  can be used, in some instances, to perform one or more of the example operations shown in  FIG. 2 . In some cases, operations can be combined, performed in parallel, iterated or otherwise repeated or performed in another manner. 
     The example process  200  shown in  FIG. 2  includes operations performed by nodes  202 A,  202 B. In the example shown, the nodes  202 A,  202 B represent two distinct entities in a supersingular isogeny-based cryptosystem. The two distinct entities are referred to as “Alice” and “Bob” in  FIG. 2 . In the example shown, the nodes  202 A,  202 B exchange public data, and each node uses the public data provided by the other node to execute the process  200 . In some cases, the nodes  202 A,  202 B may have a server-client relationship, a peer-to-peer relationship or another type of relationship. The nodes  202 A,  202 B may communicate with each other, for example, directly or indirectly, in each stage of the process  200 . In some cases, the process  200  or individual operations within the process  200  can be executed by the nodes  202 A,  202 B over a period of seconds, or the process  200  may be executed over a shorter or longer period of time. 
     In the example shown in  FIG. 2 , each entity may correspond to a computing device, a computer system, an IP address or other network address, or another type of computer-readable identifier or instance of a computer resource. Accordingly, the computations and other operations of each entity may be performed by one or more processors or other elements of the respective node  202 A,  202 B. Similarly, information sent to or received by an entity may be sent to or received by an element (e.g., one or more processors, memories, or interfaces) of the respective node  202 A,  202 B. 
     In some examples, the cryptographic process  200  is secure against quantum-enabled adversaries such as, for example, the quantum-enabled adversary  108  shown in  FIG. 1 . For instance, in some cases, the example cryptographic process  200  is secure against certain types of attacks or other processes that can be performed by a quantum-enabled adversary who has access to public information exchanged between the server  202  and the client  204 . The example cryptographic process  200  may also provide security against classically-enabled adversaries who do not have access to quantum computers or other quantum resources. 
     At  210 A and  210 B, the nodes  202 A,  202 B perform one or more cryptosystem setup operations. A supersingular isogeny-based cryptosystem can be described in terms of a supersingular elliptic curve E defined over a finite field F p     2   . Let p≥5 be a prime integer; let F p     2    denote a finite field of characteristic p with p 2  elements; and let E be an elliptic curve defined over F p     2   . The cryptosystem setup operations at  210 A,  210 B can include defining the prime integer p=l A   n l B   m f±1, where l A  and l B  are distinct prime integers, where f, n, and m are positive integers with f being coprime to l A  and l B , such that l A   n ≈l B   m . In some examples described here, l A =2 and l B =3, and p=2 n 3 m f−1, with f being coprime to 2 and 3, such that 2 n ≈3 m . In such examples, the elliptic curve E has (2 n 3 m f) 2  points. 
     The cryptosystem setup operations at  210 A,  210 B can include defining elliptic curve points P A , Q A , P B , Q B  on the elliptic curve E. For each elliptic curve point, a pair of numbers in the finite field F p     2    can represent the x-coordinate and the y-coordinate. For instance, each coordinate can be expressed A+i*B for some integers A and B between 0 and p. Therefore, each elliptic curve point can be represented by four integers between 0 and p. 
     In examples where l A =2 and l B =3, {P A ,Q A } represents a basis of the set of 2 n -torsion points E[2 n ], and {P B ,Q B } represents a basis of the set of 3 m -torsion points E[3 m ]; the order of elliptic curve points P A  and Q A  is 2 n ; and the order of elliptic curve points P B  and Q B  is 3 m . The global system parameters p, E, P A ,Q A , P B ,Q B , p, l A , l B , f, n and m, which define a supersingular isogeny cryptosystem, can be published to, computed by, or otherwise made available to the nodes  202 A,  202 B. When a cryptographic protocol is executed with these parameters, one of the entities works over a first set of elliptic curve points defined by l A   n  (e.g., E[2 n ]), and the other entity works over a second set of elliptic curve points defined by l A   n  (e.g., E[3 m ]). In the examples described here (in  FIGS. 3A-3B and 4A-4B ), Alice and Bob agree that Alice will work over the set E[2 n ] and Bob will work over the set E[3 m ]. 
     At  212 A and  212 B, the nodes  202 A,  202 B perform one or more operations to each generate a respective key pair. In some implementations, each respective node  202 A,  202 B produces a public-private key pair. For instance, a first public-private key pair for the first entity (“Alice”) may be produced at  212 A, and a second public-private key pair for the second entity (“Bob”) may be produced at  212 B. A public-private key pair of an entity includes a private key and a corresponding public key, which are related as proscribed by the cryptosystem. The private key is kept as a secret of the entity, while the public key can be published to other entities in the cryptosystem. In the example protocol  300  shown in  FIGS. 3A-3B , Alice&#39;s and Bob&#39;s respective public-private key pairs are generated by operations  310 ,  312 ,  314  and  316 ,  318 ,  320 . In the example protocol  400  shown in  FIGS. 4A-4B , Alice&#39;s and Bob&#39;s respective public-private key pairs are generated by operations  410 ,  412 ,  414  and  408 ,  416 ,  418 ,  420 . A public-private key pair may be generated in another manner. In some cases, a public-private key pair can be used as a static key pair or an ephemeral key pair. 
     At  214 A and  214 B, the nodes  202 A,  202 B perform one or more operations to derive a shared secret. In some implementations, the nodes  202 A,  202 B produce a shared secret value that can subsequently be used for cryptographic correspondence. For instance, deriving the shared secret at  214 A,  214 B may produce a secret value that is known to both entities (Alice and Bob), but is not publicly known or easily derivable from public information. In the example protocol  300  shown in  FIGS. 3A-3B , the shared secret is the j-invariant value (j(E AB )=j(E BA )) computed at  328  and  340 . In the example protocol  400  shown in  FIGS. 4A-4B , the shared secret is the j-invariant value (j(E AB )=j(E BA )) computed at  428  and  440 . In some cases, the protocol performed by each entity to derives the shared secret also validates the public key of the other entity. For example, the techniques described with respect to  FIGS. 3A-3B and 4A-4B  may be used to validate public keys. 
     At  216 A and  216 B, the shared secret (generated at  214 A and  214 B) is used for cryptographic correspondence. For example, the keys generated by a key agreement protocol may be used in in a supersingular isogeny-based cryptographic protocol to encrypt or decrypt a message, to sign or verify a message or to generate other parameters that are used for cryptographic correspondence. The keys may be used in another manner. 
     Two example cryptographic protocols  300 ,  400  are described below with respect to  FIGS. 3A-3B  and  FIGS. 4A-4B . In the examples shown in  FIGS. 3A-3B  and FIGS.  4 A- 4 B, the entities (“Alice” and “Bob”) correspond to a computing device, a computer system, an IP address or other network address, or another type of computer-readable identifier or instance of a computer resource. Accordingly, the computations and other operations of each entity may be performed by one or more processors or other elements of the respective node. Similarly, information sent to or received by an entity may be sent to or received by an element (e.g., one or more processors, memories, or interfaces) of the respective node. 
     In some cases, the example cryptographic protocols  300 ,  400  can be modified, combined or extended. For example, in the example protocols  300 ,  400 , each entity&#39;s private key is represented by a single integer (α for Alice, β for Bob). However, private keys for supersingular isogeny-based cryptosystems can have another form. For instance, a private key may have the form (α 1 , α 2 ) for some integers α 1  and α 2 . However, it is possible to choose the private key of the form (1, α) or (α, 1), so that it is given by a single integer α. As another example,  FIGS. 3A-3B and 4A-4B  show operations in which Alice validates Bob&#39;s public key. The protocols  300 ,  400  can be modified such that, additionally or alternatively, Bob validates Alice&#39;s public key using analogous operations. 
     In some implementations, the protocols  300 ,  400  could be merged, for example, to form a hybrid of the two protocols. For instance, Bob may send his secret generator in place of the random seed. In turn, instead of using two isogeny evaluations, Alice may use one pairing computation and one isogeny evaluation. In this case, Alice would verify, for example, whether e 2     n    (U,V)=e 2     n   (P A ,Q A ) 3     m    holds. The protocols  300 ,  400  may be merged in another manner. 
       FIGS. 3A-3B  are flow diagrams showing an example supersingular isogeny-based cryptographic protocol  300 . The example protocol  300  shown in  FIGS. 3A-3B  can be performed, for example, by computer systems that can exchange information over a communication network. For instance, operations in the protocol  300  may be performed by the nodes  102 ,  104  in the example communication system  100  shown in  FIG. 1  or in another type of system. The example protocol  300  may include additional or different operations, including operations performed by additional or different entities, and the operations may be performed in the order shown or in another order. In some cases, one or more of the operations shown in  FIGS. 3A-3B  are implemented as processes that include multiple operations, sub-processes or other types of routines. In some cases, operations can be combined, performed in parallel, iterated or otherwise repeated or performed in another manner. 
     The example protocol  300  shown in  FIGS. 3A-3B  includes operations performed by nodes  302 A,  302 B. In the example shown, the nodes  302 A,  302 B represent two distinct entities in a supersingular isogeny-based cryptosystem. The two distinct entities are referred to as “Alice” and “Bob” in  FIGS. 3A-3B . In the example shown, the nodes  302 A,  302 B exchange public data, and each node uses the public data provided by the other node to execute the cryptography protocol  300 . In some cases, the nodes  302 A,  302 B may have a server-client relationship, a peer-to-peer relationship or another type of relationship. 
     In some examples, the protocol  300  is secure against quantum-enabled adversaries such as, for example, the quantum-enabled adversary  108  shown in  FIG. 1 . For instance, in some cases, the example protocol  300  is secure against certain types of attacks or other processes that can be performed by a quantum-enabled adversary who has access to public information exchanged between the nodes  302 A,  302 B. The example protocol  300  may also provide security against classically-enabled adversaries who do not have access to quantum computers or other quantum resources. 
     At the beginning of the protocol  300 , or before the protocol  300  is initiated, the nodes  302 A,  302 B receive global system parameters for a supersingular isogeny-based cryptosystem. For example, the nodes  302 A,  302 B may perform one or more of the operations of the cryptosystem setup  210 A,  210 B described with respect to  FIG. 2 , or the global system parameters may be obtained in another manner. 
     In the example shown in  FIGS. 3A-3B , the global system parameters obtained by the nodes  302 A,  302 B include the parameters p, E, P A ,Q A , P B ,Q B , l A , l B , f, n and m described above with respect to  FIG. 2 . In some examples described here, l A =2 and l B =3, and p=2 n 3 m f−1, with f being coprime to 2 and 3, such that 2 n ≈3 m . The techniques in  FIGS. 3A-3B  can be adapted to other values. In the examples shown in  FIGS. 3A-3B , Alice works over the set E[2 n ], and Bob works over the set E[3 m ]. The respective set of points used by each entity can be established by agreement between the entities, by selection of one of the entities (e.g., the entity that initiates the protocol  300  can make a selection), based on a relationship of the entities (e.g., server-client), or otherwise before or during execution of the protocol  300 . 
     In the example protocol  300 , a number of values are obtained by each of the nodes  302 A,  302 B. For example, the nodes  302 A,  302 B each obtain integers, elliptic curves, image curves, elliptic curve points, image points, and various representations of these and other cryptographic values in the various operations shown in  FIGS. 3A-3B . Generally, each of these values can be computed or otherwise obtained in any suitable manner, and each of these values can be stored or represented in any suitable form or format. 
     In some instances, a node  302 A or  302 B obtains or computes a value by retrieving the value from a remote or local memory or from another source; by invoking a specialized co-processor (e.g., a pseudorandom number generator, a cryptographic co-processor, a graphics processing unit, etc.) or another system to compute the value; by directly computing the value (e.g., by operation of a processor programmed by software, or another type of processor that is otherwise configured, to perform a computation that produces the value); or otherwise. In some examples, precomputed values, global system values of the cryptosystem, and other values can be received from memory (e.g., volatile or non-volatile memory); random integers (e.g., α, β, etc.) or other random values can be received from a pseudorandom generator or another source; elliptic curve points, image curves, isogenies or values can be computed by a cryptographic co-processor, a general-purpose processor, or another type of processor. 
     As shown in  FIG. 3A , the node  302 A performs operations  310 ,  312  and  314  to produce a public-private key pair for the first entity (“Alice”), and the node  302 B performs operations  316 ,  318  and  320  to produce a public-private key pair for the second entity (“Bob”). Each node  302 A,  302 B may perform its respective operations to generate the public-private key pairs in parallel (e.g., potentially at the same time) or in series, and the operations may be performed independent of, or in response to, information from the other node. In some examples, node  302 A generates Alice&#39;s public-private key pair first, and then node  302 B generates Bob&#39;s public-private key pair after receiving Alice&#39;s public key at  322 . The operations may be performed in another order, or in response to other conditions. 
     At  310 , the node  302 A obtains a random integer α, such that 0≤α≤2 n . Generally, the random integer can be in the range 0≤α&lt;l A   n , for any appropriate value of l A   n . The random integer α is kept secret, as Alice&#39;s secret key. In some cases, Alice uses the random integer α as a static private key or as an ephemeral private key. At  312 , the node  302 A obtains elliptic curve point G A =P A +[α]Q A . Here, the pair of elliptic curve points (P A ,Q A ) is a global system parameter of the supersingular isogeny-based cryptosystem, and the elliptic curve point G A  is a generator of the cyclic subgroup  G A   . Here, [α]Q A  denotes scalar point multiplication on the elliptic curve, where the point Q A  is added to itself α times. 
     At  314 , the node  302 A generates Alice&#39;s public key. In the example shown in  FIG. 3A , to generate Alice&#39;s public key, the node  302 A computes an image curve E A , and a pair of elliptic curve points ϕ A (P B ), ϕ A (Q B )). Here, the pair of elliptic curve points (P B ,Q B ) is a global system parameter of the supersingular isogeny-based cryptosystem. In this example, the image curve E A =E/ G A    is the elliptic curve that is the image curve under the isogeny ϕ A ; ϕ A (P B ) is an elliptic curve point that is the image of P B  under the isogeny ϕ A ; and ϕ A (Q B ) is an elliptic curve point that is the image of Q B  under the isogeny ϕ A . 
     In the example shown in  FIGS. 3A-3B , the isogeny ϕ A : E→E A  is an isogeny of degree 2 n  with the kernel  G A   . An isogeny is generally defined by its kernel, and the generator of the kernel uniquely determines the isogeny. As such, the elliptic curve point G A  uniquely determines the isogeny ϕ A . The degree of an isogeny generally refers the order of its kernel, or equivalently, the order of the point that generates the kernel. Thus, the degree of the isogeny ϕ A  is the order of the kernel  G A   , which is the order of the elliptic curve point G A . The isogeny ϕ A  and the elliptic curve point G A  can be maintained as secret information of Alice. 
     The image curve E A  and image points ϕ A (P B ), ϕ A (Q B ) can be computed in any suitable manner. In some examples, the supersingular isogeny-based cryptosystem utilizes exponentially-large degree isogenies (e.g., 2 n , 3 m , etc.), and it may be infeasible or inefficient to directly compute such isogenies. However, an isogeny of degree 2 n  can be computed as the composition of n isogenies of degree 2; similarly, an isogeny of degree 3 m  can be computed as the composition of m isogenies of degree 3. Smaller degree isogenies (e.g., isogenies of degree 2, 3, 5, etc.) can be evaluated (e.g., to compute image curves and image points, etc.) efficiently, for example, using Vélu&#39;s formulas. Moreover, in some cases, isogeny evaluation at an elliptic curve point takes place while computing the image curve. For example, evaluating the elliptic curve E under the isogeny ϕ A  (to compute the image curve E A ) can include evaluating the elliptic curve points (P B ,Q B ) under the isogeny ϕ A  to compute the image points ϕ A (P B ), ϕ A (Q B ). The image curve E A  can be stored in any suitable manner, for example, an image curve can be represented by its coefficients. For instance, Montgomery curves can be represented using two elements in the field of definition. 
     At  316 , the node  302 B obtains a random integer β, such that 0≤β&lt;3 m . Generally, the random integer can be in the range 0≤α&lt;l B   m , for any appropriate value of l B   m . The random integer β is kept secret, as Bob&#39;s secret key. In some cases, Bob uses the random integer β as a static private key or as an ephemeral private key. At  318 , the node  302 B obtains an elliptic curve point G B =P B +[β]Q B . As noted, the pair of elliptic curve points (P B ,Q B ) is a global system parameter of the supersingular isogeny-based cryptosystem, and the elliptic curve point G B  is a generator of the cyclic subgroup  G B   . Here, [β]Q B  denotes scalar point multiplication on the elliptic curve, where the point Q B  is added to itself β times. 
     At  320 , the node  302 B generates Bob&#39;s public key. In the example shown in  FIG. 3A , to generate Bob&#39;s public key, the node  302 B computes an image curve E B , and a pair of elliptic curve points ϕ B  (P A ), (ϕ B  (Q A ). As noted, the pair of elliptic curve points (P A ,Q A ) is a global system parameter of the supersingular isogeny-based cryptosystem. In this example, the image curve E B =E/ G B    is the elliptic curve that is the image curve under the isogeny ϕB; ϕ B  (P A ) is an elliptic curve point that is the image of P A  under the isogeny ϕ B ; and ϕ B  (Q A ) is an elliptic curve point that is the image of Q A  under the isogeny ϕ B . In the example shown in  FIGS. 3A-3B , the isogeny ϕ B : E→E B  is an isogeny of degree 3 m  with the kernel  G B   . The image curve E B  and image points ϕ B (P A ), ϕ B (Q A ) can be computed and stored at  320  in any suitable manner, using the techniques discussed above with respect to generating Alice&#39;s public key at  314 . 
     At  322 , the node  302 A sends Alice&#39;s public key, and possibly other information, to the other node  302 B, and the other node  302 B receives the information sent by the node  302 A. In the example shown in  FIGS. 3A-3B , the set of values (E A , ϕ A (P B ), ϕ A (Q B )) represents Alice&#39;s public key. In the example shown in  FIGS. 3A-3B , the node  302 A may send information directly to the node  302 B, or the node  302 A may initiate transmission indirectly, for example, through a communication device or otherwise. Moreover, information may be sent in multiple transmissions or a single transmission over one or more communication networks or other channels. All or part of the information can be transmitted over a public channel, and may be observed by a quantum-enabled adversary or another type of adversary. 
     At  324 , the node  302 B obtains Alice&#39;s public key. For example, the node  302 B may obtain Alice&#39;s public key from the node  302 A, from memory or another remote or local source. At  326 , the node  302 B computes an image curve E AB  under the isogeny ψ B :E A →E AB . Here, the isogeny ψ B  is an isogeny of degree 3 m  with kernel  ϕ A (P B )+[β]ϕ A (Q B ) . The image curve E AB  is computed based on the image curve E A  and the image points ϕ B (P A ), ϕ B (Q A ) from Alice&#39;s public key. The image curve E AB  can be computed (e.g., using Vélu&#39;s formulas) and stored (e.g., as coefficients or element in the field definition) using the techniques discussed above with respect to the generation of Alice&#39;s public key at  314 . 
     At  328 , the node  302 B computes a shared secret value based on the image curve E AB . The shared secret value is “shared” in the sense that the secret value is known (or to be known) by Alice and Bob. In the example shown in  FIGS. 3A-3B , the shared secret is the j-invariant j(E AB ) of the image curve E AB . The j-invariant of an elliptic curve is an element of the underlying finite field F p     2   , and it can be computed, for example, from the coefficients that define the elliptic curve. For example, the j-invariant of a Montgomery curve (By 2 =x 3 +Ax 2 +x) is given by j=256(A 2 −3) 2 /(A 2 −A). In this example, the j-invariant j(E AB ) can be represented as a pair of integer values each between 0 and p. In some implementations, the j-invariant can be computed or stored in another manner. In some cases, another value is used as the shared secret, for instance, another value that is based on or related to the j-invariant j(E AB ) of the image curve E AB . 
     At  330 , the node  302 B computes a session key SK and a verification key VK. The session key SK and the verification key VK are configured for use in a symmetric key encryption scheme, such as, for example, AES or another type of symmetric key encryption protocol. In the example shown in  FIGS. 3A-3B , the session key SK and the verification key VK are computed based on the shared secret (computed at  328 ). In some implementations, the session key SK and the verification key VK may be computed from the output of a key derivation function or another type of function applied to the shared secret value. For example, the session key SK and the verification key VK may be computed by parsing SK∥VK=KDF(j(E AB )), where KDF represents a key derivation function and SK∥VK represents the concatenation of the session key SK and the verification key VK. In some cases, the key derivation function KDF can be implemented using HMAC or another type of cryptographic hash function. 
     At  332 , the node  302 B computes an encrypted generator point C B . In the example shown in  FIGS. 3A-3B , the encrypted generator point C B  is an encrypted version of Bob&#39;s generator point G B , which the node  302 B obtained at  318  as part of the key generation process that produced Bob&#39;s public-private key pair. In particular, Bob&#39;s generator point G B  was computed based on Bob&#39;s secret integer β, and was used to produce Bob&#39;s public key (E B , ϕ B (P A ), ϕ B (Q A )). The encrypted generator point C B  is computed using the symmetric key SK and the verification key VK (computed at  330 ) in a symmetric key encryption function applied to Bob&#39;s generator point G B . For instance, the encrypted generator point C B  may be computed as C B =Enc VK (G B ⊕SK), where Enc represents the symmetric key encryption function (e.g., AES or other), and ⊕ denotes the exclusive-or (“XOR”) operation. The encrypted generator point C B  may be computed in another manner. 
     At  334 , the node  302 B sends Bob&#39;s public key and encrypted generator point C B , and possibly other information, to the other node  302 A, and the other node  302 A receives the information sent by the node  302 B. In the example shown in  FIGS. 3A-3B , the set of values (E B , ϕ B (P A ), ϕ B (Q A )) represents Bob&#39;s public key. In the example shown in  FIGS. 3A-3B , the node  302 B may send information directly to the node  302 A, or the node  302 B may initiate transmission indirectly, for example, through a communication device or otherwise. Moreover, information may be sent in multiple transmissions or a single transmission over one or more communication networks or other channels. All or part of the information can be transmitted over a public channel, and may be observed by a quantum-enabled adversary or another type of adversary. 
     At  336 , the node  302 A obtains Bob&#39;s public key. For example, the node  302 A may obtain Bob&#39;s public key from the node  302 B, from memory or another remote or local source. In the example shown in  FIGS. 3A-3B , the set of values (E B ,U,V) represents Bob&#39;s public key as obtained by the node  302 A at  336 . If Bob is honest and the node  302 A obtains an accurate and valid version of Bob&#39;s public key, then U=ϕ B (P A ) and V=ϕ B (Q A ). However, the node  302 B may provide an inaccurate or otherwise invalid public key, or the node  302 A may obtain a public key that has been otherwise corrupted. For instance, if Bob is dishonest or if the node  302 B uses an invalid process to generate Bob&#39;s public-private key pair, the node  302 B may publish an invalid public key, where U≠ϕ B (P A ) or V≠ϕ B  (Q A ). Accordingly, in the example shown in  FIGS. 3A-3B , the node  302 A performs certain operations to validate the public key (E B ,U,V), for instance, to improve integrity and security of the protocol  300 . In some implementations, the validation operations performed by the node  302 A may thwart certain attacks on the cryptosystem and thereby prevent Bob or another adversary from gaining information about Alice&#39;s secret key (the secret integer α). 
     At  338 , the node  302 A computes an image curve E BA  under the isogeny ψ A : E B →E BA . Here, the isogeny ψ A  is an isogeny of degree 2 n  with kernel  U+[α]V . The image curve E BA  is computed based on the image curve E B  and the elliptic curve points U, V from Bob&#39;s public key obtained at  336 . The image curve E BA  can be computed (e.g., using Vélu&#39;s formulas) and stored (e.g., as coefficients or element in the field definition) using the techniques discussed above with respect to the generation of Alice&#39;s public key at  314 . 
     At  340 , the node  302 A computes the shared secret value based on the image curve E BA , and the shared secret value is now known by both Alice and Bob. In the example shown in  FIGS. 3A-3B , the shared secret is computed at  340  by computing the j-invariant j(E BA ) of the image curve E BA , which is identical to the j-invariant j(E AB ) computed at  328 . The node  302 A computes the shared secret value at  340  using a process that is analogous to the process used by the node  302 B to compute the shared secret value at  328 . For example, the j-invariant j(E BA ) can be computed and stored by the node  302 A as described with respect to the j-invariant j(E AB ) computed at  328 . In some cases, another value is used as the shared secret, for instance, another value that is based on or related to the j-invariant j(E BA ) of the image curve E BA . 
     At  342 , the node  302 A computes a session key SK′ and a verification key VK′. The session key SK′ and the verification key VK′ are configured for use in a symmetric key encryption scheme, such as, for example, AES or another type of symmetric key encryption protocol. The session key SK′ and the verification key VK′ are computed at  342  in the same manner that the session key SK and the verification key VK are computed at  330 , using analogous operations. In the example shown in  FIGS. 3A-3B , the session key SK′ and the verification key VK′ are computed based on the shared secret (computed at  340 ). In some implementations, the session key SK′ and the verification key VK′ may be computed from the output of a key derivation function or another type of function applied to the shared secret value. For example, the session key SK′ and the verification key VK′ may be computed by parsing SK′∥VK′=KDF(j(E BA )), where KDF represents the key derivation function used at  330  and SK′∥VK′ represents the concatenation of the session key SK′ and the verification key VK′. 
     At  344 , the node  302 A obtains the encrypted generator point C B  that was computed by the node  302 B at  332 . For example, the node  302 A may obtain the encrypted generator point C B  from the node  302 B, from memory or another remote or local source. 
     At  346 , the node  302 A computes a decrypted generator point G B ′ based on encrypted generator point C B . In the example shown in  FIGS. 3A-3B , the decrypted generator point G B ′ is a decrypted version of the encrypted generator point C B  sent by Bob at  334 . The decrypted generator point G B ′ is computed using the symmetric key SK′ and the verification key VK′ (computed at  342 ) in a symmetric key decryption function applied to the encrypted generator point C B . The symmetric key decryption function applied at  346  to decrypt the encrypted generator point C B  corresponds to the symmetric key encryption function applied at  332  to encrypt Bob&#39;s generator point G B . For instance, the decrypted generator point G B ′ may be computed as G B ′=Dec VK′ (C B )⊕SK′, where Dec represents the symmetric key decryption function (e.g., AES or other), and ⊕ denotes the exclusive-or (“XOR”) operation. The decrypted generator point G B ′ may be computed in another manner. 
     In the example shown in  FIGS. 3A-3B , the node  302 A performs operations  348 ,  350 ,  352 ,  354 , and possibly other operations to validate Bob&#39;s public key (E B ,U,V). In some instances, the process of validating Bob&#39;s public key determines that Bob&#39;s public key is invalid, and therefore, should be rejected. In such cases, the node  302 A may determine that Alice&#39;s private key α has been potentially compromised or is otherwise vulnerable, and as such, may revoke or discard the public-private key pair generated at  310 ,  312 ,  314  and terminate the protocol  300 . Bob&#39;s public key (E B ,U,V) may be deemed invalid by the node  302 A if any of the validations or verifications performed at  350 ,  352  or  354  return a false value (e.g., if compared values do not match) or are otherwise not confirmed true. In some instances, the process of validating Bob&#39;s public key determines that Bob&#39;s public key is valid, and therefore, can be accepted. In such cases, the node  302 A may determine that Alice&#39;s private key α can be reused without compromise or vulnerability, and as such, may recycle the public-private key pair generated at  310 ,  312 ,  314 . Bob&#39;s public key (E B ,U,V) may be deemed valid by the node  302 A if all the validations and verifications performed at  350 ,  352  or  354  return a true value (e.g., if all compared values match). In some implementations, Bob&#39;s public key (E B ,U,V) is validated in another manner. 
     At  348 , node  302 A computes check values (E B ′, ϕ B ′(P A ), ϕ B ′(Q A )) based on the decrypted generator G B ′. In the example shown in  FIGS. 3A-3B , the check values (E B ′, ϕ B ′(P A ), ϕ B ′(Q A )) are computed from the decrypted generator point G B ′ at  348  using the operations that were used to compute Bob&#39;s public key (E B , ϕ B (P A ), ϕ B (Q A )) from the generator point G B  at  320 . For example, the node  302 A computes the image curve E B ′ from the decrypted generator point G B ′, and the pair of elliptic curve points ϕ B ′(P A ), ϕ B ′(Q A ) from the elliptic curve points (P A ,Q A ). In this example, the image curve E B ′=E/ G B ′  is the elliptic curve that is the image curve under the isogeny ϕ B ′; ϕ B ′(P A ) is an elliptic curve point that is the image of P A  under the isogeny ϕ B ′; and ϕ B ′(Q A ) is an elliptic curve point that is the image of Q A  under the isogeny ϕ B ′. In the example shown in  FIGS. 3A-3B , the isogeny ϕ B ′:E→E B ′ is an isogeny of degree 3 m  with the kernel  G B ′ . The image curve E B ′ and image points ϕ B ′(P A ), ϕ B ′(Q A ) can be computed and stored at  348  in any suitable manner, using the techniques discussed above with respect to generating Alice&#39;s public key at  314 . 
     At  350 , the node  302 A validates the degree of the isogeny ϕ B ′ defined by the kernel  G B ′  identified by the decrypted generator point G B ′. The degree of the isogeny can be validated, for example, by verifying that deg(ϕ B ′)=l B   m , where “deg” denotes the degree. In the example shown in  FIGS. 3A-3B , the node  302 A explicitly verifies whether deg(ϕ′ B )=3 m , and if not, Bob&#39;s public key (E B ,U,V) is deemed invalid. Here, the degree of the isogeny ϕ′ B  is the order of the kernel  G B ′ , which is the order of the decrypted generator point G B ′. The validation performed at  350  can detect certain types of attacks. For example, the node  302 B can detect if Bob cheats by sending G B ′ of order not equal to l B   m . 
     At  352 , the node  302 A validates the value j(E B ), which is the j-invariant of the image curve E B  in Bob&#39;s public key (E B ,U,V). In the example shown in  FIGS. 3A-3B , the node  302 A verifies that j(E B )≠0, 1728, and if not, Bob&#39;s public key (E B ,U,V) is deemed invalid. In other words, if the node  302 A determines that j(E B )=0 or j(E B )=1728, then Bob&#39;s public key (E B ,U,V) is deemed invalid. In some implementations, the validation checks for other values of the j-invariant of the image curve E B  in Bob&#39;s public key. 
     The validation performed at  352  can detect instances of the image curve E B  in Bob&#39;s public key that could compromise security of the shared secret or create other vulnerabilities. In some cases, the validation performed at  352  ensures that the j-invariant of the image curve E B  from Bob&#39;s public key is not a trivially small value. For instance, the values 0 and 1728 are too small for shared secrets and can easily be derived using a brute force attack. In some cases, the validation performed at  352  ensures that the image curve E B  in Bob&#39;s public key is not isomorphic to the initial curve E defined in the global system parameters. For instance, in the example shown in  FIGS. 3A-3B , the initial curve E is y 2 =x 3 +x or y 2 =x 3 −x, both of which have the j-invariant  1728 . Thus, if the j-invariant j(E B ) is 1728, then the image curve E B  is isomorphic to (the same as) the initial curve E, which can compromise security of the protocol  300 . In some cases, the validation performed at  352  ensures that the j-invariant of the image curve E B  in Bob&#39;s public key have small automorphism groups. For instance, curves with j-invariants equal to 0 or 1728 have large automorphism groups, and removing these values may ensure that the image curve E B  has only two automorphisms, namely (x,y)→(x,y) (the identity map), and (x,y)→(x,−y) (the inversion map). 
     At  354 , the node  302 A verifies that the check values (E B ′, ϕ B ′(P A ), ϕ B ′(Q A )) computed at  348  match the corresponding values in Bob&#39;s public key (E B ,U,V) obtained at  336 . In particular, the node  302 A verifies that E B ′=E B ; ϕ B ′(P A )=U; and ϕ B ′(Q A )=V, and if not, Bob&#39;s public key (E B ,U,V) is deemed invalid. In other words, if the node  302 A determines that E B ′≠E B ; ϕ B′ (P A )≠U; or ϕ B ′(Q A )≠V, then Bob&#39;s public key (E B ,U,V) is deemed invalid. 
     Accordingly, if all verifications at  350 ,  352 ,  354  pass, then Bob&#39;s public key (E B ,U,V) can be deemed valid by the node  302 A. In the examples discussed above, the node  302 A verifies that deg(ϕ B ′)=3 m ; j(E B )≠0, 1728; E B ′=E B ; ϕ B ′(P A )=U; and ϕ B ′(Q A )=V. And if the answer is “yes” to all checks (all verifications are “true”), the public key (E B ,U,V) is deemed valid, whereas if all the answer is “no” to any one of the checks (any of the verifications is “false”), the public key (E B ,U,V) is deemed invalid. In some cases, after the node  302 A validates Bob&#39;s public key, the nodes  302 A,  302 B execute a cryptographic correspondence protocol using the shared secret value, for example, as described with respect to  216 A,  216 B in  FIG. 2 . 
       FIGS. 4A-4B  are flow diagrams showing another example supersingular isogeny-based cryptographic protocol. The example protocol  400  shown in  FIGS. 4A-4B  can be performed, for example, by computer systems that can exchange information over a communication network. For instance, operations in the protocol  400  may be performed by the nodes  102 ,  104  in the example communication system  100  shown in  FIG. 1  or in another type of system. The example protocol  400  may include additional or different operations, including operations performed by additional or different entities, and the operations may be performed in the order shown or in another order. In some cases, one or more of the operations shown in  FIGS. 4A-4B  are implemented as processes that include multiple operations, sub-processes or other types of routines. In some cases, operations can be combined, performed in parallel, iterated or otherwise repeated or performed in another manner. 
     The example protocol  400  shown in  FIG. 4A-4B  is similar to the example protocol  300  shown in  FIG. 3A-3B , and many operations that can be performed in the same or similar manner, by the same or similar types of hardware. Generally, analogous operations in the two protocols  300 ,  400  can be performed using the same techniques, unless otherwise noted or implied by context. 
     At the beginning of the protocol  400 , or before the protocol  400  is initiated, the nodes  402 A,  402 B receive global system parameters for a supersingular isogeny-based cryptosystem, as described with respect to  FIGS. 3A-3B . In addition to obtaining the global system parameters and other setup operations described with respect to  FIGS. 3A-3B , the node  402 A in  FIGS. 4A-4B  computes the pairing value e 2     n   (P A ,Q A ) 3     m    at  406 . The pairing value e 2     n   (P A ,Q A ) 3     m    computed at  406  is based on the pair of elliptic curve points (P A ,Q A ), and the values of l A , l B , n and m (here, l A =2 and l B =3) which are all global system parameters defined by the supersingular isogeny-based cryptosystem. Thus, the pairing value e 2     n    (P A ,Q A ) 3     m    can be precomputed by the node  402 A and saved as a system parameter to be reused as needed. In some cases, a pairing value e l     A       n   (P A ,Q A ) l     B       m    is computed based on other values of l A , l B . 
     In the example shown in  FIGS. 4A-4B , the pairing value is obtained at  406  by computing a Weil pairing. Another type of pairing, such as, for example, a Tate pairing, may be used. The Weil pairing e k  takes as an input two points on the elliptic curve and returns an element a in the base field such that a k =1. In the example protocol  400 , k=l A   n , =2 n , and the Weil pairing returns an element in the finite field F p     2    of the form A+i*B, where A and B are integers between 0 and p. The value of the Weil pairing is then raised to power 3 m  to compute the pairing value shown. The value of the Weil pairing may be computed, for example, using the so-called Miller&#39;s algorithm or possibly another technique. 
     As shown in  FIG. 4A , the node  402 A performs operations  410 ,  412  and  414  to produce a public-private key pair for the first entity (“Alice”), and the node  402 B performs operations  408 ,  416 ,  418  and  420  to produce a public-private key pair for the second entity (“Bob”). Each node  402 A,  402 B may perform its respective operations generate the public-private key pairs in parallel (e.g., at the same time) or in series, and the operations may be performed independent of, or in response to, information from the other node. In some examples, node  402 A generates Alice&#39;s public-private key pair first, and then node  402 B generates Bob&#39;s public-private key pair after receiving Alice&#39;s public key at  422 . The operations may be performed in another order, or in response to other conditions. 
     Operations  410 ,  412 ,  414  in  FIG. 4A , which produce Alice&#39;s public-private key pair, can be executed in the manner described with respect to operations  310 ,  312 ,  314  in  FIG. 3A . At  410 , the node  402 A obtains a random integer α, such that 0≤α&lt;2 n . At  412 , the node  402 A obtains elliptic curve point G A =P A +[α]Q A . At  414 , the node  402 A generates Alice&#39;s public key. In the example shown in  FIG. 4A , to generate Alice&#39;s public key, the node  402 A computes an image curve E A , and a pair of elliptic curve points (ϕ A (P B ), ϕ A (ϕ B )), as described with respect to  FIG. 3A . 
     At  406 , the node  402 B obtains a random seed r B . The random seed r B  is chosen randomly. For example, the node  402 B can use a function or program (e.g., provided by an operating system or other computing resource) that generates random values based on environmental noise collected from device drivers and other sources. 
     Operations  416 ,  418 ,  420  in  FIG. 4A , which produce Bob&#39;s public-private key pair, can be executed in the manner described with respect to operations  316 ,  318 ,  320  in  FIG. 3A ; except that  FIG. 4A  shows that the random integer β is obtained at  416  based on the random seed r B  obtained at  408 . For example, the random seed r B  can be used to seed (e.g., to refresh or randomize the state of) a pseudorandom generator, and the random integer β can then be obtained from the seeded pseudorandom generator. At  416 , the node  402 B obtains the random integer β, such that 0≤β&lt;3 m . At  418 , the node  402 B obtains an elliptic curve point G B =P B +[β]Q B . At  420 , the node  402 B generates Bob&#39;s public key. In the example shown in  FIG. 4A , to generate Bob&#39;s public key, the node  402 B computes an image curve E B , and a pair of elliptic curve points ϕ B (P A ), ϕ B (Q A ) as described with respect to  FIG. 3A . 
     At  422 , the node  402 A sends Alice&#39;s public key, and possibly other information, to the other node  402 B, and the other node  402 B receives the information sent by the node  402 A. For example, information may be communicated between the nodes  402 A,  402 B as described with respect to the nodes  302 A,  302 B in  FIG. 3A . 
     Operations  424 ,  426 ,  428 ,  430  in  FIG. 4A  can be executed in the manner described with respect to operations  324 ,  326 ,  328 ,  330  in  FIG. 3A . At  424 , the node  402 B obtains Alice&#39;s public key. At  426 , the node  402 B computes an image curve E AB  under the isogeny ψ B :E A →E AB . At  428 , the node  402 B computes a shared secret value based on the image curve E AB . In the example shown in  FIGS. 4A-4B , the shared secret is the j-invariant j(E AB ) of the image curve E AB , as described with respect to the example shown in  FIGS. 3A-3B . At  430 , the node  402 B computes a session key SK and a verification key VK. The session key SK and the verification key VK are configured for use in a symmetric key encryption scheme, such as, for example, AES or another type of symmetric key encryption protocol. In the example shown in  FIGS. 4A-4B , the session key SK and the verification key VK are computed based on the shared secret value, as described with respect to  FIGS. 3A-3B . 
     At  432 , the node  402 B computes an encrypted seed value C B . In the example shown in  FIGS. 4A-4B , the encrypted seed value C B  is an encrypted version of Bob&#39;s seed value r B , which the node  402 B obtained at  408  as part of the key generation process that produced Bob&#39;s public-private key pair. In particular, Bob&#39;s generator point G B  was computed based on Bob&#39;s seed value r B , and was used to produce Bob&#39;s public key (E B , ϕ B  (P A ), ϕ B  (Q A )). The encrypted seed value C B  is computed using the symmetric key SK and the verification key VK (computed at  430 ) in a symmetric key encryption function applied to the seed value r B . For instance, the encrypted seed value r B  may be computed as C B =Enc VK (r B ⊕SK), where Enc represents the symmetric key encryption function (e.g., AES or other), and ⊕ denotes the exclusive-or (“XOR”) operation. The encrypted seed value C B  may be computed in another manner. 
     At  434 , the node  402 B sends Bob&#39;s public key and encrypted generator point C B , and possibly other information, to the other node  402 A, and the other node  402 A receives the information sent by the node  402 B. For example, information may be communicated between the nodes  402 A,  402 B as described with respect to the nodes  302 A,  302 B in  FIG. 3A . 
     At  436 , the node  402 A obtains Bob&#39;s public key. For example, the node  402 A may obtain Bob&#39;s public key from the node  402 B, from memory or another remote or local source. In the example shown in  FIGS. 4A-4B , the set of values (E B ,U,V) represents Bob&#39;s public key as obtained by the node  402 A at  436 . If Bob is honest and the node  402 A obtains an accurate and valid version of Bob&#39;s public key, then U=ϕ B  (P A ) and V=ϕ B (Q A ). As described with respect to  FIGS. 3A-3B , the node  402 A may obtain an invalid public key, where U≠ϕ B (P A ) or V≠ϕ B (Q A ). Accordingly, in the example shown in  FIGS. 4A-4B , the node  402 A performs certain operations to validate the public key (E B ,U,V), for instance, to improve integrity and security of the protocol  400 . In some implementations, the validation operations performed by the node  402 A may thwart certain attacks on the cryptosystem and thereby prevent Bob or another adversary from gaining information about Alice&#39;s secret key (the secret integer α). 
     At  437 , the node  402 A computes another pairing value e 2     n   (U,V) and verifies whether e 2     n   (U,V)=e 2     n    (P A ,Q A ) 3     m   . In other words, the node  402 A verifies whether the first pairing value obtained (at  406 ) from the global system parameters matches the second pairing value obtained from the pair of elliptic curve points in Bob&#39;s public key. In some cases, the pairing value e 2     n   (U,V) is computed to verify whether e l     A       n   (U,V)=e l     A       n   (P A ,Q A ) l     B       m    based on other values of l A , l B . In the example shown in  FIGS. 4A-4B , the second pairing value is obtained at  447  by computing a Weil pairing. Another type of pairing, such as, for example, a Tate pairing, may be used. The Weil pairing may be computed, for example, using the so-called Miller&#39;s algorithm or possibly another technique. Generally, the same type of pairing calculation is used at  406  (to compute e 2     n   (P A ,Q A ) 3     m   ) and  447  (to compute e 2     n   (U,V)). In the example shown in  FIGS. 4A-4B , the node  402 A verifies that e 2     n   (U,V)=e 2     n   (P A ,Q A ) 3     m   , and if not, Bob&#39;s public key (E B ,U,V) is deemed invalid. In other words, if the node  402 A determines that e 2     n   (U,V)≠e 2     n   (P A ,Q A ) 3     m   , then Bob&#39;s public key (E B ,U,V) is deemed invalid. As such, in the example shown in  FIGS. 4A-4B , an invalid public key may be identified by the node  402 A at  437 , and the protocol  400  could then be terminated without performing further operations (e.g., one or more of  438 ,  440 ,  442 ,  444 ,  446 ,  447 ,  448 ,  454 ). 
     At  438 , the node  402 A computes an image curve E BA  under the isogeny ψ A :E B →E BA . The image curve E BA  may be computed at  438  as described with respect to operation  338  in  FIG. 3B . At  440 , the node  402 A computes the shared secret value based on the image curve E BA , and the shared secret value is now known by both Alice and Bob. In the example shown in  FIGS. 4A-4B , the shared secret is computed at  440  by computing the j-invariant j(E BA ) of the image curve E BA , which is identical to the j-invariant j(E AB ) computed at  428 . The node  402 A computes the shared secret value at  440  using a process that is analogous to the process used by the node  402 B to compute the shared secret value at  428 . In some cases, another value is used as the shared secret, for instance, another value that is based on or related to the j-invariant j(E BA ) of the image curve E BA . 
     At  442 , the node  402 A computes a session key SW and a verification key VK′. The session key SW and the verification key VK′ are configured for use in a symmetric key encryption scheme, such as, for example, AES or another type of symmetric key encryption protocol. The session key SW and the verification key VK′ are computed at  442  in the same manner that the session key SK and the verification key VK are computed at  430 , using analogous operations. In the example shown in  FIGS. 4A-4B , the session key SK′ and the verification key VK′ are computed based on the shared secret (computed at  440 ). In some implementations, the session key SK′ and the verification key VK′ may be computed as described with respect to operation  342  in  FIG. 3B . 
     At  444 , the node  402 A obtains the encrypted seed value C B  that was computed by the node  402 B at  432 . For example, the node  402 A may obtain the encrypted seed value C B  from the node  402 B, from memory or another remote or local source. 
     At  446 , the node  402 A computes a decrypted seed value r B ′ based on encrypted seed value C B . In the example shown in  FIGS. 4A-4B , the decrypted seed value r B ′ is a decrypted version of the encrypted seed value C B  sent by Bob at  434 . The decrypted seed value r B ′ is computed using the symmetric key SW and the verification key VK′ (computed at  442 ) in a symmetric key decryption function applied to the encrypted seed value C B . The symmetric key decryption function applied at  446  to decrypt the encrypted seed point C B  corresponds to the symmetric key encryption function applied at  432  to encrypt Bob&#39;s random seed r B . For instance, the decrypted seed value r B ′ may be computed as r B ′=Dec VK′ (C B )⊕SK′, where Dec represents the symmetric key decryption function (e.g., AES or other), and ⊕ denotes the exclusive-or (“XOR”) operation. The decrypted generator point G B ′ may be computed in another manner. 
     At  447 , the node  447  computes the generator point G B ′ from the decrypted seed value r B ′. The generator point G B ′ can be computed (at  447 , by the node  402 A) from the decrypted seed value r B ′ using the same operations that were used (at  416 ,  418 , by the node  402 B) to generate the elliptic curve point G B  from the seed value r B . For example, the node  402 A can compute an integer β′=PRF(r B ′), and then compute G B ′=P B +[β′]Q B . 
     In the example shown in  FIGS. 4A-4B , the node  402 A performs operations  437 ,  448 ,  454 , and possibly other operations to validate Bob&#39;s public key (E B ,U,V). In some instances, the process of validating Bob&#39;s public key determines that Bob&#39;s public key is invalid, and therefore, should be rejected. In such cases, the node  402 A may determine that Alice&#39;s private key α has been potentially compromised or is otherwise vulnerable, and as such, may revoke or discard the public-private key pair generated at  410 ,  412 ,  414  and terminate the protocol  400 . Bob&#39;s public key (E B ,U,V) may be deemed invalid by the node  402 A if any of the validations or verifications performed at  437  or  454  return a false value (e.g., if compared values do not match) or are otherwise not confirmed true. In some instances, the process of validating Bob&#39;s public key determines that Bob&#39;s public key is valid, and therefore, can be accepted. In such cases, the node  402 A may determine that Alice&#39;s private key α can be reused without compromise or vulnerability, and as such, may recycle the public-private key pair generated at  410 ,  412 ,  414 . Bob&#39;s public key (E B ,U,V) may be deemed valid by the node  402 A if all the validations and verifications performed at  437  and  454  return a true value (e.g., if all compared values match). In some implementations, Bob&#39;s public key (E B ,U,V) is validated in another manner. 
     At  448 , node  402 A computes check values (E B ′, ϕ B ′(Q A )) based on the generator point G B ′ computed at  446 . In the example shown in  FIGS. 4A-4B , the check values (E B ′, ϕ B ′(Q A )) are computed from the generator point G B ′ at  448  using some of the operations that were used to compute Bob&#39;s public key (E B ϕ B (P A ), ϕ B (Q A )) from the generator point G B  at  420 . For example, the node  402 A computes the image curve E B ′ from the generator point G B ′, and the elliptic curve point ϕ B ′(Q A ) from the elliptic curve point Q A . In this example, the image curve E B ′=E/ G B ′  is the elliptic curve that is the image curve under the isogeny ϕ B ′; and ϕ B ′(Q A ) is an elliptic curve point that is the image of Q A  under the isogeny ϕ B ′. In the example shown in  FIGS. 4A-4B , the isogeny ϕ B ′: E→E B ′ is an isogeny of degree 3 m  with the kernel  G B ′ . The image curve E B ′ and image points ϕ B ′(P A ), ϕ B ′(Q A ) can be computed and stored at  448  in any suitable manner, using the techniques discussed above with respect to generating Alice&#39;s public key at  414 . 
     At  454 , the node  402 A verifies that the check values (E B ′,ϕ B ′(Q A )) computed at  448  match the corresponding values (E B ,V) from Bob&#39;s public key obtained at  436 . In particular, the node  402 A verifies that E B ′=E B  and ϕ B ′(Q A )=V, and if not, Bob&#39;s public key (E B ,U,V) is deemed invalid. In other words, if the node  402 A determines that E B ′≠E B  or ϕ B ′(Q A ) # V, then Bob&#39;s public key (E B ,U,V) is deemed invalid. 
     Accordingly, if all verifications at  447 ,  454  pass, then Bob&#39;s public key (E B ,U,V) can be deemed valid by the node  402 A. In the examples discussed above, the node  402 A verifies that e 2     n   (U,V)=e 2     n   (P A ,Q A ) 3     m   , E B ′=E B , and ϕ B ′(Q A )=V; and if the answer is “yes” to all checks (all verifications are “true”), the public key (E B ,U,V) is deemed valid, whereas if all the answer is “no” to any one of the checks (any of the verifications is “false”), the public key (E B ,U,V) is deemed invalid. In some cases, after the node  402 A validates Bob&#39;s public key, the nodes  402 A,  402 B execute a cryptographic correspondence protocol using the shared secret value, for example, as described with respect to  216 A,  216 B in  FIG. 2 . 
     The protocol  400  shown in  FIGS. 4A-4B  can be modified or extended. As an example, instead of verifying whether ϕ B ′(Q A )=V holds, Alice could verify whether ϕ B ′([γ]P A +[δ]Q A )=[γ]U+[δ]V holds for some fixed values γ and δ such that 0≤γ,δ&lt; 2   n . However, the secret key α would depend on the values of γ and δ, so Alice would choose α carefully. For example, if Alice picks γ=1 and δ=0, then analysis shows that a should be odd, and if Alice picks γ=1 and δ=1, then a should be even. As another example, instead of verifying whether e 2     n   (U,V)=e 2     n   (P A ,Q A ) 3     m    holds, Alice could verify whether e 2     n   ([a]U+[b]V, [c]U+[d]V)=e 2     n   (P A ,Q A ) 3     m     (ad-bc)  holds for some fixed values a, b, c and d such that 0≤a,b,c,d&lt;2 n . As another example, it is also possible to replace the Weil pairing e k (.,.) with another pairing t k (.,.), such as the Tate pairing, or another pairing that possesses the property t k (ϕ(P), ϕ(Q))=t k (P,Q) deg(ϕ) , where deg(ϕ) denotes the degree of an isogeny ϕ. 
     Some of the subject matter and operations described in this specification can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Some of the subject matter described in this specification can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions, encoded on a computer storage medium for execution by, or to control the operation of, data-processing apparatus. A computer storage medium can be, or can be included in, a computer-readable storage device, a computer-readable storage substrate, a random or serial access memory array or device, or a combination of one or more of them. Moreover, while a computer storage medium is not a propagated signal, a computer storage medium can be a source or destination of computer program instructions encoded in an artificially generated propagated signal. The computer storage medium can also be, or be included in, one or more separate physical components or media (e.g., multiple CDs, disks, or other storage devices). 
     Some of the operations described in this specification can be implemented as operations performed by a data processing apparatus on data stored on one or more computer-readable storage devices or received from other sources. 
     The term “data-processing apparatus” encompasses all kinds of apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, a system on a chip, or multiple ones, or combinations, of the foregoing. The apparatus can include special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). The apparatus can also include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, a cross-platform runtime environment, a virtual machine, or a combination of one or more of them. 
     A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, declarative or procedural languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, object, or other unit suitable for use in a computing environment. A computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program, or in multiple coordinated files (e.g., files that store one or more modules, sub programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network. 
     Some of the processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform actions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). 
     Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random-access memory or both. Elements of a computer can include a processor that performs actions in accordance with instructions, and one or more memory devices that store the instructions and data. A computer may also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., non-magnetic drives (e.g., a solid-state drive), magnetic disks, magneto optical disks, or optical disks. However, a computer need not have such devices. Moreover, a computer can be embedded in another device, e.g., a phone, an electronic appliance, a mobile audio or video player, a game console, a Global Positioning System (GPS) receiver, an Internet-of-Things (IoT) device, a machine-to-machine (M2M) sensor or actuator, or a portable storage device (e.g., a universal serial bus (USB) flash drive). Devices suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices (e.g., EPROM, EEPROM, flash memory devices, and others), magnetic disks (e.g., internal hard disks, removable disks, and others), magneto optical disks, and CD ROM and DVD-ROM disks. In some cases, the processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry. 
     To provide for interaction with a user, operations can be implemented on a computer having a display device (e.g., a monitor, or another type of display device) for displaying information to the user and a keyboard and a pointing device (e.g., a mouse, a trackball, a tablet, a touch sensitive screen, or another type of pointing device) by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user&#39;s client device in response to requests received from the web browser. 
     A computer system may include a single computing device, or multiple computers that operate in proximity or generally remote from each other and typically interact through a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), an inter-network (e.g., the Internet), a network comprising a satellite link, and peer-to-peer networks (e.g., ad hoc peer-to-peer networks). A relationship of client and server may arise by virtue of computer programs running on the respective computers and having a client-server relationship to each other. 
     In a general aspect of what is described above, a supersingular isogeny-based cryptography process is performed. In some aspects, an entity validates another entity&#39;s public key. In some aspects, an entity provides its public key and further information to another entity, to enable the other entity to validate its public key. In some cases, a public key is validated in a manner that improves computational efficiency of a cryptographic protocol, improves security or integrity of a cryptographic protocol, or provides other technical advantages. 
     In a first example, a first public key of a first entity (e.g., “Alice” in the example shown in  FIGS. 3A-3B ) is received. The first public key comprises a first image curve (e.g., E A  in the example shown in  FIGS. 3A-3B ) and a first pair of elliptic curve points (e.g., ϕ A (P B ), ϕ A (Q B )) in the example shown in  FIGS. 3A-3B ). The first pair of elliptic curve points represent an image of a second pair of elliptic curve points (e.g., (P B ,Q B ) in the example shown in  FIGS. 3A-3B ) under a first isogeny (e.g., ϕ A  in the example shown in  FIGS. 3A-3B ). A secret integer (e.g., β in the example shown in  FIGS. 3A-3B ) of a second entity (e.g., “Bob” in the example shown in  FIGS. 3A-3B ) is obtained. A second public key of the second entity is generated based on the secret integer. The second public key comprises a second image curve (e.g., E B  in the example shown in  FIGS. 3A-3B ) and a third pair of elliptic curve points (e.g., ϕ B  (P A ), ϕ B  (Q A )) in the example shown in  FIGS. 3A-3B ). The third pair of elliptic curve points represent an image of a fourth pair of elliptic curve points (e.g., (P A ,Q A ) in the example shown in  FIGS. 3A-3B ) under a second isogeny (e.g., ϕ B  in the example shown in  FIGS. 3A-3B ). A first generator point (e.g., G B  in the example shown in  FIGS. 3A-3B ), based on the secret integer and the second pair of elliptic curve points is obtained. A third image curve (e.g., E AB  in the example shown in  FIGS. 3A-3B ) is computed based on the secret integer and the first pair of elliptic curve points. A shared secret value (e.g., j(E AB ) in the example shown in  FIGS. 3A-3B ) is computed based on the third image curve. The shared secret value is to be shared by the first entity and the second entity. An encrypted generator point (e.g., C B  in the example shown in  FIGS. 3A-3B ) is computed from the first generator point and the shared secret value. The second public key is sent to the first entity to enable the first entity to compute the shared secret value. The encrypted generator point is sent to the first entity to enable the first entity to validate the second public key. The shared secret value can then be used to execute cryptographic correspondence over a communication network between the first entity and the second entity. 
     In a second example, a computing system includes one or more processors and a computer-readable medium storing instructions that are operable when executed by the one or more processors to perform one or more operations of the first example. 
     In a third example, a computer-readable medium stores instructions that are operable when executed by a data processing apparatus to perform one or more operations of the first example. 
     Implementations of the first, second, or third example may include one or more of the following features. Obtaining the first generator point can include computing G B =P B +[β]Q B , where G B  represents the first generator point, β represents the secret integer of the second entity, and (P B ,Q B ) represents the second pair of elliptic curve points. The first generator point G B  is a generator of a cyclic subgroup  G B   . The encrypted generator point can be computed by applying a symmetric key encryption function to the first generator point. A session key and a verification key can be computed based on the shared secret value. The symmetric key encryption function can use the session key and the verification key to generate the encrypted generator point. 
     In a fourth example, a secret integer (e.g., α in the example shown in  FIGS. 3A-3B ) of a first entity (e.g., “Alice” in the example shown in  FIGS. 3A-3B ) is obtained. A public key of a second entity (e.g., “Bob” in the example shown in  FIGS. 3A-3B ) is received. The public key includes a first image curve (e.g., E B  in the example shown in  FIGS. 3A-3B ) and a first pair of elliptic curve points (e.g., (U,V) in the example shown in  FIGS. 3A-3B ). A second image curve (e.g., E BA  in the example shown in  FIGS. 3A-3B ) is computed based on the secret integer and the first pair of elliptic curve points. A shared secret value (e.g., j(E BA ) in the example shown in  FIGS. 3A-3B ) is computed based on the second image curve. An encrypted generator point (e.g., C B  in the example shown in  FIGS. 3A-3B ), generated by the second entity, is received. A decrypted generator point (e.g., G B ′ in the example shown in  FIGS. 3A-3B ) is computed by decrypting the encrypted generator point. The decrypted generator point is used to validate the public key. The shared secret value can then be used to execute cryptographic correspondence over a communication network between the first entity and the second entity. 
     In a fifth example, a computing system includes one or more processors and a computer-readable medium storing instructions that are operable when executed by the one or more processors to perform one or more operations of the fourth example. 
     In a sixth example, a computer-readable medium stores instructions that are operable when executed by a data processing apparatus to perform one or more operations of the fourth example. 
     Implementations of the fourth, fifth, or sixth example may include one or more of the following features. The decrypted generator point can be decrypted by applying a symmetric key decryption function to the encrypted generator point. A session key and a verification key can be computed based on the shared secret value. The symmetric key decryption function can use the session key and the verification key to generate the decrypted generator point. 
     Implementations of the fourth, fifth, or sixth example may include one or more of the following features. Using the decrypted generator point to validate the public key can include validating the degree of an isogeny having the kernel  G B ′ , where G B ′ represents the decrypted generator point. For example, validating the degree of an isogeny can include validating deg(ϕ B ′)=3 m , where ϕ B ′ is the isogeny having the kernel  G B ′ , and m is an integer defined by the supersingular isogeny-based cryptosystem. Using the decrypted generator point to validate the public key can include using the decrypted generator point to compute a second pair of elliptic curve points (e.g., ϕ B ′(P A ), ϕ B ′(Q A ) in the example shown in  FIGS. 3A-3B ), wherein the second pair of elliptic curve points represent an image of a third pair of elliptic curve points (e.g., (P A ,Q A ) in the example shown in  FIGS. 3A-3B ) under an isogeny having a kernel defined by the decrypted generator point. Using the decrypted generator point to validate the public key can include verifying that the second pair of elliptic curve points matches the first pair of elliptic curve points. Using the decrypted generator point to validate the public key can include computing a third image curve (e.g., E B ′ in the example shown in  FIGS. 3A-3B ) based on the decrypted generator point; and verifying that the third image curve matches the first image curve. Validating the public key can include validating the j-invariant of the first image curve (e.g., E B  in the example shown in  FIGS. 3A-3B ). For example, validating the j-invariant of the first image curve can include verifying that j(E B )≠0, 1728, where E B  represents the first image curve. Using the decrypted generator point to validate the public key can include determining that the pubic key is valid, wherein the first pair of elliptic curve points represent an image of a second pair of elliptic curve points (e.g., (P A ,Q A ) in the example shown in  FIGS. 3A-3B ) under an isogeny (e.g., ϕ B  in the example shown in  FIGS. 3A-3B ). 
     In a seventh example, a secret integer (e.g., a in the example shown in  FIGS. 4A-4B ) of a first entity (e.g., “Alice” in the example shown in  FIGS. 4A-4B ) is obtained. A public key of a second entity (e.g., “Bob” in the example shown in  FIGS. 4A-4B ) is obtained. The public key includes a first image curve (e.g., E B  in the example shown in  FIGS. 4A-4B ) and a first pair of elliptic curve points (e.g., (U,V) in the example shown in  FIGS. 4A-4B ). A first pairing value (e.g., e 2     n   (P A ,Q A ) 3     m    in the example shown in  FIGS. 4A-4B ), based on a second pair of elliptic curve points (e.g., (P A ,Q A ) in the example shown in  FIGS. 4A-4B ) defined by a supersingular isogeny-based cryptosystem, is obtained. A second pairing value (e.g., e 2     n   (U,V) in the example shown in  FIGS. 4A-4B ) is computed based on the first pair of elliptic curve points. The public key is validated, and validating the public key includes verifying whether the first pairing value matches the second pairing value. A second image curve (e.g., E BA  in the example shown in  FIGS. 4A-4B ) is computed based on the secret integer and the first pair of elliptic curve points. A shared secret value (e.g., j (E BA ) in the example shown in  FIGS. 4A-4B ) is computed based on the second image curve. The shared secret value is shared by the first entity and the second entity. The shared secret value can then be used to execute cryptographic correspondence over a communication network between the first entity and the second entity. 
     In an eighth example, a computing system includes one or more processors and a computer-readable medium storing instructions that are operable when executed by the one or more processors to perform one or more operations of the seventh example. 
     In a ninth example, a computer-readable medium stores instructions that are operable when executed by a data processing apparatus to perform one or more operations of the seventh example. 
     Implementations of the seventh, eighth, or ninth example may include one or more of the following features. The first pairing value can be based on a Weil pairing in a base field, and the second pairing value can be based on a Weil pairing in the base field. 
     Implementations of the seventh, eighth, or ninth example may include one or more of the following features. A generator point (e.g., G B ′ in the example shown in  FIGS. 4A-4B ) can be computed based on information from the second entity. Check values can be computed based on the generator point. Validating the public key can include verifying that the check values match respective values in the public key. Computing the generator point based on information from the second entity can include obtaining an encrypted seed value (e.g., C B  in the example shown in  FIGS. 4A-4B ) from the second entity; computing a decrypted seed value (e.g., r B ′ in the example shown in  FIGS. 4A-4B ) by decrypting the encrypted seed value; and computing the generator point based on the decrypted seed value. 
     Implementations of the seventh, eighth, or ninth example may include one or more of the following features. Validating the public key can include using the generator point to compute a first elliptic curve point (e.g., ϕ B ′(Q A ) in the example shown in  FIGS. 4A-4B ) representing an image of a second elliptic curve point (Q A ) under an isogeny (e.g., ϕ B ′ in the example shown in  FIGS. 4A-4B ) having a kernel (e.g.,  G B ′  in the example shown in  FIGS. 4A-4B ) defined by the generator point, where the second elliptic curve point is one of the elliptic curve points in the second pair of elliptic curve points; and verifying that the first elliptic curve point matches one of the elliptic curve points (e.g., V in the example shown in  FIGS. 4A-4B ) in the first pair of elliptic curve points. Validating the public key can include computing a third image curve (e.g., E B ′ in the example shown in  FIGS. 4A-4B ) based on the generator point; and verifying that the third image curve matches the first image curve. 
     Implementations of the seventh, eighth, or ninth example may include one or more of the following features. Validating the public key can require only one isogeny evaluation. The first pairing value can be precomputed by the first entity before receiving the public key. Validating the public key can include determining that the second pubic key is valid, wherein the first pair of elliptic curve points represent an image of the second pair of elliptic curve points under an isogeny (e.g., ϕ B  in the example shown in  FIGS. 4A-4B ). 
     While this specification contains many details, these should not be understood as limitations on the scope of what may be claimed, but rather as descriptions of features specific to particular examples. Certain features that are described in this specification or shown in the drawings in the context of separate implementations can also be combined. Conversely, various features that are described or shown in the context of a single implementation can also be implemented in multiple embodiments separately or in any suitable subcombination. 
     Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the implementations described above should not be understood as requiring such separation in all implementations, and it should be understood that the described program components and systems can generally be integrated together in a single product or packaged into multiple products. 
     A number of embodiments have been described. Nevertheless, it will be understood that various modifications can be made. Accordingly, other embodiments are within the scope of the following claims.