Online/Offline Signature Schemes for Devices with Limited Computing Capabilities

We propose a family of three efficient digital signature schemes, which are proved secure under the strong RSA assumption without requiring a random oracle. The new signature schemes can operate in an online/offline manner, doing most of their work in the offline precomputation phase. The online phase of even the least efficient variant is very fast, requiring only a single non-modular multiplication of a short (160-bit) value by a longer (1022-bit) value. Online/offline signatures are useful in settings in which signatures need to be produced with few operations, either when there is a large volume of requests or if the device performing the signature is not computationally powerful. Our schemes have extremely low computation cost so are particularly suitable for devices with limited computing capabilities such as smart cards or mobile devices.

This paper provides three specific contributions. First, we propose our basic online/offline signature scheme, which could be viewed as the online/offline extension of the Camenisch-Lysyanskaya (CL) signature scheme. Compared to using the general Shamir-Tauman technique for converting the CL signature scheme into one that operates in an online/offline fashion, our direct adaptation has the same online efficiency, while having advantages of a more efficient offline phase, simpler key management that only requires one keypair, and a shorter signature. In addition, when used as a traditional one-phase signature our basic scheme is more efficient than the Camenisch-Lysyanskaya scheme, due to our operation restructuring. While this first scheme has advantages over using the Shamir-Tauman/Camenisch-Lysyanskaya construction, we describe two additional techniques that further improve efficiency of both online and offline phases. Our first improvement uses computations over a small subgroup of

$Z_n^*$

to reduce the size of the required computations. Our second improvement uses division intractable hash functions to remove the requirement of generating random primes for use in this class of signature schemes. As we present these three schemes, each one is more efficient than the previous one, but requires increasingly strong complexity assumptions.