Optimal Asymmetric Encryption and Signature Paddings.
Benoît Chevallier-Mames and Duong Hieu Phan and David Pointcheval.
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 requires
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 construction, a universal padding, which
one could apply for both encryption and signature. As a consequence, such a padding has to introduce both
randomness 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.
Ref: Proceeding of ACNS '05, Lecture Notes in Computer Science Vol. 3531, pages 254-268, Springer-Verlag, 2005.
Available: pdf.