Most Efficient way of Encrypted Chat

Public key cryptography can, in this case, be used to facilitate setting up a secure channel in which to transmit a symmetric key. Once the secure channel has been set up, it is not necessary to continue to encrypt and decrypt using the public/private keys. Instead, generate a symmetric key and use that to encrypt the traffic. You only have to distribute the symmetric key once, and the traffic need only be encrypted with this key rather than with each public key. The main challenge is when or if the symmetric key needs to be regenerated, revoked, etc.

The most efficient way is to have client's exchange their RSA public keys and then generate random "session keys" to use for conversations with each other. This avoids multiple encryption and doesn't require the server to be able to decrypt the data.

So if Jack is going to talk to Jill and Seth, Jack generates a random encryption key to use to talk to Jill and Seth. Jack encrypts this key with Jill's public key and Seth's public key and sends the encrypted keys to Jill and Set. The server cannot decrypt them. Now Jill and Set know the key Jack will use. Jack can now encrypt the messages once with this key and have the server relay them to Jill and Seth. Jill and Seth can decrypt the data with the session key. The server can never decrypt the data.

This means clients will have to keep session key tables and generate new keys for any distinct combination of clients they may wish to talk to.

Be warned that with all of these schemes, unless you use certificates they are vulnerable to an attack where the server simply substitutes its own keys for the client's keys and decrypts and re-encrypts all traffic, unbeknownst to the clients.

Run a jabber server and tell them to use pidgin with OTR