Abstract
We study how digital signature schemes can generate signatures as short as possible, in particular in the case where partial message recovery is allowed. We give a concrete proposition named OPSSR that achieves the lower bound for message expansion, and give an exact security proof of the scheme in the ideal cipher model. We extend it to the multi-key setting. We also show that this padding can be used for an asymmetric encryption scheme with minimal message expansion.
Part of this work has been supported by the Commission of the European Communities through the IST Programme under Contract IST-1999-12324 (NESSIE). This paper is NESSIE document NES/DOC/ENS/WP5/021/2.
Chapter PDF
Similar content being viewed by others
References
M. Bellare and P. Rogaway. Optimal asymmetric encryption-how to encrypt with RSA. Proc. Eurocrypt’94, LNCS 950, pages 92–111, May 1994. Available from http://www-cse. ucsd. edu/users/mihir/crypto-research-papers. html.
M. Bellare and P. Rogaway. The exact security of digital signatures: how to sign with RSA and Rabin. Proc. Eurocrypt’96, LNCS 1070, pages 399–416, May 1996. Revised version available from http://www-cse.ucsd.edu/users/mihir/crypto-research-papers.html.
D. Boneh. Simplified OEAP for the RSA and Rabin functions. Proc. Crypto’01, LNCS 2139, pages 275–291, Aug. 2001. Available at http://crypto.stanford.edu/~dabo/papers/saep.ps.
D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. Proc. Asiacrypt’01, LNCS 2248, pages 514–532, Dec. 2001. Available at http://crypto.stanford.edu/~dabo/papers/weilsig.ps.
D. Brown and D. Johnson. Formal Security Proofs for a Signature Scheme with Partial Message Recovery. 2000. Available at http://www.cacr.math.uwaterloo.ca/techreports/2000/corr2000-39.pdf.
R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. Proc. STOC’98, ACM, pages 209–218, May 1998. Available at http://theory.lcs.mit.edu/~oded/rom.html.
D. Coppersmith. Modifications of the Number Field Sieve. Journal of Cryptology, vol. 6, n. 3, pages 169–180, 1993.
J.-S. Coron. On the exact security of Full Domain Hash. Proc. Crypto’00, LNCS 1880, pages 229–235, Aug. 2000. Available at http://www.eleves.ens.fr/home/coron/fdh.ps.
J.-S. Coron. Optimal security proofs for PSS and other signature schemes. Proc. Eurocrypt’02, LNCS 2332, pages 272–287, May 2002. Available at http://eprint.iacr.org/2001/062/.
J.-S. Coron, M. Joye, D. Naccache and P. Paillier. Universal Padding Schemes for RSA. Proc. Crypto’02, LNCS, Aug. 2002. Available at http://eprint.iacr.org/2002/115/.
N. Courtois, M. Finiasz, and N. Sendrier. How to Achieve a McEliece-based Digital Signature Scheme. Proc. Asiacrypt’01, LNCS 2248, 157–174, Dec. 2001. Available at http://www.minrank.org/mceliece/.
N. Courtois, L. Goubin, and J. Patarin. Quartz, 128-bit long digital signatures. Cryptographers’ Track Rsa Conference 2001, LNCS 2020, Apr. 2001. Available at http://www.minrank.org/quartz/.
A. Dent. Adapting the weaknesses of the Random Oracle model to the Generic Group model. To appear in Asiacrypt’02. Available at http://eprint.iacr.org/2002/086/.
J. Jonsson. An OAEP variant with a tight security proof. Manuscript, Mar. 2002. Available at http://eprint.iacr.org/2002/034/.
KCDSA Task Force Team. The Korean Certificate-based Digital Signature Algorithm. Proc. Asiacrypt’98, LNCS 1514, pages 175–186, Oct. 1998. Also available at http://grouper.ieee.org/groups/1363/P1363a/PSSigs.html as an IEEE P1363a submission.
K. Kobara and H. Imai. OAEP++: A very simple way to apply OAEP to deterministic OW-CPA primitives. Manuscript, Aug. 2002. Available at http://eprint.iacr.org/2002/130/.
D. Naccache and J. Stern. Signing on a Postcard. Proc. FC’00, LNCS 1962, pages 121–135, Feb. 2000. Available at http://grouper.ieee.org/groups/1363/Research/contributions/Postcard.ps.
L. Pintsov and S. Vanstone. Postal revenue collection in the digital age. Proc. FC’00, LNCS 1962, pages 105–120, Feb. 2000. Available at http://www.cacr.math.uwaterloo.ca/techreports/2000/corr2000-43.ps. Analysed in [5].
V. Shoup. OAEP Reconsidered. Proc. Crypto’01, LNCS 2139, pages 239–259, Aug. 2001. Available at http://www.shoup.net/papers/oaep.pdf.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Granboulan, L. (2002). Short Signatures in the Random Oracle Model. In: Zheng, Y. (eds) Advances in Cryptology — ASIACRYPT 2002. ASIACRYPT 2002. Lecture Notes in Computer Science, vol 2501. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36178-2_23
Download citation
DOI: https://doi.org/10.1007/3-540-36178-2_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00171-3
Online ISBN: 978-3-540-36178-7
eBook Packages: Springer Book Archive