Cryptology ePrint Archive: Report 2016/1154

Signature Schemes Based On Supersingular Isogeny Problems

Steven D. Galbraith and Christophe Petit and Javier Silva

Abstract: We present the first signature schemes whose security relies on computational assumptions relating to isogeny graphs of supersingular elliptic curves. We give two schemes, both of them based on interactive identification protocols. The first identification protocol is due to De Feo, Jao and Plût. The second one, and the main contribution of the paper, uses novel ideas that have not been used in cryptography previously, and is based on a more standard and potentially stronger computational problem. Both identification protocols lead to signatures that are existentially unforgeable under chosen message attacks in the random oracle model using the well-known Fiat-Shamir transform, and in the quantum random oracle model using another transform due to Unruh.

Category / Keywords: public key cryptography / isogeny problems / post-quantum /

Date: received 15 Dec 2016, last revised 22 Feb 2017

Contact author: s galbraith at auckland ac nz; christophe petit@maths ox ac uk; javier silva@upf edu

Available format(s): PDF | BibTeX Citation

Version: 20170222:090050 (All versions of this report)

Short URL: ia.cr/2016/1154

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]