
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Lenient/Strict Batch Verification in Several Groups
Fumitaka HOSHINO Masayuki ABE Tetsutaro KOBAYASHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E86A
No.1
pp.6472 Publication Date: 2003/01/01
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Symmetric Ciphers and Hash Functions Keyword: batch verification, elliptic curve cryptosystem,
Full Text: PDF>>
Summary:
Batch verification is a useful tool in verifying a large number of cryptographic items all at one time. It is especially effective in verifying predicates based on modular exponentiation. In some cases, however the items can be incorrect although they pass batch verification together. Such leniency can be eliminated by checking the domain of each item in advance. With this in mind, we introduce the strict batch verification and investigate if the strict batch verification can remain more effective than separate verification. In this paper, we estimate the efficiency of such strict batch verification in several types of groups, a prime subgroup of Z_{p} with special/random prime p and prime subgroups defined on elliptic curves over F_{p}, F_{2m} and F_{pm}, with are often used in DLbased cryptographic primitives. Our analysis concludes that the efficiency differs greatly depending on the choice of the group and parameters determined by the verifying predicate. Furthermore, we even show that there are some cases where batch verification, regardless of strictness, loses its computational advantage.

