Abstract
We present two new schemes for efficient certificate revocation. Our first scheme is a direct improvement on a well-known tree-based variant of the NOVOMODO system of Micali [11]. Our second scheme is a direct improvement on a tree-based variant of a multi-certificate revocation system by Aiello, Lodha, and Ostrovsky [1]. At the core of our schemes is a novel construct termed a QuasiModo tree, which is like a Merkle tree but contains a length-2 chain at the leaves and also directly utilizes interior nodes. This concept is of independent interest, and we believe such trees will have numerous other applications. The idea, while simple, immediately provides a strict improvement in the relevant time and communication complexities over previously published schemes.
A very preliminary portion of this work was conducted when F. Elwailly and Z. Ramzan were at IP Dynamics, Inc.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aiello, W., Lodha, S., Ostrovsky, R.: Fast Digital Identity Revocation. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 137. Springer, Heidelberg (1998)
Damgård, I.: A Design Principle for Hash Functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990)
Dei, W.: Crypto++ library v5.1
Gassko, I., Gemmell, P.S., MacKenzie, P.D.: Efficient and Fresh Certification. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 342–353. Springer, Heidelberg (2000)
Gentry, C., Ramzan, Z.: Microcredits for Verifiable Foreign Service Provider Metering. In: Juels, A. (ed.) FC 2004. LNCS, vol. 3110, pp. 9–23. Springer, Heidelberg (2004)
Goldwasser, S., Micali, S., Rivest, R.L.: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM Journal on Computing 17(2), 281–308 (1988)
Kocher, P.: On Certificate Revocation and Validation. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 172–177. Springer, Heidelberg (1998)
Merkle, R.: One-way Hash Functions and DES. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 428–446. Springer, Heidelberg (1990)
Merkle, R.: Protocols for Public-Key Cryptography. In: Proc. of IEEE Symposium on Security and Privacy 1980 (1980)
Micali, S.: Efficient Certificate Revocation. In: Proc. of RSA Data Security Conference 1997 (1997)
Micali, S.: NOVOMODO: Scalable Certificate Validation and Simplified PKI Management. In: Proc. of PKI Research Workshop (2002)
Micali, S.: Efficient Certificate Revocation. LCS/TM 542b, Massachusetts Institute of Technology (1996)
Myers, M., Ankney, R., Malpani, A., Galperin, S., Adams, C.: X.509 Internet Public Key Infrastructure Online Certificate Status Protocol - OCSP. In: Internet RFC 2560, June
Naor, M., Nissim, K.: Certificate Revocation and Certificate Update. In: Proc. of USENIX Security 1998 (1998)
National Institute of Standards. FIPS 180-1: Secure Hash Standard (1995)
Okamoto, T., Fujisaki, E., Morita, H.: TSH-ESIGN: Efficient Digital Signature Scheme Using Trisection Size Hash. In: Contribution to IEEE P1363 1998 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Elwailly, F.F., Gentry, C., Ramzan, Z. (2004). QuasiModo: Efficient Certificate Validation and Revocation. In: Bao, F., Deng, R., Zhou, J. (eds) Public Key Cryptography – PKC 2004. PKC 2004. Lecture Notes in Computer Science, vol 2947. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24632-9_27
Download citation
DOI: https://doi.org/10.1007/978-3-540-24632-9_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21018-4
Online ISBN: 978-3-540-24632-9
eBook Packages: Springer Book Archive