Loading...
Please wait, while we are loading the content...
Similar Documents
Fast batch verification for modular exponentiation and digital signatures (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Rabin, Tal Garay, Juan A. Bellare, Mihir |
| Abstract | Abstract. Many tasks in cryptography (e.g., digital signature verification) call for verification of a basic operation like modular exponentiation in some group: given (9, z, v) check that g2 = y. This is typically done by re-computing gz and checking we get y. We would like to do it differently, and faster. The approach we use is batching. Focusing first on the basic modular exponentiation operation, we provide some probabilistic batch verifiers, or tests, that verify a sequence of modular exponentiations significantly faster than the naive re-computation method. This yields speedups for several verification tasks that involve modular exponentiations. Focusing specifically on digital signatures, we then suggest a weaker notion of (batch) verification which we call “screening. ” It seems useful for many usages of signatures, and has the advantage that it can be done very fast; in particular, we show how to screen a sequence of RSA signatures at the cost of one RSA verification plus hashing. 1 |
| File Format | |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Several Verification Task Naive Re-computation Method Digital Signature Basic Operation Modular Exponentiation Fast Batch Verification Re-computing Gz Digital Signature Verification Rsa Signature Probabilistic Batch Verifier Many Usage Rsa Verification Basic Modular Exponentiation Operation Many Task |
| Content Type | Text |
| Resource Type | Article |
