Simple Tree-Based Algorithm Whose Average Case Behavior Isn't
Ilya Mironov, Microsoft Research
Oct 3, 2003, Wean 7220, 3:30pm

Abstract:
In this talk we will explore a surprising average-case analysis of a simple tree-based algorithm for secure broadcast. A proof of an estimate obtained by simulations will take us to analysis of complex poles, Mellin transform and tiny fluctuations which are as small as 10^-6.

Any secure broadcast scheme, such as distribution of DVDs, satellite TV, or pay-per-view, has to solve the problem of user revocation. Some users who have discontinued their subscription or were found guilty of leaking their keys must be prevented from decrypting future broadcasts. The problem is most difficult when the receivers are stateless, i.e. the broadcast key cannot be easily updated. One ill-fated example of such a system is CCS made famous by the DeCCS cracking program. A scheme for broadcast encryption for stateless receivers due to Naor, Naor, and Lotspiech proposed in 2001 broke the information-theoretic lower bound for a secure broadcast with user revocation. One crucial parameter of that scheme is the overhead as a function of the number of revoked users. We analyze its average case complexity using the method of Mellin transform pioneered by de Bruijn and Knuth.

Bio
Ilya Mironov (Microsoft Research, Silicon Valley Campus) works in theoretical cryptology and cryptanalysis. He graduated from Stanford in 2003 with Ph.D. thesis about card shuffles and their applications in cryptography.