Bounded-Retrieval Model with Keys Derived from Private Data

摘要

The Bounded Retrieval Model (BRM) was proposed at TCC 2006 (independently by Dziembowski and Di Crescenzo et al.). Essentially, the main idea of this model is to design cryptographic schemes with secret keys that are so large that it is infeasible for the adversary to steal them. One of the main technical problems of this idea is that it by definition requires the users to store large amounts of secret data on their disks. In this paper we put forward a technique for dealing with the problem of this large space consumption for protocols in BRM. More precisely, we propose a method to derive keys for such protocols on-the-fly from weakly random private data (like text documents or photos, users keep on their disks anyway for non-cryptographic purposes) in such a way that no extra storage is needed. We prove that any leakage-resilient protocol (belonging to a certain, arguably quite broad class) when run with a key obtained this way retains a similar level of security as the original protocol had. Additionally, we guarantee privacy of the data the actual keys are derived from. In other words: the adversary obtains essentially no information about the private data that is used for the key derivation. Our techniques are based on the disperser graphs. We have also implemented an experimental test of efficiency of our protocol. For arguably practical parameter settings the performance of the dispersing procedure is satisfactory.