I have been thinking about implementing this for quite some time, but I would like some feedback from people more knowledgeable than me on the matter.

There’s been some great progress in the field of Private Information Retrieval (PIR) protocols. Recently, in a 2022 article, Lin et al. describe an “updateable DEPIR”, with both read and write times that can be made sublinear to database size.

I wonder if one couldn’t use a combination of this technique and regular public-key cryptography to provide fully anonymous message routing. One could write outgoing messages to a fixed address and issue private reads to their contacts’ addresses, with the messages themselves being encrypted with the receiver’s public key.

The benefit of this would be a messaging protocol wherein the server wouldn’t just be oblivious to the content of all messages, but also the social graph itself, plus all message-sending operations becoming deniable as a side effect.