Comments on efficient batch verification test for digital signatures based on elliptic curves

Keisuke Hakuta, Hiroyuki Ochiai, Tsuyoshi Takagi

Research output: Contribution to journalArticlepeer-review


Batch verification for digital signature scheme is a method to verify multiple signatures simultaneously. The complex exponent test (CE test for short) proposed by Cheon and Lee is one of the most efficient batch verification tests for several digital signature schemes on certain types of elliptic curves (including Koblitz curves). The security of the CE test relies essentially on the cardinality of a subset of a residue ring of the endomorphism ring of an elliptic curve over an ideal. They have evaluated the cardinality of the above subset, and have illustrated the effectiveness of the CE test by using the evaluation. The aim of this paper is to point out that their evaluation contains a flaw. The flaw is generally related to two roots of a quadratic equation which is used in their argument. We mend the flaw of their evaluation. Our correct evaluation shows that the CE test can achieve the same security as the underlying signature scheme on Koblitz curves. As a result, the CE test is a secure batch verification when the underlying signature scheme uses Koblitz curves.

Original languageEnglish
Pages (from-to)575-590
Number of pages16
JournalMathematica Slovaca
Issue number3
Publication statusPublished - Jun 1 2022

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Comments on efficient batch verification test for digital signatures based on elliptic curves'. Together they form a unique fingerprint.

Cite this