New generation of secure and practical RSA-based signatures

For most digital signature schemes used in practice, such as ISO9796/RSA or DSA, it has only been shown that certain plausible cryptographic assumptions, such as the difficulty of factoring integers, computing discrete logarithms or the collision-intractability of certain hash-functions are necessary for the security of the scheme, while their sufficiency is, strictly speaking, an open question. A clear advantage of such schemes over many signature schemes with security proven relative to such common cryptographic assumptions, is their efficiency: as a result of their relatively weak requirements regarding computation, bandwidth and storage, these schemes have so far beaten proven secure schemes in practice. Our aim is to contribute to the bridging of the gap that seems to exist between the theory and practice of digital signature schemes. We present a digital signature that offers both proven security and practical value. More precisely, under an appropriate assumption about RSA, the scheme is proven to be not existentially forgeable under adaptively chosen message attacks. Furthermore, we identify some electronic devices where our scheme can be conveniently implemented using dedicated smartcards that are available today.