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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Fumitaka HOSHINO, Masayuki ABE, Tetsutaro KOBAYASHI, "Lenient/Strict Batch Verification in Several Groups" in IEICE TRANSACTIONS on Fundamentals,
vol. E86-A, no. 1, pp. 64-72, January 2003, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e86-a_1_64/_p
Copy
@ARTICLE{e86-a_1_64,
author={Fumitaka HOSHINO, Masayuki ABE, Tetsutaro KOBAYASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Lenient/Strict Batch Verification in Several Groups},
year={2003},
volume={E86-A},
number={1},
pages={64-72},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - Lenient/Strict Batch Verification in Several Groups
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 64
EP - 72
AU - Fumitaka HOSHINO
AU - Masayuki ABE
AU - Tetsutaro KOBAYASHI
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2003
AB - 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.
ER -