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. Our optimized C implementation of the signature scheme shows that signing is roughly \(1.8\times \) faster than all SQIsign variants, whereas verification is \(1.4\times \) times slower. The sizes of the public key and signature are comparable to existing schemes.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

PRISM: Simple and Compact Identification and Signatures from Large Prime Degree Isogenies

  • Andrea Basso,
  • Giacomo Borin,
  • Wouter Castryck,
  • Maria Corte-Real Santos,
  • Riccardo Invernizzi,
  • Antonin Leroux,
  • Luciano Maino,
  • Frederik Vercauteren,
  • Benjamin Wesolowski

摘要

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. Our optimized C implementation of the signature scheme shows that signing is roughly \(1.8\times \) faster than all SQIsign variants, whereas verification is \(1.4\times \) times slower. The sizes of the public key and signature are comparable to existing schemes.