The Network Coding and Reliable Communications Group, Professor Muriel Medard


Seminar: Quantifying the Computational Security of Multi-User Systems


January 23, 2014, 4:00pm

MIT Room: 32-155

Ken Duffy

National University of Ireland Maynooth



In an elegant one page paper presented at ISIT in 1994, James Massey asked the following question: how does one metrize the computational security of a single user system? He established that the Shannon entropy of the password source was not the correct measure. Starting with seminal work of Erdal Arikan, published in 1996, it was established that as strings to be guessed become long, the specific Renyi entropy with parameter 1/2 governs the average guessing growth rate as a function of string length.

Motivated by distributed storage in the cloud and other applications, in this talk we expand this question to address the computational security of multi-user systems, aiming to quantify the security cost that comes from having more than one user. Within a collection of other results, coming full circle, we prove that if users pick their strings independently and the users’s string statistics are the same, then the specific Shannon entropy of the string source is a tight, universal lower bound on the guesswork growth rate.

This talk is based on work with M. Christiansen (NUIM), F. du Pin Calmon (MIT) and M. Medard (MIT),



Ken Duffy received the B.A (mod) and Ph.D. in Mathematics from Trinity College Dublin in 1996 and 2000, respectively.

He is currently a Professor at the Hamilton Institute, an applied math research centre of the National University of Ireland Maynooth. He is a co-founder of the Royal Statistical Society’s Applied Probability Section and his research interests encompass probability and its applications to engineering and science, particularly to communication networks and biology. More information is available at