Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Alice pays Bob $5/month to host a gigantic file for her. She wants to occasionally verify that Bob is actually hosting the file. To do this, she selects random blocks from the file, and challenges Bob to hash those same blocks with her chosen salt. The digests should match.

This is a solved problem because Bob won't know what blocks in the file Alice will audit next. But what can be done if Bob decides to host in multiple places?

Bob proposes to Alice that he can host the file on four more hosts, for a total of $25/month. Alice agrees, and continues using her old audit method. But Bob never actually hosted the files in more than one place; every time Alice audited a host without the file, that host asked Bob's main host for the answers, and sent them to Alice.

share|improve this question
Alice can get a very low ping connection to one of the places and require that she receives a response faster than it would take for a light-speed signal to go back and forth between that place and the closest other relevant place. $\;$ – Ricky Demer Jul 10 '14 at 15:46
Or she could store different copies of the data encrypted with e.g. separate keys. Since Bob knows neither the plaintext nor the keys, he can't show a hash of the ciphertext without storing all the copies. – otus Jul 10 '14 at 23:06
@otus This requires sending to Bob $m$ encryptions of the same file, where $m$ is the number of mirrors. – Dmitry Khovratovich Jul 11 '14 at 9:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.