Paper 2016/1185

A Digital Signature Scheme Based On Supersingular Isogeny Problem

Kisoon Yoon, Jihoon Kwon, and Suhri Kim

Abstract

In this paper we propose a digital signature scheme based on supersingular isogeny problem. We design a signature scheme using the Fiat-Shamir transform. The scheme uses a modified version of zero-knowledge proof proposed by De Feo, Jao, and Plût. Unlike the original version our zero-knowledge proof uses only one curve as a commitment. A digital signature scheme using the similar idea was proposed recently by Galbraith et al., but our proposal uses a different method in computing isogeny. We take advantage of our proposed version of zero-knowledge proof to speed up signature generation process. We also present a method of compressing signature.

Note: There is a serious error in the paper. The scheme is not secure. An adversary sees a point G = S + R where S has order l_S^{e_S} and R has order l_R^{e_R}. The adversary can compute S. Thanks to Steven Galbraith for pointing out the mistake. P = [l_R^{e_R}] G = [l_R^{e_R}] S and then can compute u = (l_R^{e_R})^{-1} (mod l_S^{e_S}) and so can compute [u]P = S. The adversary now has learned the secret key S.