International Association for Cryptologic Research

International Association
for Cryptologic Research


Lea Kissner


Provable Data Possession at Untrusted Stores
We introduce a model for {\em provable data possession} ($\pdp$) that allows a client that has stored data at an untrusted server to verify that the server possesses the original data without retrieving it. The model generates probabilistic proofs of possession by sampling random sets of blocks from the server, which drastically reduces I/O costs. The client maintains a constant amount of metadata to verify the proof. The challenge/response protocol transmits a small, constant amount of data, which minimizes network communication. Thus, the $\pdp$ model for remote data checking supports large data sets in widely-distributed storage systems. Previous work offers guarantees weaker than data possession, or requires prohibitive overhead at the server. We present two provably-secure $\pdp$ schemes that are more efficient than previous solutions, even when compared with schemes that achieve weaker guarantees. In particular, the overhead at the server is low (or even constant), as opposed to linear in the size of the data. Experiments using our implementation verify the practicality of $\pdp$ and reveal that the performance of $\pdp$ is bounded by disk I/O and not by cryptographic computation.
Provably Secure Subsitution of Cryptographic Tools
Lea Kissner David Molnar
Many cryptographic protocols secure against malicious players use specially designed cryptographic tools. Essentially, these special tools function much like less-expensive tools, but give extra `powers' to a reduction or simulation algorithm. Using these powers, cryptographers can construct a proof of security using standard techniques. However, these powers are not available to either the honest parties or the adversary. In a large class of protocols, by replacing the expensive, specially designed cryptographic tool with a corresponding less-expensive tool, we can improve the protocol's efficiency without changing the functionality available to either the adversary or the honest parties. The key motivating question we address in this paper is whether the new, `substituted' protocol is still secure. We introduce a framework for reasoning about this question. Our framework uses translators: special purpose oracles that map outputs of one cryptographic tool to corresponding outputs of a different tool. Translators are similar to, but generally weaker than, the ``angels'' of Prabhakaran and Sahai. We introduce the notion of substitution-friendly protocols and show that such protocols remain secure after substitution in our framework. We also leverage existing proofs of security; there is no need to re-prove security from scratch. We demonstrate our framework with a non-interactive non-malleable bit commitment protocol.