Abstract
We initiate the investigation of a new kind of efficiency for cryptographic transformations. The idea is that having once applied the transformation to some document M, the time to update the result upon modification of M should be “proportional” to the “amount of modification” done to M. Thereby one obtains much faster cryptographic primitives for environments where closely related documents are undergoing the same cryptographic transformations.
We provide some basic definitions enabling treatment of the new notion. We then exemplify our approach by suggesting incremental schemes for hashing and signing which are efficient according to our new measure.
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
M. Bellare, J. Kilian and P. Rogaway. The security of cipher block chaining. Advances in Cryptology — Crypto 94 Proceedings.
M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. Proceedings of the First Annual Conference on Computer and Communications Security, ACM, 1993.
M. Bellare, O. Goldreich and S. Gpldwasser. Work in progress.
J. Bos and M. Coster. Addition chain heuristics. Advances in Cryptology — Crypto 89 Proceedings, Lecture Notes in Computer Science Vol. 435, Springer-Verlag, G. Brassard, ed., 1989.
S. Brands. An efficient off-line electronic cash system based on the representation problem. CWI Technical Report CS-R9323.
D. Chaum and H. Van Antwerpen. Undeniable signatures. Advances in Cryptology — Crypto 89 Proceedings, Lecture Notes in Computer Science Vol. 435, Springer-Verlag, G. Brassard, ed., 1989.
D. Chaum, E. Heijst and B. Pfitzmann. Cryptographically strong undeniable signatures, unconditionally secure for the signer. Advances in Cryptology — Crypto 91 Proceedings, Lecture Notes in Computer Science Vol. 576, Springer-Verlag, J. Feigenbaum, ed., 1991.
Croft and Harris. Public key cryptography and re-usable shared secrets. In Cryptography and Coding, Clarendon Press, 1989.
I. Damgård. Collision free hash functions and public key signature schemes. Advances in Cryptology — Eurocrypt 87 Proceedings, Lecture Notes in Computer Science Vol. 304, Springer-Verlag, D. Chaum, ed., 1987.
T. El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Info. Theory, Vol. IT 31, 1985.
S. Even, O. Goldrech and S. Micali. On-line/Off line digital signatures. Manuscript. Preliminary version in Crypto 89.
O. Goldreich and L. Levin. A hard predicate for all one-way functions. Proceedings of the Twenty First Annual Symposium on the Theory of Computing, ACM, 1989.
S. Goldwasser, S. Micali and R. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal of Computing, 17(2):281–308, April 1988.
R. Impagliazzo, L. Levin and M. Luby. Pseudo-random generation from one-way functions. Proceedings of the Twenty First Annual Symposium on the Theory of Computing, ACM, 1989.
M. Naor and M. Yung. Universal One-Way Hash Functions and their Cryptographic Applications. Proceedings of the Twenty First Annual Symposium on the Theory of Computing, ACM, 1989.
R. Rivest. The MD5 message-digest algorithm. IETF Network Working Group, RFC 1321, April 1992.
C. Schnorr. Efficient identification and signatures for smart cards. Advances in Cryptology — Crypto 89 Proceedings, Lecture Notes in Computer Science Vol. 435, Springer-Verlag, G. Brassard, ed., 1989.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Goldreich, O., Goldwasser, S. (1994). Incremental Cryptography: The Case of Hashing and Signing. In: Desmedt, Y.G. (eds) Advances in Cryptology — CRYPTO ’94. CRYPTO 1994. Lecture Notes in Computer Science, vol 839. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48658-5_22
Download citation
DOI: https://doi.org/10.1007/3-540-48658-5_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58333-2
Online ISBN: 978-3-540-48658-9
eBook Packages: Springer Book Archive