Lenient/Strict Batch Verification in Several Groups

Fumitaka HOSHINO  Masayuki ABE  Tetsutaro KOBAYASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.1   pp.64-72
Publication Date: 2003/01/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Symmetric Ciphers and Hash Functions
batch verification,  elliptic curve cryptosystem,  

Full Text: PDF(258.1KB)>>
Buy this Article

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 Zp with special/random prime p and prime subgroups defined on elliptic curves over Fp, F2m and Fpm, with are often used in DL-based 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.