Mitigating the effects of server-compromise in an end-to-end encrypted system
Trusted server

That's right.  There are several standard approaches to handling group key management with a trusted server:


Group key: Use a single group key known to everyone in the group.  Anytime someone is removed from the group, change the group key and update everyone who is supposed to still have access.  Use a symmetric key for the group key; this makes encryption and decryption efficient.
Individual keying, with server proxying: Give each person their own individual symmetric key, which is shared only with the server.  Each person has a secure connection with the server, secured with this key, and the server forwards messages (decrypting and re-encrypting).  This is a hub-and-spoke model, with the server responsible for determining who is allowed to see the messages.  When someone is removed from the group, the server will stop forward messages to them.
Signed list of group members: Have the server sign a list of group members, along with a timestamp.  For instance, each group member could be indicated by its public key.  It's important to include a way for the server to prove freshness of the signed list (e.g., include a timestamp in the signed data).  This solution is vaguely similar to what you sketched in your question, except you seem to have overlooked the need for a timestamp and a signature.  Clients will have to periodically poll the server to check for updates to the list of group members.

If you use public-key encryption to encrypt all messages between group membesr, this will be unnecessarily expensive/slow, because it would require all clients to use public-key encryption to encrypt each message, and require $O(n)$ public-key encryptions per message sent.  However, each client could exchange a symmetric key with every other authorized member of the group (using the public key provided by the server), cache this symmetric key, and use it for all subsequent messages, which will be more efficient.


Yes, this is a pain, but it's a necessary pain.

No, your solution isn't secure, for exactly the reason you mentioned: because the list of group members is unsigned, it can be modified by a man-in-the-middle.

All of these solutions require trust in the server.  That is unavoidable: it's part of your problem specification that the server determines who is authorized to be in the group.  Thus, a malicious server can just add himself to the group and read/modify all the traffic.  Once you start from a world where the server is empowered to decide group membership, you must trust the server.  There's no way to avoid trusting the server, if the server is empowered to decide who is part of the group -- in that model, there's no way to build a solution that doesn't involve trust in the server.

Untrusted server

The simplest approach is to have a single group leader who is in charge of group membership, and who has complete control over the list of people in th group.  The most natural model is that the group leader be the first person to create the group -- so the group owner is one of the members of the group, and controls who the other members are.

You can easily support that model, without trust in the server.  Simply take any of the three solutions above, but replace "server" with "the group owner's machine".

There are other approaches one could imagine -- e.g., once someone is in the group they can never be removed (revocation is impossible); or, all members must approve each group member and any member can kick anyone out of the group at any time -- but the usability consequences of those seem horrible, so I can't imagine they are going to be attractive.