# efficient authentication with broadcast encryption?

(I am not a crypto expert, so I apologize if the terminology I use is incorrect.)

Suppose I have the following simple broadcast encryption scheme for securely sending content to $n$ authorized recipients using only symmetric-key algorithms:

1. each authorized recipient is given a recipient key (known only to the sender and recipient)
2. the sender generates a random key to encrypt a message (content key)
3. for each receipient, the sender broadcasts the content key encrypted with the recipient key
4. each recipient uses its recipient key to decrypt the content key
5. the sender broadcasts the message encrypted with the content key
6. each recipient uses the content key to decrypt the message

With the above scheme, there is no authentication. A man-in-the-middle attack would allow one recipient to undetectably alter the original message on its way to another recipient. Some additional steps could fix this:

1. the sender calculates a cryptographic hash of the content
2. for each recipient, the sender broadcasts the hash encrypted with the recipient key
3. each recipient decrypts the hash and uses it to authenticate the message

My question: Is there a scheme that allows recipients to authenticate the message without the $\operatorname{O}\left(n\right)$ overhead of sending the encrypted hash and without using asymmetric cryptography? If not, can the overhead be reduced?

-