Optimal Asymmetric Encryption and Signature Paddings

Abstract. Strong security notions often introduce strong constraints on the construction of cryptographic schemes: semantic security implies probabilistic encryption, while the resistance to existential forgeries re-quires redundancy in signature schemes. Some paddings have thus been designed in order to provide these minimal requirements to each of them, in order to achieve secure primitives. A few years ago, Coron et al. suggested the design of a common construc-tion, a universal padding, which one could apply for both encryption and signature. As a consequence, such a padding has to introduce both ran-domness and redundancy, which does not lead to an optimal encryption nor an optimal signature. In this paper, we refine this notion of universal padding, in which a part can be either a random string in order to introduce randomness or a zero-constant string in order to introduce some redundancy. This helps us to build, with a unique padding, optimal encryption and optimal signature: first, in the random-permutation model, and then in the random-oracle model. In both cases, we study the concrete sizes of the parameters, for a specific security level: The former achieves an optimal bandwidth.