Speeding-up verification of digital signatures

作者:

Highlights:

摘要

In 2003, Fischlin introduced the concept of progressive verification in cryptography to relate the error probability of a cryptographic verification procedure to its running time. It ensures that the verifier confidence in the validity of a verification procedure grows with the work it invests in the computation. Le, Kelkar and Kate recently revisited this approach for digital signatures and proposed a similar framework under the name of flexible signatures. We propose efficient probabilistic verification procedures for popular signature schemes in which the error probability of a verifier decreases exponentially with the verifier running time. We propose theoretical schemes for the RSA and ECDSA signatures based on some elegant idea proposed by Bernstein in 2000 and some additional tricks. We also present a general practical method, that makes use of efficient error-correcting codes, for signature schemes for which verification involves a matrix/vector multiplication.

论文关键词:Public-key cryptography,Digital signatures,Probabilistic verification,RSA signatures,ECDSA signatures,GPV signatures

论文评审过程:Received 1 March 2020, Revised 27 July 2020, Accepted 28 August 2020, Available online 25 September 2020, Version of Record 29 September 2020.

论文官网地址:https://doi.org/10.1016/j.jcss.2020.08.005