Cryptographic tamper evidence

ABSTRACT

We propose a new notion of cryptographic tamper evidence. A tamper-evident signature scheme provides an additional procedure Div which detects tampering: given two signatures, Div can determine whether one of them was generated by the forger. Surprisingly, this is possible even after the adversary has inconspicuously learned (exposed\footnote We say that a secret is exposed when it becomes known to the adversary. Exposure does not imply that the secrets become publicly known. Moreover, nobody --- except the adversary --- is aware of the exposure taking place.) some --- or even all --- the secrets in the system. In this case, it might be impossible to tell which signature is generated by the legitimate signer and which by the forger, but at least the fact of the tampering will be made evident.We define several variants of tamper-evidence, differing in their power to detect tampering. In all of these, we assume an equally powerful adversary: she adaptively controls all the inputs to the legitimate signer (i.e., all messages to be signed and their timing), and observes all his outputs; she can also adaptively expose all the secrets at arbitrary times.We provide tamper-evident schemes for all the variants. Some of our schemes use a combinatorial construction of a-separating sets, which might be of independent interest.The schemes are optimal: we prove tight lower-bounds. These lower bounds are perhaps the most surprising result of this paper. The lower bounds proofs are information-theoretic, and thus cannot be broken by introducing number-theoretic or algebraic complexity assumptions.Our mechanisms are purely cryptographic: the tamper-detection algorithm Div is stateless and takes no inputs except the two signatures, it uses no infrastructure (or other ways to conceal additional secrets), and relies on no hardware properties (except those implied by the standard cryptographic assumptions, such as random number generators).All constructions in this paper are based on arbitrary ordinary signature schemes and do not require random oracles.

REFERENCES

• 1: Michel Abdalla , Leonid Reyzin, A New Forward-Secure Digital Signature Scheme, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.116-129, December 03-07, 2000
• 2: R. Anderson. Invited lecture. Fourth Annual Conference on Computer and Communications Security, ACM (see http://www.ftp.cl.cam.ac.uk/ ftp/users/rja14/forwardsecure.pdf), 1997.
• 3: Mihir Bellare , Sara K. Miner, A Forward-Secure Digital Signature Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.431-448, August 15-19, 1999
• 4: Matt Blaze, High-Bandwidth Encryption with Low-Bandwidth Smartcards, Proceedings of the Third International Workshop on Fast Software Encryption, p.33-40, February 21-23, 1996
• 5: M. Blaze, J. Feigenbaum, and M. Naor. A formal treatment of remotely keyed encryption. In Advances in Cryptology -- EUROCRYPT '98, pages 251--265, 1998.
• 6: Dan Boneh , Matthew K. Franklin, Efficient Generation of Shared RSA Keys (Extended Abstract), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.425-439, August 17-21, 1997
• 7: R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, and A. Sahai. Exposure-resilient functions and all-or-nothing transforms. In B. Preneel, editor, Advances in Cryptology---EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 453--469. Springer-Verlag, 14--18~May 2000.
• 8: R. Canetti, S. Halevi, and A. Herzberg. Maintaining authenticated communication in the presence of break-ins. Journal of Cryptology, 13(1):61--105, Jan. 2000.
• 9: Yvo G. Desmedt , Yair Frankel, Threshold cryptosystems, Proceedings on Advances in cryptology, p.307-315, July 1989, Santa Barbara, California, United States
• 10: Yevgeniy Dodis , Jonathan Katz , Shouhuai Xu , Moti Yung, Key-Insulated Public Key Cryptosystems, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.65-82, May 02, 2002
• 11: Yevgeniy Dodis , Jonathan Katz , Shouhuai Xu , Moti Yung, Strong Key-Insulated Signature Schemes, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.130-144, January 06-08, 2003
• 12: U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
• 13: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 14: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 15: Johan Håstad , Jakob Jonsson , Ari Juels , Moti Yung, Funkspiel schemes: an alternative to conventional tamper resistance, Proceedings of the 7th ACM conference on Computer and communications security, p.125-133, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352619]
• 16: Amir Herzberg , Markus Jakobsson , Stanislław Jarecki , Hugo Krawczyk , Moti Yung, Proactive public key and signature systems, Proceedings of the 4th ACM conference on Computer and communications security, p.100-110, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266442]
• 17: G. Itkis. Intrusion-resilient signatures: Generic constructions, or defeating strong adversary with minimal assumptions. In Third Conference on Security in Communication Networks (SCN'02) {31}.
• 18: Gene Itkis , Leonid Reyzin, Forward-Secure Signatures with Optimal Signing and Verifying, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.332-354, August 19-23, 2001
• 19: Gene Itkis , Leonid Reyzin, SiBIR: Signer-Base Intrusion-Resilient Signatures, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.499-514, August 18-22, 2002
• 20: G. Itkis and P. Xie. Generalized key-evolving signatures, or how to foil an armed adversary. In 1st MiAn International Conference on Applied Cryptography and Network Security. Springer-Verlag, 2003.
• 21: L. Knudsen, editor. Advances in Cryptology--- EUROCRYPT 2002, Lecture Notes in Computer Science. Springer-Verlag, 28 April--2 May 2002.
• 22: A. Kozlov and L. Reyzin. Forward-secure signatures with fast key update. In Third Conference on Security in Communication Networks (SCN'02) {31}.
• 23: Hugo Krawczyk, Simple forward-secure signatures from any signature scheme, Proceedings of the 7th ACM conference on Computer and communications security, p.108-115, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352617]
• 24: Stefan Lucks, On the Security of Remotely Keyed Encryption, Proceedings of the 4th International Workshop on Fast Software Encryption, p.219-229, January 20-22, 1997
• 25: Tal Malkin , Daniele Micciancio , Sara K. Miner, Efficient Generic Forward-Secure Signatures with an Unbounded Number Of Time Periods, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.400-417, May 02, 2002
• 26: David Naccache , David Pointcheval , Christophe Tymen, Monotone Signatures, Proceedings of the 5th International Conference on Financial Cryptography, p.305-318, February 19-22, 2002
• 27: Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112605]
• 28: T. P. Pedersen. A threshold cryptosystem without a trusted party (extended abstract). In D. W. Davies, editor, Advances in Cryptology---EUROCRYPT 91, volume 547 of Lecture Notes in Computer Science, pages 522--526. Springer-Verlag, 8--11 Apr. 1991.
• 29: Torben Pryds Pedersen , Birgit Pfitzmann, Fail-Stop Signatures, SIAM Journal on Computing, v.26 n.2, p.291-330, April 1997 [doi>10.1137/S009753979324557X]
• 30: Ronald L. Rivest, Can We Eliminate Certificate Revocations Lists?, Proceedings of the Second International Conference on Financial Cryptography, p.178-183, February 23-25, 1998
• 31: Third Conference on Security in Communication Networks (SCN'02), Lecture Notes in Computer Science. Springer-Verlag, Sept. 12--13 2002.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Security

Keywords:
digital signatures, evolving cryptosystems, exposures, key evolution, tamper evidence