A Short Signature Scheme from the RSA Family

摘要

We propose a short signature scheme based on the complexity assumptions related to the RSA modulus. More specifically, the new scheme is secure in the standard model based on the strong RSA subgroup assumption. Most short signature schemes are based on either the discrete logarithm problem (or its variants), or the problems from bilinear mapping. So far we are not aware of any signature schemes in the RSA family can produce a signature shorter than the RSA modulus (in a typical setting, an RSA modulus is 1024 bits). The new scheme can produce a 420-bit signature, much shorter than the RSA modulus. In addition, the new scheme is very efficient. It only needs one modulo exponentiation with a 200-bit exponent to produce a signature. In comparison, most RSA-type signature schemes at least need one modulo exponentiation with 1024-bit exponent, whose cost is more than five times of the new scheme's.