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.