Ross Anderson
Bruno Crispo
Abstract
We present a related family of authentication and digital signature protocols based on symmetric cryptographic primitives which perform substantially better than previous constructions. Previously, one-time digital signatures based on hash functions involved hundreds of hash function computations for each signature; we show that given online access to a timestamping service, we can sign messages using only two computations of a hash function. Previously, techniques to sign infinite streams involved one such one-time signature for each message block; we show that in many realistic scenarios a small number of hash function computations is sufficient. Previously, the Diffie Hellman protocol enabled two principals to create a confidentiality key from scratch: we provide an equivalent protocol for integrity, which enables two people who do not share a secret to set up a securely serialised channel into which attackers cannot subsequently intrude. In addition to being of potential use in real applications, our constructions also raise interesting questions about the definition of a digital signature, and the relationship between integrity and authenticity.
- 1. "The History of Subliminal Channels", GJ Simmons, in Proceedings of the First International Workshop on Information Hiding (Springer LNCS v 1174) pp 237-256. Google Scholar
Digital Library
- 2. "Verification of Treaty Compliance--Revisited", GJ Simmons, in Proceedings of the IEEE Symposium on Security and Privacy (IEEE, 1983) pp 61-66. Google ScholarDigital Library
- 3. "Constructing digital signatures from a one-way function", L Lamport, SRI TR CSL 98 (1979).Google Scholar
- 4. "A Digital Signature Based on a Conventional Encryption Function" RC Merkle, in Advances in Cryptology--Crypto 87 (Springer LNCS v 293) pp 369-378. Google ScholarDigital Library
- 5. "A Certified Digital Signature", RC Merkle, in Advances in Cryptology--Crypto 89 (Springer LNCS v 435) pp 218-238. Google ScholarDigital Library
- 6. "On-line/off-line digital signatures", S Even, O Goldreich, S Micali, in Advances in Cryptology--Crypto 89 (Springer LNCS v 435) pp 263-275. Google ScholarDigital Library
- 7. "Directed Acyclic Graphs, One-way Functions and Digital Signatures", D Bleichenbacher, UM Maurer, Advances in Cryptology--Crypto 94 (Springer LNCS v 839) pp 75-82. Google ScholarDigital Library
- 8. "The S/KEY One-Time Password System", N Hailer, in Proceedings of the ISOC Symposium on Network and Distributed System Security (February 1994, San Diego, CA) pp 151-157; see also RFCs 1704, 1760 and 1938.Google Scholar
- 9. "NetCard--A Practical Electronic Cash System", R Anderson, C Manifavas, C Sutherland, inProceedings of the Fourth Cambridge Security Protocols Workshop (Springer LNCS v 1189) pp 49-57. Google ScholarDigital Library
- 10. "PayWord and MicroMint: Two Simple Micropayment Schemes", RL Rivest, A Shamir, in Proceedings of the Fourth Cambridge Security Protocols Workshop (Springer LNCS v 1189) 69-87. Google ScholarDigital Library
- 11. "Electronic Payments of Small Amounts", TP Pedersen, in Proceedings of the Fourth Cambridge Security Protocols Workshop (Springer LNCS v 1189) 59-68. Google ScholarDigital Library
- 12. "New Directions in Cryptography", W Diffie, ME Hellman, in IEEE Transactions on Information Theory v IT-22 no 6 (November 1976) pp 644-654.Google Scholar
- 13. "The First Ten Years of Public-Key Cryptography", W Diffie, in Proceedings of the IEEE v 76 no 5 (May 88) pp 560-577.Google Scholar
- 14. "How To Prove Yourself: Practical Solutions to Identification and Signature problems", A Fiat, A Shamir, in Advances in Cryptology--CRYPTO 86, Springer LNCS v 263 pp 186-194. Google ScholarDigital Library
- 15. "A Digital Signature Scheme Secure Against Adaptive Chosen Message Attacks", S Goldwasser, S Micali, RL Rivest, in SIAM Journal of Computing v 17 no 2 (April 1988) pp 281-308. Google ScholarDigital Library
- 16. "Digital Signatures with Blindfold Arbitrators who Cannot Form Alliances", SG Akl, in Proceedings of the 1983 IEEE Computer Society Symposium on Security and Privacy, pp 129-135.Google Scholar
- 17. 'Applied Cryptography', B Schneier, Wiley 96.Google Scholar
- 18. "Universal One-Way Hash Functions and Their Cryptographic Application", M Naor, M Yung, in Proceedings of the 21st Annual ACM Symposium on the Theory of Computing (1989) pp 33-43. Google ScholarDigital Library
- 19. "One-Way Functions are Necessary and Sufficient for Digital Signatures", J Rompel, in Proceedings of the 22ndAnnual ACM Symposium on the Theory of Computing (1990) pp 387-394. Google ScholarDigital Library
- 20. 'Digital Signature Schemes--General Framework and Fail-Stop Signatures', B Pfitzmann, Springer LNCS v 1100. Google ScholarDigital Library
- 21. "How to Sign Digital Streams", R Gennaro, P Rohatgi, in Advances in Cryptology--CRYPTO 97, Springer LNCS v 1294 pp 180-197. Google ScholarDigital Library
- 22. "On fortifying key negotiation schemes with poorly chosen passwords", RJ Anderson, TMA Lomas, in Electronics letters v 30 no 12 (23rd July 1994) pp 1040-1041.Google Scholar
- 23. "How to Time-Stamp a Digital Document", S Haber, WS Stornetta, in Journal of Cryptology v 3 no 2 (1991) pp 99-112.Google Scholar
- 24. "How to Expose an Eavesdropper", RL Rivest, A Shamir, in Communications of the ACM v 27 no 4 (Apr 84) pp 393-395. Google ScholarDigital Library
- 25. "An Attack on the Interlock protocol When Used for Authentication", SM Bellovin, M Merritt, IEEE Transactions on Information Theory v 40 no 1 (Jan 94) pp 273-275.Google Scholar
- 26. "Secure Agreement Protocols: Reliable and Atomic Group Multicast in Rampart', MK Reiter, in Proceedings of the 1994 ACM Conference on Computer and Communications Security pp 68-80. Google ScholarDigital Library
- 27. "Maintaining Security in the Presence of Transient Faults", R Canetti, A Herzberg, in Advances in Cryptology--CRYPTO 94, Springer LNCS v 839 pp 425-438. Google ScholarDigital Library
- 28. "Network Randomization Protocol: A Proactive Pseudo-Random Generator", CS Chow, A Herzberg, in Usenix Security 95 pp 55-63.Google Scholar
- 29. "The Omega Key Management Service", MK Reiter, MK Franklin, JB Lacy, RA Wright, in Proceedings of the 1996 ACM Conference on Computer and Communications Security pp 38-47. Google ScholarDigital Library
Index Terms
- A new family of authentication protocols
Recommendations
Efficient Non-interactive Deniable Authentication Protocols
CIT '05: Proceedings of the The Fifth International Conference on Computer and Information TechnologyDeniable authentication protocol is an authentication protocol that allows a sender to authenticate a message for a receiver, in a way that the receiver cannot convince a third party that such authentication ever took place. In recent years, due to the ...
An Enhanced Secure Authentication Scheme for Vehicular Ad Hoc Networks Without Pairings
In the recent paper, Nai-Wei Lo and Jia-Lun Tsai mathematically proposed an efficient authentication scheme for vehicular sensor network. It uses elliptic curve cryptography based ID-based signature (IBS) for authentication purpose without pairings. The ...
Efficient proxy signature schemes using self-certified public keys
Elaborating on the merits of self-certified public key systems and message recovery signature schemes, this paper proposed a proxy signature scheme based on discrete logarithms and its variant based on elliptic curve discrete logarithms. The proposed ...
Comments