Public key validation in supersingular isogeny-based cryptographic protocols

A non-transitory computer-readable medium storing instructions that are operable when executed by data processing apparatus to perform operations comprising:

• obtaining a first public key of a first entity, the first public key comprising a first image curve and a first pair of elliptic curve points, wherein the first pair of elliptic curve points represent an image of a second pair of elliptic curve points under a first isogeny;
• obtaining a secret integer of a second entity;
• obtaining a second public key of the second entity based on the secret integer, the second public key comprising a second image curve and a third pair of elliptic curve points, wherein the third pair of elliptic curve points represent an image of a fourth pair of elliptic curve points under a second isogeny;
• obtaining a first generator point based on the secret integer and the second pair of elliptic curve points;
• computing a third image curve based on the secret integer and the first pair of elliptic curve points;
• computing a shared secret value based on the third image curve;
• computing an encrypted generator point from the first generator point and the shared secret value;
• sending, to the first entity, the second public key to enable the first entity to compute the shared secret value;
• and
• sending, to the first entity, the encrypted generator point to enable the first entity to validate the second public key.

A computing device, comprising:

• one or more processors;
• and
• memory storing instructions that are operable when executed by the one or more processors to perform operations comprising:
• obtaining a first public key of a first entity, the first public key comprising a first image curve and a first pair of elliptic curve points, wherein the first pair of elliptic curve points represent an image of a second pair of elliptic curve points under a first isogeny;
• obtaining a secret integer of a second entity;
• obtaining a second public key of the second entity based on the secret integer, the second public key comprising a second image curve and a third pair of elliptic curve points, wherein the third pair of elliptic curve points represent an image of a fourth pair of elliptic curve points under a second isogeny;
• obtaining a first generator point based on the secret integer and the second pair of elliptic curve points;
• computing a third image curve based on the secret integer and the first pair of elliptic curve points;
• computing a shared secret value based on the third image curve;
• computing an encrypted generator point from the first generator point and the shared secret value;
• sending, to the first entity, the second public key to enable the first entity to compute the shared secret value;
• and
• sending, to the first entity, the encrypted generator point to enable the first entity to validate the second public key.