On secure distributed storage under data theft

Consider a message coded for storage in which a fraction of the stored data is stolen. Ideally, the data remaining should allow message recovery, while the stolen data should reveal no information on the message. This gives a twist on the erasure wiretap channel, in that “Bob” no longer has a clear channel from “Alice”. We show how the storage capacity can, as in other multi-terminal coding problems, be approached using nested codes, and propose nested erasure codes using Krylov subspaces. These offer good performance and perfect secrecy, while integrating the nested code structure naturally.