Quantifying the computational security of multi-user systems
Speaker: Mark Christiansen (Hamilton Institute, NUIM)
Time: 4:00pm
Date: Monday January 27th 2014
Location: CASL Seminar Room, Block 8, Belfield Office Park
Abstract:
What is the correct metric to use to estimate the number of guesses required to guess a string? Here we assume that an inquisitor may only ask about a string at a time but that the distribution used to pick the string is known. In 1994 Massey showed the Shannon entropy does not give the full picture, only giving a lower bound on the expected number of guesses. In 1996 Arikan showed that as strings become longer the correct quantity is the Renyi entropy with parameter 1/2 that gives the growth rate of the average guesswork. Arikan's work in 1996 has been expanded upon in various directions, here we present the problem of V users each picking a string independently from a finite list and an inquisitor must guess U of them, this could be representative of distributed storage. Recent results allow us to garner a collection of results on multi user guesswork including that the growth rate of the average guesswork can again be quantified. In the case where each user's string statistics are identical, the specific Shannon entropy of the string source is a tight, universal lower bound on the growth rate of the average guesswork bringing the work of Massey full circle. This talk is based on work with K. Duffy (NUIM), F. du Pin Calmon (MIT) and M. Medard (MIT).
Series: Algebra & Number Theory Seminar Series
Social Media Links