Patent ID: 8250367

Claim:
A computer-implemented method for cryptographically signing a message performed by one or more processors, comprising: under control of one or more computing systems comprising the one or more processors, storing a first integer, a second integer, and a third integer to represent a first isogeny, wherein: the first integer comprises a prime number comprising a degree of the first isogeny, and the second and third integers are calculated by splitting the prime number in a quadratic extension field; determining a first curve; determining a second curve by applying the first isogeny to the first curve; computing a hash of the message onto a first point on the first curve; determining a second point on the second curve; defining a second isogeny corresponding to a dual isogeny of the first isogeny, the second isogeny mapping the second curve to the first curve; storing the second isogeny; generating a public key by evaluating the second isogeny at the second point; generating a signature by evaluating the first isogeny at the first point, the evaluating comprising evaluating the isogeny by: decomposing the isogeny into a plurality of isogenies and a fourth integer, evaluating each of the plurality of isogenies, composing each of the evaluations of the plurality of isogenies to find a result, and applying endomorphism to the result; and making available the message, the signature, the first point, and the evaluation of the second isogeny at the second point.