Our Publications

by Adrian Perrig, Dawn Song, and Doug Tygar
Abstract:
Secure media broadcast over the Internet poses unique security challenges. One problem access control to a large number of subscribers in a public broadcast. A common solution is to encrypt the broadcast data and to disclose the decryption key to legitimate receivers only. However, how do we securely and efficiently establish a shared secret among the legitimate receivers? And most importantly, how can we efficiently update the group key securely if receivers join or leave? How can we provide reliability for key update messages in a way that scales up to large groups? Recent research makes substantial progress to address these challenges. Current schemes feature efficient key update mechanisms assuming that the key updates are communicated reliably to the receivers. In practice, however, the principal impediment to achieve a scalable system is to distribute the key updates reliably to all receivers. We have designed and implemented ELK, a novel key distribution protocol, to address these challenges with the following features: - ELK features perfectly reliable, super-efficient member joins. - ELK uses smaller key update messages than previous protocols. - ELK features a mechanism that allows short hint messages to be used for key recovery allowing a tradeoff of communication overhead with member computation. - ELK proposes to append a small amount of key update information to data packets, such that the majority of receivers can recover from lost key update messages. - ELK allows to trade off security with communication overhead.
Reference:
ELK, a New Protocol for Efficient Large-Group Key Distribution. Adrian Perrig, Dawn Song, and Doug Tygar. In Proceedings of the IEEE Symposium on Security and Privacy 2001.
Bibtex Entry:
@InProceedings{PeSoTy2001,
    author =       {Adrian Perrig and Dawn Song and Doug Tygar},
    title =        {{ELK}, a New Protocol for Efficient Large-Group Key Distribution},
    url = {/publications/papers/elk.pdf},
    booktitle =    {Proceedings of the IEEE Symposium on Security and Privacy},
    year =         2001,
    month =        may,
    abstract =     {Secure media broadcast over the Internet poses unique security challenges.
    One problem access control to a large number of subscribers in a public
    broadcast. A common solution is to encrypt the broadcast data and to disclose
    the decryption key to legitimate receivers only.  However, how do we securely
    and efficiently establish a shared secret among the legitimate receivers? And
    most importantly, how can we efficiently update the group key securely if
    receivers join or leave? How can we provide reliability for key update
    messages in a way that scales up to large groups?

    Recent research makes substantial progress to address these challenges. Current
    schemes feature efficient key update mechanisms assuming that the key updates
    are communicated reliably to the receivers. In practice, however, the
    principal impediment to achieve a scalable system is to distribute the key
    updates reliably to all receivers. We have designed and implemented ELK, a novel
    key distribution protocol, to address these challenges with the following
    features:
    - ELK features perfectly reliable, super-efficient member joins.
    - ELK uses smaller key update messages than previous protocols.
    - ELK features a mechanism that allows short hint messages to be used for
    key recovery allowing a tradeoff of communication overhead with member
    computation.
    - ELK proposes to append a small amount of key update information to data
    packets, such that the majority of receivers can recover from lost key
    update messages.
    - ELK allows to trade off security with communication overhead.}
}