What makes it impossible? Naively I would think that if you have a secure 1:1 communication protocol, then you can send N*(1:1) secure messages to a group of N people. To solve the "fake group message" problem where an adversarial member of the group sends different messages to different members of the group, or delays the message to some members, the protocol could simply allow for a 2nd level "vouch" message to be sent, such that Alice sends the message to Bob, Alice sends the message to Charlie, Charlie messages Bob a receipt with the receive time and a hash of the chat log, and Bob messages Charlie a receipt with the receive time and a hash of the chat log. If the hashes don't match, or the receive time is unacceptably different, then you highlight the message as suspect.
Sure, it takes N^2+N messages, but that's not exactly a massive overhead for text. Multimedia takes N times as much bandwidth as the 1-server, server-many model for the sender, but otherwise isn't terrible.
Ah, but what if I send different vouch messages to different users?
There is actually a way to do it, if you assume PKI (which signal provides) and that all messages will be delivered in some bounded time. It’s called the dolev-strong protocol and it guarantees that all honest members of the group will agree with each other. Unfortunately, it requires one round per group member and delivering all messages within a bounded time isn’t easy.
Since you'd be receiving vouches from all group members, you'd get some data about who trusts who's message. To the user, you'd probably highlight the message with the "something's fucky" notifier (red background? a caution symbol?) and then have the further "of X vouches you've recieved, these Y disputed the message's (content/existence)" type deal.
Which lets you know that Alice and Bob are in contention, which is probably good enough for most situations. "One of these three (or more if you have multiple groups of bad faith actors) sets of users are operating in bad faith" should be plenty of information for a user to make an informed decision. Even if that decision is "wow, how did I end up in a group containing multiple groups of bad actors, I should be elsewhere".
> Naively I would think that if you have a secure 1:1 communication protocol, then you can send N*(1:1) secure messages to a group of N people
IIUC this is what iMessage does (at least when Messages in iCloud or whatever it's called is disabled), except s/people/devices: say you have three devices and someone sends you one message, the message is encrypted once per recipient device, and three encrypted messages get sent. Whether it's 1 person with 3 devices, 3 people each with 1 device, or 2 persons with one having 2 devices and the other a single one becomes largely immaterial.
Why not use a merkle tree/blockchain? Usually a meme, but seems like a good solution here: every message is a blob containing the mssage and the hash of the previous received blob. As long as order and messages are the same, the message is valid.
A bad actor could screw with you in this naive implementation though
What you described is a tendermint-consensus-protocol-like round. It requires a direct connection (or some emulation of such channel) between participants.
Sure, it takes N^2+N messages, but that's not exactly a massive overhead for text. Multimedia takes N times as much bandwidth as the 1-server, server-many model for the sender, but otherwise isn't terrible.