A Method of Finding Bad Signatures in an RSA-Type Batch Verification

摘要

Batch cryptography has been developed into two main branches - batch verification and batch identification. Batch verification is a method to determine whether a set of signatures contains invalid signatures, and batch identification is a method to find bad signatures if a set of signatures contains invalid signatures. Recently, some significant developments appeared in such field, especially by Lee et at, Ferrara et al. and Law et al., respectively. In this paper, we address some weakness of Lee et al.'s earlier work, and propose an identification method in an RSA-type signature. Our method is more efficient than the well known divide and conquer method for the signature scheme. We conclude this paper by providing a method to choose optimal divide and conquer verifiers.%Paketinė kriptografija skirstoma į paketinę identifikaciją ir paketinę verifikaciją. Paketinė verifikacija nustato ar parašų aibėje yra negaliojančių parašų, o paketinė identifikacija suranda blogus parašus, jei parašų aibėje yra negaliojančių parašų. Neseniai šį uždavinį sprendė Lee et ai, Fer-rara et al. ir Law et al. Šiame straipsnyje parodyti tam tikri Lee et al. darbo trūkumai ir pasiūlytas RSA tipo parašo identifikavimo metodas. Pasiūlytasis metodas yra efektyvesnis negu gerai žinomas parašo schemos išskaidymo metodas. Pasiūlytas optimalių išskaidymo verifikatorių parinkimo algoritmas.