More Web Proxy on the site http://driver.im/

Article

Asynchronous group key exchange with failures

Authors:

Christian Cachin,

Reto StroblAuthors Info & Claims

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

Pages 357 - 366

https://doi.org/10.1145/1011767.1011820

Published: 25 July 2004 Publication History

Abstract

Group key exchange protocols allow a group of servers communicating over an asynchronous network of point-to-point links to establish a common key, such that an adversary which fully controls the network links (but not the group members) cannot learn the key. Currently known group key exchange protocols rely on the assumption that all group members participate in the protocol and if a single server crashes, then no server may terminate the protocol. In this paper, we propose the first purely asynchronous group key exchange protocol that tolerates a minority of servers to crash. Our solution uses a constant number of rounds, which makes it suitable for use in practice. Furthermore, we also investigate how to provide forward secrecy with respect to an adversary that may break into some servers and observe their internal state. We show that any group key exchange protocol among n servers that tolerates t_c > 0 servers to crash can only provide forward secrecy if the adversary breaks into less than n - 2t_c servers, and propose a group key exchange protocol that achieves this bound.

References

[1]

Y. Amir, Y. Kim, C. Nita-Rotaru, J. Schultz, J. Stanton, and G. Tsudik, "Secure group communication using robust contributory key agreement," in IEEE Transaction on Parallel and Distributed Systems, to appear, 2004.]]

Digital Library

[2]

Y. Amir, Y. Kim, C. Nita-Rotaru, J. Schultz, J. Stanton, and G. Tsudik, "Exploring robustness in group key agreement," in Proc. 21st IEEE International Conference on Distributed Computing Systems, pp. 399--409, 2001.]]

Digital Library

[3]

G. Ateniese, M. Steiner, and G. Tsudik, "New multiparty authentication services and key agreement protocols," Journal of Selected Areas in Communications IEEE, vol. 18, no. 4, pp. 1--13, 2000.]]

Digital Library

[4]

H. Attiya and J. Welch, Distributed Computing: Fundamentals, Simulations, and Advanced Topics. McGraw-Hill, 1998.]]

Digital Library

[5]

M. Bellare, D. Pointcheval, and P. Rogaway, "Authenticated key exchange secure against dictionary attacks," in Advances in Cryptology: Eurocrypt '00, 2000.]]

[6]

C. Boyd, "On key agreement and conference key agreement," in Proc. 2nd Australasian Conference on Information Security and Privacy (ACISP), 1997.]]

Digital Library

[7]

E. Bresson, O. Chevassut, D. Pointcheval, and J. Quisquater, "Provably authenticated group Diffie-Hellman key exchange," in Proc. 8th ACM Conference on Computer and Communication Secuirty (CCS), 2001.]]

Digital Library

[8]

M. Burmester and Y. Desmedt, "A secure and efficient conference key distribution system," in Advances in Cryptology: Eurocrypt '94, 1994.]]

[9]

C. Cachin, K. Kursawe, F. Petzold, and V. Shoup, "Secure and efficient asynchronous broadcast protocols (extended abstract)," in Advances in Cryptology: Crypto '01, 2001.]]

Digital Library

[10]

C. Cachin, K. Kursawe, and V. Shoup, "Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography," in Proc. 19th ACM Symposium on Principles of Distributed Computing (PODC), pp. 123--132, 2000.]]

Digital Library

[11]

R. Canetti, U. Feige, O. Goldreich, and M. Naor, "Adaptively secure computation," in Proc. 28th Symposium on Theory of Computing (STOC), pp. 639--648, 1996.]]

Digital Library

[12]

R. Canetti, "Universally composable security: A new paradigm for cryptographic protocols," in Proc. 42nd IEEE Symposium on Foundations of Computer Science (FOCS), 2001.]]

Digital Library

[13]

R. Canetti and T. Rabin, "Fast asynchronous Byzantine agreement with optimal resilience," in Proc. 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 42--51, 1993.]]

Digital Library

[14]

T. D. Chandra and S. Toueg, "Unreliable failure detectors for reliable distributed systems," Journal of the ACM, vol. 46, no. 4, pp. 685--722, 1996.]]

