Alice wants to store key:value pairs with Bob. The goal of the exercise is for Alice to be able to use Bob as a reliable data storage service, even if Bob were untrustworthy. A (correctly implemented) MAC/AEAD/Signature means Bob cannot tamper with records. But basic authentication is not sufficient to ensure that Bob returns the correct record, because it does not stop Bob from replaying old records.

Here is an example. Assume that somewhere among key and value is a correctly implemented secure authenticator that Alice can use to validate received records:

  • Alice sets key1:value1 with Bob
    • Bob stores it correctly
  • Alice later overwrites key1 and sets key1:value2 with Bob where value2 != value1
    • When Alice queries key1 from Bob, she expects to receive value2
    • But Bob could save and replay value1
      • HMAC tag verification will pass because both records were created by Alice

Thus simply authenticating the data is not sufficient. One naturally reaches for some kind of nonce. However because it is possible for Alice to lose (or not have) the state and rely on recovering that state from Bob (the whole point of the exercise) we must address the case where Alice has no state and consequently no longer has the most recent nonce. This appears to be the hard part.

How can Alice ensure that she receives the most recent record from Bob?

Other goals/security issues

A malicious Bob can still refuse to store records or delete records. Considering that these are natural events that could occur during benign operation (e.g. Bob runs out of space), it's not clear that preventing these capabilities is strictly necessary or beneficial.

There may be other goals regarding secure storage/backup that I am unaware of. An explanation or paper covering the standard formalized security notions of this subfield would great.

  • $\begingroup$ How often do updates occur, in particular could a timestamp be useful? $\endgroup$ Nov 29, 2021 at 21:31
  • $\begingroup$ I don't think this has a solution. If she cannot reliably store any information in her own node she cannot reliably retrieve any information. It really depends on what do you mean state. If she can be stateless I don't think she can reliably retrieve anything. There are related papers like this one : eprint.iacr.org/2007/202.pdf but they don't cover stateless participants. $\endgroup$
    – tur11ng
    Nov 30, 2021 at 0:48

1 Answer 1


From "Titanium: A Metadata-Hiding File-Sharing System with Malicious Security":

Moreover, integrity, which is not ensured in [34], is critical. Malicious users should not be able to write to other users’ files. Malicious servers should not be able to serve incorrect or outdated files without being caught. Achieving integrity in the presence of a malicious adversary is challenging, and sometimes impossible. For example, in any single-server construction, it is impossible to have integrity [36–41] against the malicious server because the server can always present different versions of the files to different users, which we discuss in §II-B.

There is an impossibility result [36–41] saying that single-server storage systems cannot offer integrity guarantees against the malicious server, as the server can always present an old version of the storage to certain users. A separate system, either another server [39] or blockchain [40, 41], has to be used to recover such integrity guarantees.

The cited references:

  1. D. Mazieres and D. Shasha, “Building secure file systems ` out of Byzantine storage,” in PODC ’02.
  2. J. Li, M. Krohn, D. Mazieres, and D. Shasha, “Secure ` untrusted data repository (SUNDR),” in OSDI ’04.
  3. A. J. Feldman, W. P. Zeller, M. J. Freedman, and E. W. Felten, “SPORC: Group collaboration using untrusted cloud resources,” in OSDI ’10.
  4. N. Karapanos, A. Filios, R. A. Popa, and S. Capkun, “Verena: End-to-end integrity protection for web applications,” in S&P ’16.
  5. A. Tomescu and S. Devadas, “Catena: Efficient nonequivocation via Bitcoin,” in S&P ’17.
  6. Y. Hu, S. Kumar, and R. A. Popa, “Ghostor: Toward a secure data-sharing system from decentralized trust,” in NSDI ’20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.