Advertisement

Incremental Cryptography: The Case of Hashing and Signing

  • Mihir Bellare
  • Oded Goldreich
  • Shafi Goldwasser
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)

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.

Keywords

Hash Function Signature Scheme Random Oracle Security Parameter Hash Family 
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

  1. 1.
    M. Bellare, J. Kilian and P. Rogaway. The security of cipher block chaining. Advances in Cryptology — Crypto 94 Proceedings.Google Scholar
  2. 2.
    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.Google Scholar
  3. 3.
    M. Bellare, O. Goldreich and S. Gpldwasser. Work in progress.Google Scholar
  4. 4.
    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.Google Scholar
  5. 5.
    S. Brands. An efficient off-line electronic cash system based on the representation problem. CWI Technical Report CS-R9323.Google Scholar
  6. 6.
    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.Google Scholar
  7. 7.
    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.Google Scholar
  8. 8.
    Croft and Harris. Public key cryptography and re-usable shared secrets. In Cryptography and Coding, Clarendon Press, 1989.Google Scholar
  9. 9.
    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.Google Scholar
  10. 10.
    T. El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Info. Theory, Vol. IT 31, 1985.Google Scholar
  11. 11.
    S. Even, O. Goldrech and S. Micali. On-line/Off line digital signatures. Manuscript. Preliminary version in Crypto 89.Google Scholar
  12. 12.
    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.Google Scholar
  13. 13.
    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.zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    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.Google Scholar
  15. 15.
    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.Google Scholar
  16. 16.
    R. Rivest. The MD5 message-digest algorithm. IETF Network Working Group, RFC 1321, April 1992.Google Scholar
  17. 17.
    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.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Mihir Bellare
    • 1
  • Oded Goldreich
    • 2
  • Shafi Goldwasser
    • 2
    • 3
  1. 1.Advanced Networking LaboratoryIBM T.J. Watson Research CenterYorktown HeightsUSA
  2. 2.Department of Applied Mathematics and Computer ScienceWeizmann Institute of ScienceRehovotIsrael
  3. 3.MIT Laboratory for Computer ScienceCambridgeUSA

Personalised recommendations