How to securely store data with an untrustworthy party?

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.

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:

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