Processing batches of point evaluations in a supersingular isogeny-based cryptosystem

Abstract

In a general aspect, a supersingular isogeny-based cryptography process is performed. In some aspects, a cryptographic element is generated by executing a supersingular isogeny-based cryptography protocol. A generator of a first isogeny kernel is computed. A pre-determined tree topology is traversed. The tree topology includes nodes coupled by edges. A first set of edges represent scalar multiplications, and a second set of edges represent point evaluations. A plurality of isogeny kernels corresponding to respective nodes in the tree topology are computed by executing batches of operations. At least one of the batches includes a first point evaluation represented in the tree topology having a first domain and a first range, and a second point evaluation represented in the tree topology having a second domain and a second range. The first domain, the first range, the second domain and the second range are non-isomorphic elliptic curves.

What is claimed is: 
     
       1. A supersingular isogeny-based cryptography method comprising:
 generating a cryptographic element by executing a supersingular isogeny-based cryptography protocol, wherein executing the supersingular isogeny-based cryptography protocol comprises:
 computing a generator of a first isogeny kernel; and 
 traversing a pre-determined tree topology comprising nodes connected by edges, a first subset of the edges representing scalar multiplications, a second subset of the edges representing point evaluations, 
 wherein traversing the pre-determined tree topology comprises computing a plurality of isogeny kernels based on the generator of the first isogeny kernel, each of the plurality of isogeny kernels corresponding to a respective node in the tree topology and having a lower order than the first isogeny kernel, and 
 wherein computing the plurality of isogeny kernels comprises executing batches of operations in a computer system, and at least one of the batches comprises:
 a first point evaluation represented in the tree topology and having a first domain and a first range, and 
 a second point evaluation represented in the tree topology and having a second domain and a second range, 
 wherein the first domain, the first range, the second domain and the second range are non-isomorphic elliptic curves; and 
 
 
 using the cryptographic element to execute cryptographic correspondence between a first entity and a second entity, wherein the cryptographic correspondence includes communication over a communication channel between computer devices. 
 
     
     
       2. The method of  claim 1 , wherein the lower order is one of 2, 3, or 4. 
     
     
       3. The method of  claim 1 , wherein computing the generator of the first isogeny kernel comprises computing a coordinate of the generator. 
     
     
       4. The method of  claim 1 , wherein the cryptography protocol corresponds to a supersingular isogeny key exchange (SIKE) protocol or a supersingular isogeny Diffie-Hellman (SIDH) protocol. 
     
     
       5. The method of  claim 4 , wherein executing the cryptography protocol comprises at least one of: generating a public key of the first entity, generating a shared secret or verifying a public key of the second entity. 
     
     
       6. The method of  claim 1 , wherein at least one of the batches comprises a plurality of the point evaluations represented in the tree topology and at least one of the scalar multiplications represented in the tree topology. 
     
     
       7. The method of  claim 1 , wherein computing the plurality of isogeny kernels comprises using a plurality of cryptographic co-processors to execute the batches of operations, the plurality of cryptographic co-processors comprising at least one scalar multiplication co-processor and a plurality of point evaluation co-processors. 
     
     
       8. The method of  claim 1 , wherein at least one of the batches comprises a point evaluation of a public parameter of a supersingular isogeny-based cryptosystem, which is not represented in the tree topology. 
     
     
       9. The method of  claim 1 , wherein executing the supersingular isogeny-based cryptography protocol comprises using the plurality of isogeny kernels to generate or verify the cryptographic element. 
     
     
       10. A computer system comprising:
 one or more processors; and 
 memory storing instructions that, when executed, cause the one or more processors to perform operations comprising:
 generating a cryptographic element by executing a supersingular isogeny-based cryptography protocol, wherein executing the supersingular isogeny-based cryptography protocol comprises:
 computing a generator of a first isogeny kernel; and 
 traversing a pre-determined tree topology comprising nodes connected by edges, a first subset of the edges representing scalar multiplications, a second subset of the edges representing point evaluations, 
 wherein traversing the pre-determined tree topology comprises computing a plurality of isogeny kernels based on the generator of the first isogeny kernel, each of the plurality of isogeny kernels corresponding to a respective node in the tree topology and having a lower order than the first isogeny kernel, and 
 wherein computing the plurality of isogeny kernels comprises executing batches of operations in a computer system, and at least one of the batches comprises:
 a first point evaluation represented in the tree topology and having a first domain and a first range, and 
 a second point evaluation represented in the tree topology and having a second domain and a second range, 
 wherein the first domain, the first range, the second domain and the second range are non-isomorphic elliptic curves; and 
 
 
 using the cryptographic element to execute cryptographic correspondence between a first entity and a second entity, wherein the cryptographic correspondence includes communication over a communication channel between the computer system and another computer device. 
 
 
     
     
       11. The method of  claim 10 , wherein the lower order is one of 2, 3, or 4. 
     
     
       12. The method of  claim 10 , wherein computing the generator of the first isogeny kernel comprises computing a coordinate of the generator. 
     
     
       13. The method of  claim 10 , wherein the cryptography protocol corresponds to a supersingular isogeny key exchange (SIKE) protocol or a supersingular isogeny Diffie-Hellman (SIDH) protocol. 
     
     
       14. The method of  claim 13 , wherein executing the cryptography protocol comprises at least one of: generating a public key of the first entity, generating a shared secret or verifying a public key of the second entity. 
     
     
       15. The method of  claim 10 , wherein at least one of the batches comprises a plurality of the point evaluations represented in the tree topology and at least one of the scalar multiplications represented in the tree topology. 
     
     
       16. The method of  claim 10 , wherein computing the plurality of isogeny kernels comprises using a plurality of cryptographic co-processors to execute the batches of operations, the plurality of cryptographic co-processors comprising at least one scalar multiplication co-processor and a plurality of point evaluation co-processors. 
     
     
       17. The method of  claim 10 , wherein at least one of the batches comprises a point evaluation of a public parameter of a supersingular isogeny-based cryptosystem, which is not represented in the tree topology. 
     
     
       18. The method of  claim 10 , wherein executing the supersingular isogeny-based cryptography protocol comprises using the plurality of isogeny kernels to generate or verify the cryptographic element. 
     
     
       19. A non-transitory computer-readable medium storing instructions that are operable when executed by data processing apparatus to perform operations comprising:
 generating a cryptographic element by executing a supersingular isogeny-based cryptography protocol, wherein executing the supersingular isogeny-based cryptography protocol comprises
 computing a generator of a first isogeny kernel; and 
 traversing a pre-determined tree topology comprising nodes connected by edges, a first subset of the edges representing scalar multiplications, a second subset of the edges representing point evaluations, 
 
 wherein traversing the pre-determined tree topology comprises computing a plurality of isogeny kernels based on the generator of the first isogeny kernel, each of the plurality of isogeny kernels corresponding to a respective node in the tree topology and having a lower order than the first isogeny kernel, computing the plurality of isogeny kernels comprises executing batches of operations in a computer system, and at least one of the batches comprises:
 a first point evaluation represented in the tree topology and having a first domain and a first range, and 
 a second point evaluation represented in the tree topology and having a second domain and a second range, 
 wherein the first domain, the first range, the second domain and the second range are non-isomorphic elliptic curves; and 
 
 using the cryptographic element to execute cryptographic correspondence between a first entity and a second entity, wherein the cryptographic correspondence includes communication over a communication channel between computer devices. 
 
     
     
       20. The non-transitory computer-readable medium of  claim 19 , wherein the lower order is one of 2, 3, or 4. 
     
     
       21. The non-transitory computer-readable medium of  claim 19 , wherein computing the generator of the first isogeny kernel comprises computing a coordinate of the generator. 
     
     
       22. The non-transitory computer-readable medium of  claim 19 , wherein the cryptography protocol corresponds to a supersingular isogeny key exchange (SIKE) protocol or a supersingular isogeny Diffie-Hellman (SIDH) protocol. 
     
     
       23. The non-transitory computer-readable medium of  claim 22 , wherein executing the cryptography protocol comprises at least one of: generating a public key of the first entity, generating a shared secret or verifying a public key of the second entity. 
     
     
       24. The non-transitory computer-readable medium of  claim 19 , wherein at least one of the batches comprises a plurality of the point evaluations represented in the tree topology and at least one of the scalar multiplications represented in the tree topology. 
     
     
       25. The non-transitory computer-readable medium of  claim 19 , wherein computing the plurality of isogeny kernels comprises using a plurality of cryptographic co-processors to execute the batches of operations, the plurality of cryptographic co-processors comprising at least one scalar multiplication co-processor and a plurality of point evaluation co-processors. 
     
     
       26. The non-transitory computer-readable medium of  claim 19 , wherein at least one of the batches comprises a point evaluation of a public parameter of a supersingular isogeny-based cryptosystem, which is not represented in the tree topology. 
     
     
       27. The non-transitory computer-readable medium of  claim 19 , wherein executing the supersingular isogeny-based cryptography protocol comprises using the plurality of isogeny kernels to generate or verify the cryptographic element.