Addressing the shortcomings of one-way chains

ABSTRACT

One-way hash chains have been the preferred choice, over the symmetric and asymmetric key cryptography, in security setups where efficiency mattered; despite the ephemeral confidentiality and authentication they assure. Known constructions of one-way chains (for example, SHA-1 based), only ensure the forward secrecy and have limitations over their length i.e., a priori knowledge of chain's length is necessary before constructing it. In this paper, we will see how our approach, based on chameleon functions, leads to the generation of practically unbounded one-way chains with constant storage and computational requirements. We provide the construction and advantages of our proposal with the help of a secure group communication setup. We also provide the implementation details of our construction and argue its suitability for security setups, where one cannot a priori determine the longevity of the setup.

REFERENCES

• 1: Michel Abdalla , Mihir Bellare, Increasing the Lifetime of a Key: A Comparative Analysis of the Security of Re-keying Techniques, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.546-559, December 03-07, 2000
• 2: G. Ateniese, D. H. Chou, B. de Medeiros, and G. Tsudik. Sanitizable signatures. ESORICS: Proceedings of the 10th European Symposium on Research in Computer Security, Springer--Verlag, LNCS(3679):159--177, 2005.
• 3: G. Ateniese and B. de Medeiros. Identity-based chameleon hash and applications. FC: Financial Cryptography, 8th International Conference, Springer--Verlag, LNCS(3110):164--180, 2004.
• 4: G. Ateniese and B. de Medeiros. On the key exposure problem in chameleon hashes. SCN: Security in Communication Networks, 4th International Conference, Springer--Verlag, LNCS(3352):165--179, 2004.
• 5: Boaz Barak , Russell Impagliazzo , Avi Wigderson, Extracting Randomness Using Few Independent Sources, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.384-393, October 17-19, 2004 [doi>10.1109/FOCS.2004.29]
• 6: Joan F. Boyar , Stuart A. Kurtz, A discrete logarithm implementation of perfect zero-knowledge blobs, Journal of Cryptology, v.2 n.2, p.63-76, 1990
• 7: Stefan A. Brands, Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy, MIT Press, Cambridge, MA, 2000
• 8: Gilles Brassard , David Chaum , Claude Crépeau, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, v.37 n.2, p.156-189, October 1988 [doi>10.1016/0022-0000(88)90005-0]
• 9: X. Chen, F. Zhang, and K. Kim. Chameleon hashing without key exposure. ISC: Information Security, 7th International Conference, Springer--Verlag, LNCS(3225):87--98, 2004.
• 10: R. Di Pietro, A. Durante, and L. V. Mancini. A reliable key authentication schema for secure multicast communications. In SRDS: 22nd Symposium on Reliable Distributed Systems, pages 231--240. IEEE Computer Society, 2003.
• 11: Roberto Di Pietro , Luigi V. Mancini, Security and privacy issues of handheld and wearable wireless devices, Communications of the ACM, v.46 n.9, p.74-79, September 2003 [doi>10.1145/903893.903897]
• 12: Warwick Ford , Michael S. Baum, Secure Electronic Commerce: Building the Infrastructure for Digital Signatures and Encryption, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 13: 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]
• 14: N. M. Haller. The S/KEY one-time password system. NDSS: Proceedings of the ISOC Symposium on Network and Distributed System Security, pages 151--157, 1994.
• 15: H. Krawczyk and T. Rabin. Chameleon hashing and signatures. NDSS: Proceedings of the ISOC Symposium on Network and Distributed System Security, pages 143--154, 2000.
• 16: Leslie Lamport, Password authentication with insecure communication, Communications of the ACM, v.24 n.11, p.770-772, Nov. 1981 [doi>10.1145/358790.358797]
• 17: A. Pannetrat and R. Molva. Efficient multicast packet authentication. NDSS: Proceedings of the ISOC Symposium on Network and Distributed System Security, 2003.
• 18: Jung Min Park , Edwin K. P. Chong , Howard Jay Siegel, Efficient Multicast Packet Authentication Using Signature Amortization, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.227, May 12-15, 2002
• 19: A. Perrig, R. Canetti, D. X. Song, and J. D. Tygar. Efficient and secure source authentication for multicast. NDSS: Proceedings of the ISOC Symposium on Network and Distributed System Security, 2001.
• 20: Adrian Perrig , J. D. Tygar , Dawn Song , Ran Canetti, Efficient Authentication and Signing of Multicast Streams over Lossy Channels, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.56, May 14-17, 2000
• 21: Adi Shamir , Yael Tauman, Improved Online/Offline Signature Schemes, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.355-367, August 19-23, 2001
• 22: Chung Kei Wong , Mohamed Gouda , Simon S. Lam, Secure group communications using key graphs, IEEE/ACM Transactions on Networking (TON), v.8 n.1, p.16-30, Feb. 2000 [doi>10.1109/90.836475]
• 23: Yang Richard Yang , X. Steve Li , X. Brian Zhang , Simon S. Lam, Reliable group rekeying: a performance analysis, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.27-38, August 2001, San Diego, California, United States

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

  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:
Design, Management, Security

Keywords:
chameleon hash, one-way chain, secure group management for multicast