Comment by reifyx

Assuming you don't want to keep any "chain state" in between messages (which seems reasonable), you can always consume a fresh one-time key of the recipient for every message. The first downside is how you know that the one-time key hasn't been reused, for this you can either trust the service provider or use blockchain or blockchain-like technologies. Second downside is that the user has to be online to generate a ton of one-time keys. I believe puncturable encryption helps with this so the recipient can "puncture" their key at the used-up key identifiers, and thus doesn't have to be online all the time. No idea how practical this is.