Digital Library

[15]

G. Chockler, I. Keidar, and R. Vitenberg, "Group communication specifications: A comprehensive study," ACM Computing Surveys, vol. 4, pp. 427--469, December 2001.]]

Digital Library

[16]

O. Goldreich, S. Goldwasser, and S. Micali, "How to construct random functions," Journal of the ACM, vol. 33, pp. 792--807, Oct. 1986.]]

Digital Library

[17]

S. Goldwasser and S. Micali, "Probabilistic encryption," Journal of Computer and System Sciences, vol. 28, pp. 270--299, 1984.]]

[18]

S. Goldwasser, S. Micali, and C. Rackoff, "The knowledge complexity of interactive proof-systems," SIAM Journal of Computing, vol. 18, pp. 186--208, Feb. 1989.]]

Digital Library

[19]

I. Ingemarasson, D. Tang, and C. Wong, "A conference key distribution system," IEEE Transactions on Information Theory, vol. 28, no. 5, pp. 714--720, 1982.]]

Digital Library

[20]

M. Just and S. Vaudenay, "Authenticated multi-party key agreement," in Advances in Cryptology: Asiacrypt '96, 1996.]]

Digital Library

[21]

J. Katz and M. Yung, "Scalable protocols for authenticated group key exchange," in Advances in Cryptology: Crypto'03, 2003.]]

[22]

J. Nielsen, "A threshold pseudorandom function construction and its applicatoins," in Advances in Cryptology: Crypto'02, 2002.]]

Digital Library

[23]

B. Pfitzmann and M. Waidner, "A model for asynchronous reactive systems and its application to secure message transmission," in Proc. 22nd IEEE Symposium on Security & Privacy, pp. 184--200, 2001.]]

Digital Library

[24]

O. Rodeh, K. P. Birman, and D. Dolev, "A study of group rekeying," Technical Report TR2000-1791, Cornell University Computer Science, March 2000.]]

Digital Library

[25]

A. Shamir, "How to share a secret," Communications of the ACM, vol. 22, pp. 612--613, Nov. 1979.]]

Digital Library

[26]

M. Steiner, G. Tsudik, and M. Waidner, "Key agrement in dynamic peer groups," IEEE Transactions on Parallel and Distributed Systems, vol. 11, no. 8, pp. 769--780, 2000.]]

Digital Library

[27]

M. Steiner, Secure Group Key Agreement. PhD thesis, Naturwissenschaftlich- Technische Fakultät der Universität des Saarlandes, Saarbrücken, March 2002.]]

[28]

W. Tzeng, "A practical and secure fault-tolerant conference key agreement protocol," in Proc. Third International Workshop on Practice and Theory in Public Key Cryptography (PKC), 2000.]]

Digital Library

Cited By

Kemmoe VKwon YHussain RCho SSon J(2023)Leveraging Smart Contracts for Secure and Asynchronous Group Key Exchange Without Trusted Third PartyIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2022.318997720:4(3176-3193)Online publication date: 1-Jul-2023
https://doi.org/10.1109/TDSC.2022.3189977
Cohn-Gordon KCremers CGarratt LMillican JMilner KLie DMannan MBackes MWang X(2018)On Ends-to-Ends EncryptionProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243747(1802-1819)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3243734.3243747
Alarifi SWolthusen S(2013)Robust Coordination of Cloud-Internal Denial of Service AttacksProceedings of the 2013 International Conference on Cloud and Green Computing10.1109/CGC.2013.28(135-142)Online publication date: 30-Sep-2013
https://dl.acm.org/doi/10.1109/CGC.2013.28
Show More Cited By

Index Terms

Asynchronous group key exchange with failures
1. Security and privacy
  1. Cryptography
  2. Systems security
    1. Operating systems security
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles
        Organizing principles for web applications

Recommendations

A Universally Composable Group Key Exchange Protocol with Minimum Communication Effort
SCN '08: Proceedings of the 6th international conference on Security and Cryptography for Networks

