[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.

[eru]

Good point. Though you can probably use 'blocks' (think like hard-disk blocks) instead of complete mail boxes. You download random blocks that also contain blocks from your mailbox.

[ThatPlayer]

You can't just download random blocks until you get your data though, you might never download some blocks. So you need some kind of index of blocks. And your client can't generate that because the server stores all the data. So it's a server-sided index.

If you only download the index for specific users, that's no different than an inbox: if you pull the index for an inbox and don't pull all the associated blocks (including videos), that's obviously not your box.

The other alternative is downloading the entire index for every single block, which sounds even worse than just downloading random complete inboxes with videos. Especially if the blocks are going to be filled with trash inboxes filled with trash data to obfuscate the sender. Even my own blocks would get trash data including videos that I have to download to pretend it's real.

[eru]

Fountain codes and other tricks might help.

Ie any block could be useful for multiple inboxes and messages. See also how freenet used to do it. https://en.wikipedia.org/wiki/Freenet

[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.