Fast Batch Verification for Modular Exponentiation and Digital Signatures

By Mihir Bellare, Juan A. Garay, Tal Rabin. 1998

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Bulletproofs: Short Proofs for Confidential Transactions and More (2018, methodology): “We can therefore apply batch verification [67] in order to reduce the number of expensive exponentiations.”
Direct anonymous attestation (2004, background): “[2]) to obtain a considerable speed-up of the verification step 4.”
Faster Batch Forgery Identification (2012, methodology): “The first paper to point out a non-constant speedup was [2] by Bellare, Garay, and Rabin, using a different technique that does not appear to be competitive with advanced multi-scalar multiplication methods.”
One (Block) Size Fits All: PIR and SPIR with Variable-Length Records via Multi-Block Queries (2013, unknown): “’s “small exponent” batch verification [4]: if 〈 f1(0), .”
Scalable Protocols for Authenticated Group Key Exchange (2003, background): “See Section 4 for further discussion. protocol which is secure (and achieves forward secrecy) under the DDH assumption.3 Unfortunately, the given proof of security applies only when n is constant ; in contrast, the proofs given here allow n = poly(k).”
How to Disembed a Program? (2004, methodology): “5 Historically, [4] proposed only the criterion ( ∏ σi) = ∏ μ(mi) mod N .”
Evaluating 2-DNF Formulas on Ciphertexts (2005, background): “∑ ri · vi · (vi− 1) where the ri’s are chosen by the verifiers) and then run a binary search to identify the invalid votes [1].”
Efficient oblivious transfer protocols (2001, background): “The best results are in the area of signatures: it is possible to ver/fy several modular exponential equations (and in particular signatures) with a number of exponentiations proportional to the security parameter (See [2, 24, 29]).”
Provable data possession at untrusted stores (2007, methodology): “Under the RSA and KEA1-r assumptions, S-PDP guarantees data possession in the random oracle model.”
A Security and Privacy Review of VANETs (2015, methodology): “More performance evaluation of these schemes should be conducted on a large-scale VANET, with varying vehicle mobility models, like creating a stronger threat model in which an adversary can utilize more character factors to track a vehicle.”
Cooperative Security for Network Coding File Distribution (2006, methodology): “However, this batching scheme is exposed to a specific byzantine attack, which we call the pairwise byzantine attack [6].”
On-the-fly verification of rateless erasure codes for efficient content distribution (2004, methodology): “We use a technique suggested by Bellare, Garay, and Rabin [19] to improve verification performance.”