[temporalparts]

It's not possible to have a "web scale" that end-to-end encrypts metadata, because part of the metadata is understanding the recipient.

If the network or server has no idea where to deliver an encrypted message, then the only way to guarantee delivery is to send all the messages to all the users to unpack to see which ones are relevant to them, which fails "web scale"

[hamandcheese]

What if all inboxes were public, but only decryptable by the recipient? Recipient can then poll for new messages.

[ThatPlayer]

Only the recipient would be able receive/send messages from that inbox. So you can easily match inbox to the recipient.

[eru]

You wouldn't send via your inbox. And anyone would be able to download any inbox, the data would just be useless without the key.

There might be problems with the proposed model, but they aren't the problems you suggested.

(As an individual, you wouldn't want to download just your own inbox. But to obfuscate, you can download a random subset of inboxes that often-enough includes your own.)

[ThatPlayer]

And that's not something I want to have to do: download random inboxes on a limited phone data plan. As a polled service, how many times do you have a poll a minute? If I'm instant messaging, I could be pulling multiple times a seconds. How many more inboxes would I have to poll at the same time to obfuscate my actual inbox?

And if you want to be anonymous you can't filter by the last message you've received, so every time you pull your inbox, you're getting the last X time in messages. So if I have multiple active group chats, that would really start to add up.

Videos and images like every other messaging service would have to be anonymized the same way. Even 10x noise polling for a 10MB video would be too much data on phones and probably not enough to anonymous. How about obfuscating the sender? Would a sender be uploading 10x trash, not just text but also video, messages in every inbox?

[eru]

If you have such a limited data plan, perhaps you shouldn't communicate with videos?

[ThatPlayer]

Even if I don't, any inbox chosen to randomly download could have videos.

[lxgr]

This is very hard to get right.

Some Bitcoin SPV clients have tried solving an almost equivalent problem, but the obvious approach does not work for various subtle reasons: https://eprint.iacr.org/2014/763.pdf

[eru]

Oh, it's definitely not easy to get this right properly. I just wanted to point out that things aren't as clear-cut impossible as the comment suggested.

[bryan_w]

Y'all are struggling so hard to describe newsgroups :)

Check out alt.cryptography (I think) if you can.

[temporalparts]

How would the servers know where to route the poll requests without metadata? They wouldn't.