ElGamal型签名算法分批验证及其安全性

ElGamal Type Signature Algorithms Batch Verification and Their Security

在９４年欧洲密码会上，Ｎａｃｃａｃｈｅ等人〔１〕为加速ＤＳＡ验证提出了两种分批验证：交互式分批和概率分批。Ｌｉｍ等人〔２〕指出，签名者和验证者很容易伪造签名以满足交互式分批验证方程，因此，交互式分批验证方法很不安全。作者研究了ＥｌＧａｍａｌ型签名算法交互式分批验证及其安全性。并基于一些ＥｌＧａｍａｌ型签名算法，提出３种新的交互式分批验证方案。

At Eurocrtypt'94, Naccache et al. 1 presented two kinds of batch verification protocol for fast DSA verification: the interactive batch and probability batch. The authors of paper 2 showed that either the signer or the verifier could easily generate a collection of bogus signatures that satisfied the batch verification equation, so the interactive DSA batch verification method was not secure at all. This paper investigates the security of the interactive ElGamal type signature algorithms batch verification. More precisely, we present three kinds of interactive batch verification schemes based on some ElGamal type signature algorithms and discuss their security.