Paper 2018/514

Weak Compression and (In)security of Rational Proofs of Storage

Ben Fisch and Shashwat Silas

Abstract

We point out an implicit unproven assumption underlying the security of rational proofs of storage that is related to a concept we call weak randomized compression. This is a class of interactive proofs designed in a security model with a rational prover who is encouraged to store data (possibly in a particular format), as otherwise it either fails verification or does not save any storage costs by deviating (in some cases it may even increase costs by ``wasting" the space). Weak randomized compression is a scheme that takes a random seed $r$ and a compressible string $s$ and outputs a compression of the concatenation $r \circ s$. Strong compression would compress $s$ by itself (and store the random seed separately). In the context of a storage protocol, it is plausible that the adversary knows a weak compression that uses its incompressible storage advice as a seed to help compress other useful data it is storing, and yet it does not know a strong compression that would perform just as well. It therefore may be incentivized to deviate from the protocol in order to save space. This would be particularly problematic for proofs of replication, designed to encourage provers to store data in a redundant format, which weak compression would likely destroy. We thus motivate the question of whether weak compression can always be used to efficiently construct strong compression, and find (negatively) that a black-box reduction would imply a universal compression scheme in the random oracle model for all compressible efficiently sampleable sources. Implausibility of universal compression aside, we conclude that constructing this black-box reduction for a class of sources is at least as hard as directly constructing a universal compression scheme for that class.

Note: Put in a missing sentence.