I would do what PGP does, which is symmetrically encrypt the message, and then encrypt the symmetric key multiple times, once to each recipient, via ECDH, putting that alongside the message. 

 This is a great solution, thank you.