Generating signatures with optimal overhead: Practical paddings for signature schemes

Optimal signatures (generating signatures as short as possible), which achieve the optimal bandwidth for communication, are extremely useful in bandwidth-critical networks. Previous approaches use the random permutations with large block size as building blocks, which incurs less efficient implementations in the real world. Meanwhile, all the practical signature schemes are not optimal in bandwidth including PSS-R (probabilistic signature scheme with message recovery ), FDH ( Full Domain Hash), and DSA (Digital Signature Algorithm). This paper presents three constructions for optimal signature schemes. All the proposals use both the random oracles and the ideal ciphers with smaller block sizes as building blocks to obtain optimal paddings for signature schemes. The ideal ciphers in our schemes can be implemented by real block ciphers (e.g., AES (Advanced Encryption Standard)-256). Concrete implementations of these signature schemes can utilize the trapdoor permutations of Rabin and RSA, respectively. Surprisingly, RSA and Rabin (trapdoor permutations) lead to not only optimality in bandwidth but also a tight security. Therefore, besides yielding secure signatures with high efficiency, our proposals can also be flexibly applied to the bandwidth-limited networks that reduces the communication cost as less as possible.