Key Establishment in Large Dynamic Groups Using One-Way Function Trees

Thumbnail Image

Files

5.pdf (235.8 KB)

Links to Files

https://ieeexplore.ieee.org/document/1199073

Permanent Link

http://doi.org/10.1109/TSE.2003.1199073
 http://hdl.handle.net/11603/12820

Collections

UMBC Center for Information Security and Assurance (CISA)
UMBC Computer Science and Electrical Engineering Department

Author/Creator

Author/Creator ORCID

Date

2003-05-21

Type of Work

conference papers and proceedings preprints
Text

Department

Program

Citation of Original Publication

Alan T. Sherman and David A. McGrew, Key Establishment in Large Dynamic Groups Using One-Way Function Trees, IEEE Transactions on Software Engineering, VOL. 29, NO. 5, MAY 2003, DOI: 10.1109/TSE.2003.1199073

Rights

This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
© 2003 IEEE

Subjects

broadcast encryption
conference keying
cryptography
cryptographic protocols
Dynamic Cryptographic Context Management (DCCM) Project
group keying
key agreement
key establishment
key management
logical key hierarchy (LKH)
one-way functions
one-way function chain (OFC)
one-way function tree (OFT)
secure conferences
secure group applications

Abstract

We present, implement, and analyze a new scalable centralized algorithm, called OFT, for establishing shared cryptographic keys in large, dynamically changing groups. Our algorithm is based on a novel application of one-way function trees. In comparison with the top-down logical key hierarchy (LKH) method of Wallner et al., our bottom-up algorithm approximately halves the number of bits that need to be broadcast to members in order to rekey after a member is added or evicted. The number of keys stored by group members, the number of keys broadcast to the group when new members are added or evicted, and the computational efforts of group members, are logarithmic in the number of group members. Among the hierarchical methods, OFT is the first to achieve an approximate halving in broadcast length, an idea on which subsequent algorithms have built. Our algorithm provides complete forward and backward security: Newly admitted group members cannot read previous messages, and evicted members cannot read future messages, even with collusion by arbitrarily many evicted members. In addition, and unlike LKH, our algorithm has the option of being member contributory in that members can be allowed to contribute entropy to the group key. Running on a Pentium II, our prototype has handled groups with up to 10 million members. This algorithm offers a new scalable method for establishing group session keys for secure large-group applications such as broadcast encryption, electronic conferences, multicast sessions, and military command and control.