Paper 2026/508

Schnorr Blind Signatures and Signed ElGamal KEM in Algebraic Group Action Model

Willy Susilo, University of Wollongong

Chuanqi Zhang, Monash University

Abstract

Schnorr blind signature is one of the most efficient and widely used blind signatures. At CRYPTO'23, Katsumata et al. proposed CSIOtter, the first blind signature from isogenies, which does not follow the construction framework of the Schnorr blind signature. Instead, CSIOtter was constructed from the sigma protocol for an OR relation that captures the idea of the Abe-Okamoto signature and hence can adapt the proof techniques by Kastner, Loss and Xu (PKC'22) into its security proof. Unfortunately, the concurrent security of CSIOtter was later broken independently by Katsumata et al. (PKC'24) and Do et al. (Eurocrypt'24). As a result, CSIOtter and Schnorr-like blind signature schemes constructed from Sigma protocols with small challenge space should not be used for polynomially many concurrent signing sessions without additional boosting transformations. Sequential security, and in some settings logarithmic-session concurrent security, remain meaningful security guarantees. In this paper, we provide an intensive study of the Schnorr blind signature from isogenies in the Algebraic Group Action Model (AGAM) and the Random Oracle Model (ROM). In particular, we first prove the tight security of the existing Schnorr signature from isogenies under the group action discrete logarithm assumption (GADLOG) in AGAM + ROM, which serves as the foundation for the proof of the sequential security and logarithmic-session concurrent security of the Schnorr blind signature in AGAM + ROM under the hardness of the one-more group action discrete logarithm (OMGADLOG) assumption. We also clarify a limitation of the direct parallel-repetition approach: because the large challenge space is obtained from binary challenges, the construction should not be claimed to satisfy general two-open-session concurrent security for polynomially many total signing sessions. In addition, of independent interest, we also present the Schnorr-Signed Hashed ElGamal KEM from isogenies and prove its CCA2 security in AGAM + ROM under the hardness of GADLOG.

Note: We thank Dr Lucjan Hanzlik for kindly bringing to our attention an issue concerning the 2-concurrent security claim in the first version of this work. The claim has been removed in this version, and the relevant discussion has been updated accordingly.

@misc{cryptoeprint:2026/508,
      author = {Dung Hoang Duong and Willy Susilo and Chuanqi Zhang},
      title = {Schnorr Blind Signatures and Signed {ElGamal} {KEM} in Algebraic Group Action Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/508},
      year = {2026},
      url = {https://eprint.iacr.org/2026/508}
}