The universal composability (UC) framework by Canetti [15] is a general-purpose framework for designing secure protocols. It ensures the security of UC-secure protocols under arbitrary compositions. As key exchange protocols (KEs) belong to the most ...
Universally composable contributory group key exchange
ASIACCS '09: Proceedings of the 4th International Symposium on Information, Computer, and Communications Security

We treat the security of group key exchange (GKE) in the universal composability (UC) framework. Analyzing GKE protocols in the UC framework naturally addresses attacks by malicious insiders. We define an ideal functionality for GKE that captures ...
Password-Authenticated Group Key Exchange: A Cross-Layer Design
Special Issue on Internet of Things (IoT): Smart and Secure Service Delivery

Two-party password-authenticated key exchange (2PAKE) protocols provide a natural mechanism for secret key establishment in distributed applications, and they have been extensively studied in past decades. However, only a few efforts have been made so ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

July 2004

422 pages

ISBN:1581138024

DOI:10.1145/1011767

General Chair:
Soma Chaudhuri
Iowa State University
,
Program Chair:
Shay Kutten
Technion

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC04

Sponsor:

PODC04: Principles of Distributed Computing 2004

July 25 - 28, 2004

Newfoundland, St. John's, Canada

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
479
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kemmoe VKwon YHussain RCho SSon J(2023)Leveraging Smart Contracts for Secure and Asynchronous Group Key Exchange Without Trusted Third PartyIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2022.318997720:4(3176-3193)Online publication date: 1-Jul-2023
https://doi.org/10.1109/TDSC.2022.3189977
Cohn-Gordon KCremers CGarratt LMillican JMilner KLie DMannan MBackes MWang X(2018)On Ends-to-Ends EncryptionProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243747(1802-1819)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3243734.3243747
Alarifi SWolthusen S(2013)Robust Coordination of Cloud-Internal Denial of Service AttacksProceedings of the 2013 International Conference on Cloud and Green Computing10.1109/CGC.2013.28(135-142)Online publication date: 30-Sep-2013
https://dl.acm.org/doi/10.1109/CGC.2013.28
Bilogrevic IJadliwala MKalkan KHubaux JAad I(2011)Privacy in mobile computing for location-sharing-based servicesProceedings of the 11th international conference on Privacy enhancing technologies10.5555/2032162.2032167(77-96)Online publication date: 27-Jul-2011
https://dl.acm.org/doi/10.5555/2032162.2032167
Hatano TMiyaji ASato T(2011)T-robust scalable group key exchange protocol with O(log n) complexityProceedings of the 16th Australasian conference on Information security and privacy10.5555/2029853.2029870(189-207)Online publication date: 11-Jul-2011
https://dl.acm.org/doi/10.5555/2029853.2029870
Bilogrevic IJadliwala MHubaux JAad INiemi VSandhu RBertino E(2011)Privacy-preserving activity scheduling on mobile devicesProceedings of the first ACM conference on Data and application security and privacy10.1145/1943513.1943549(261-272)Online publication date: 21-Feb-2011
https://dl.acm.org/doi/10.1145/1943513.1943549
Jarecki SJihye Kim Tsudik G(2011)Flexible Robust Group Key AgreementIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2010.12822:5(879-886)Online publication date: May-2011
https://doi.org/10.1109/TPDS.2010.128
Bilogrevic IJadliwala MKumar PWalia SHubaux JAad INiemi V(2011)Meetings through the cloudJournal of Systems and Software10.1016/j.jss.2011.04.02784:11(1910-1927)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1016/j.jss.2011.04.027
Bilogrevic IJadliwala MKalkan KHubaux JAad I(2011)Privacy in Mobile Computing for Location-Sharing-Based ServicesPrivacy Enhancing Technologies10.1007/978-3-642-22263-4_5(77-96)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22263-4_5
Brecher TBresson EManulis M(2009)Fully Robust Tree-Diffie-Hellman Group Key ExchangeProceedings of the 8th International Conference on Cryptology and Network Security10.1007/978-3-642-10433-6_33(478-497)Online publication date: 23-Nov-2009
https://dl.acm.org/doi/10.1007/978-3-642-10433-6_33
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents