Unconditionally secure ring authentication

ABSTRACT

We propose ring authentication in unconditionally secure setting. In a ring authentication system a sender can choose a set of users and construct an authenticated message for a receiver such that the receiver can verify authenticity of the message with respect to the user group chosen by the real sender. The sender will be unconditionally secure even if the receiver has corrupted up to c users and has access to up to ℓ past messages in the system. This functionality is similar to the one provided by ring signature systems with the difference that protection is against an adversary with unlimited power. (This also implies that the verification is not public and is by group members.) In ring signatures an adversary with unlimited computational power can always forge signed messages attributing them to groups of his choice. In our proposed systems the success chance of the adversary can be reduced to the required security of the system. We define model, propose a generic construction whose security is reduced to the security of its building blocks, and give concrete examples of this construction. The construction can also be used in computational setting resulting in ring authentication systems without public key cryptography.

REFERENCES

• 1: M. Bellare, D. Micciancio, and B. Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions. In E. Biham, editor, EUROCRYPT, volume 2656 of Lecture Notes in Computer Science, pages 614--629. Springer, 2003.
• 2: Carlo Blundo , Alfredo De Santis , Ugo Vaccaro , Amir Herzberg , Shay Kutten , Moti Yong, Perfectly secure key distribution for dynamic conferences, Information and Computation, v.146 n.1, p.1-23, Oct. 10, 1998 [doi>10.1006/inco.1998.2717]
• 3: Ernie Brickell , Jan Camenisch , Liqun Chen, Direct anonymous attestation, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030103]
• 4: D. Chaum, The dining cryptographers problem: unconditional sender and recipient untraceability, Journal of Cryptology, v.1 n.1, p.65-75, 1988
• 5: D. Chaum and E. van Heyst. Group signatures. In D. W. Davies, editor, EUROCRYPT, volume 547 of Lecture Notes in Computer Science, pages 257--265. Springer, 1991.
• 6: Yvo Desmedt , Yair Frankel , Moti Yung, Multi-receiver/multi-sender network security: efficient authenticated multicast/feedback, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 3), p.2045-2054, May 1992, Florence, Italy
• 7: Yvo Desmedt , Rei Safavi-Naini , Huaxiong Wang , Lynn Batten , Chris Charnes , Josef Pieprzyk, Broadcast anti-jamming systems, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.35 n.2-3, p.223-236, Feb. 2001 [doi>10.1016/S1389-1286(00)00169-9]
• 8: Y. Desmedt and V. Viswanathan. Unconditionally secure dynamic conference key distribution. In ISIT, page 383, Cambridge, MA, USA, 1998. IEEE Press.
• 9: Cunsheng Ding , Xuesong Wang, A coding theory construction of new systematic authentication codes, Theoretical Computer Science, v.330 n.1, p.81-99, 31 January 2005 [doi>10.1016/j.tcs.2004.09.011]
• 10: Y. Dodis, L. Reyzin, and A. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In C. Cachin and J. Camenisch, editors, EUROCRYPT, volume 3027 of Lecture Notes in Computer Science, pages 523--540. Springer, 2004.
• 11: M. E. Dyer, T. I. Fenner, A. M. Frieze, and A. Thomason. On key storage in secure networks. J. Cryptology, 8(4):189--200, 1995.
• 12: 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
• 13: Juan A. Garay , Jessica Staddon , Avishai Wool, Long-Lived Broadcast Encryption, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.333-352, August 20-24, 2000
• 14: W. H. Kautz and R. C. Singleton. Nonrandom binary superimposed codes. IEEE Transactions on Information Theory, 10(4):363--377, 1964.
• 15: A. Kiayias and M. Yung. Efficient secure group signatures with dynamic joins and keeping anonymity against group managers. In Dawson and S. Vaudenay, editors, MYCRYPT, volume 3715 of Lecture Notes in Computer Science, pages 151--170. Springer, 2005.
• 16: H. Krawczyk , M. Bellare , R. Canetti, HMAC: Keyed-Hashing for Message Authentication, RFC Editor, 1997
• 17: Theodore Dennis Krovetz , Phillip Rogaway, Software-optimized universal hashing and message authentication, 2000
• 18: Ravi Kumar , Sridhar Rajagopalan , Amit Sahai, Coding Constructions for Blacklisting Problems without Computational Assumptions, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.609-623, August 15-19, 1999
• 19: Kaoru Kurosawa , Satoshi Obana, Characterisation of (k, n) Multi-receiver Authentication, Proceedings of the Second Australasian Conference on Information Security and Privacy, p.204-215, July 07-09, 1997
• 20: Keith M. Martin , Reihaneh Safavi-Naini, Multisender authentication systems with unconditional security, Proceedings of the First International Conference on Information and Communication Security, p.130-143, November 11-14, 1997
• 21: C. J. Mitchell , F. C. Piper, Key storage in secure networks, Discrete Applied Mathematics, v.21 n.3, p.215-228, October 1988 [doi>10.1016/0166-218X(88)90068-6]
• 22: Moni Naor, Deniable Ring Authentication, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.481-498, August 18-22, 2002
• 23: L. Nguyen and R. Safavi-Naini. Efficient and provably secure trapdoor-free group signature schemes from bilinear pairings. In P. J. Lee, editor, ASIACRYPT, volume 3329 of Lecture Notes in Computer Science, pages 372--386. Springer, 2004.
• 24: Ronald L. Rivest , Adi Shamir , Yael Tauman, How to Leak a Secret, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.552-565, December 09-13, 2001
• 25: J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100269]
• 26: R. Safavi-Naini and P. Wild. Bounds on authentication systems in query model. In Theory and Practice in Information-Theoretic Security, ITW'05, pages 85--91. IEEE Press, 2005.
• 27: A. Serjantov and G. Danezis. Towards an information theoretic metric for anonymity. In R. Dingledine and P. F. Syverson, editors, Privacy Enhancing Technologies, volume 2482 of Lecture Notes in Computer Science, pages 41--53. Springer, 2002.
• 28: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 29: P. W. Shor. Quantum computing. In ICM: Proceedings of the International Congress of Mathematicians, 1998.
• 30: Gustavus J Simmons, Authentication theory/coding theory, Proceedings of CRYPTO 84 on Advances in cryptology, p.411-431, August 1985, Santa Barbara, California, United States
• 31: Doug R. Stinson, On Some Methods for Unconditionally Secure Key Distributionand Broadcast Encryption, Designs, Codes and Cryptography, v.12 n.3, p.215-243, Nov. 1997 [doi>10.1023/A:1008268610932]
• 32: Doug R. Stinson , Tran Van Trung, Some New Results on Key Distribution Patterns and BroadcastEncryption, Designs, Codes and Cryptography, v.14 n.3, p.261-279, Sept. 1998 [doi>10.1023/A:1008209004667]
• 33: D. R. Stinson, T. van Trung, and R. Wei. Secure frameproof codes, key distribution patterns, group testing algorithms and related structures. J. Stat. Planning and Inference, 86(2):595--617, 2000.
• 34: D. R. Stinson and R. Wei. Generalized cover-free families. Discrete Mathematics, 279(1--3):463--477, 2004.
• 35: M. N. Wegman and L. Carter. New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci., 22(3):265--279, 1981.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Security

Keywords:
authentication codes, ring signature, unconditional security