Guessing Attacks on Distributed-Storage Systems

The secrecy of a distributed-storage system for passwords is studied. The encoder, Alice, observes a length-
$n$
password and describes it using two hints, which she stores in different locations. The legitimate receiver, Bob, observes both hints and the eavesdropper, Eve, only one. In one scenario—the “guessing version”—we require that the expected number of guesses it takes Bob to guess the password approach one as
$n$
tends to infinity, and in the second—the “listsize version”—that the expected size of the shortest list that Bob must form to guarantee that it contain the password approach one. Assuming that Alice cannot control which hint Eve observes, the largest normalized (by
$n$
) exponent that can be guaranteed for the expected number of guesses it takes Eve to guess the password is characterized for each scenario. Key to the proof are new results on Massey–Arikan guessing, Bunte–Lapidoth task-encoding, and the close relation between them. A generalization that allows for Alice to produce
$\delta $
(not necessarily two) hints, for Bob to observe
$\nu $
(not necessarily two) of the hints, and for Eve to observe
$\eta $
(not necessarily one) of the hints is also discussed. This models scenarios where hints are stored on fail-prone disks.