ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

논문 검색
구분 SCI
연도 ~ 키워드

상세정보

학술지 Simplified Small Exponent Test for Batch Verification
Cited 6 time in scopus Download 9 time Share share facebook twitter linkedin kakaostory
저자
황정연, 송보연, 최대선, 진승헌, 조현숙, 이문규
발행일
201702
출처
Theoretical Computer Science, v.662, pp.48-58
ISSN
0304-3975
출판사
Elsevier
DOI
https://dx.doi.org/10.1016/j.tcs.2016.12.017
협약과제
16MH1500, 상황인지기반 멀티팩터 인증 및 전자서명을 제공하는 범용인증플랫폼기술 개발, 김수형
초록
The Small Exponent Test (SET) for exponentiation is an essential batch-verification technique that is widely applied. In this paper, we propose a simplified SET that can securely batch-verify n instances with only n?닋1 randomizing exponents. We show that the structure of the proposed batch test is compact in the sense that it works with a minimal number of randomizing exponents for the SET. Thus, our test offers various advantages. Overall, compared to the original SET, the proposed simplified SET is more efficient for any sized batch instance. In particular, unlike the SET, our proposal performs well even when the size of a batch instance is small, e.g., n=1,2,3, and 4. This feature can be also used to significantly reduce pairing computations in a signature scheme where several pairing equations are verified. In addition, our test can be combined easily and generically with existing batch techniques such as the use of sparse exponents, the bucket test for large batch sizes, or an automated tool to generate a batch algorithm. Finally, with our simplified test, an efficient identification algorithm can be constructed to discover incorrect instances in a batch.
키워드
Batch verification, Digital signature, Exponentiation, Small exponent test
KSP 제안 키워드
Automated tool, Batch Verification, Batch test, Digital signature, Pairing computation, Signature scheme, identification algorithm