PRISM with a Pinch of Salt: Simple, Efficient, and Strongly Unforgeable Signatures from Isogenies

Abstract

Abstract The problem of computing an isogeny of large prime degree from a supersingular elliptic curve of unknown endomorphism ring is assumed to be hard both for classical as well as quantum computers. In this work, we first build a two-round identification protocol whose security reduces to this problem. The challenge consists of a random large prime q and the prover simply replies with an efficient representation of an isogeny of degree q from its public key. Using the hash-and-sign paradigm, we then derive a signature scheme with a very simple and flexible signing procedure and prove its security in the standard model. The most efficient variant of our signature schemes features a signing which is $$1.4\times $$ 1.4 × to $$1.6\times $$ 1.6 × faster than the most recent implementation of SQIsign, whereas verification ranges from $$1.2\times $$ 1.2 × slower to $$1.01\times $$ 1.01 × faster depending on the security level. The sizes of public key and signature are comparable to existing schemes.