A practical optimal padding for signature schemes

A digital signature scheme that achieves an optimal bandwidth (generating signatures as short as possible) is called an optimal signature scheme. The previous optimal signature schemes all need the random permutations (or the ideal ciphers) with large block size as building blocks. However, the practical cipher with large block size such as Halevi and Rogaway’s CMC-mode should call the underlying secure block cipher with small block size many times each time. This makes the previous optimal signature schemes which use the large domain permutation (or the ideal cipher) less efficient in the real world, even if there exist the methods that can encipher the messages with larger domain. On the other hand, all the practical signature schemes are not optimal in bandwidth including PSS-R, FDH, DSA, etc. Hence, the problem on how to design a practical, efficient and optimal signature scheme remains open. This paper uses two random oracles and an ideal cipher with a smaller block size to design an optimal padding for signature schemes. The ideal cipher in our scheme can be implemented with a truly real block cipher (e.g. AES). Therefore, we provide a perfect solution to the open problem. More precisely, we design a practical, efficient and optimal signature scheme. Particularly, in the case of RSA, the padding leads the signature scheme to achieve not only optimality in bandwidth but also a tight security.