(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:
- each authorized recipient is given a recipient key (known only to the sender and recipient)
- the sender generates a random key to encrypt a message (content key)
- for each receipient, the sender broadcasts the content key encrypted with the recipient key
- each recipient uses its recipient key to decrypt the content key
- the sender broadcasts the message encrypted with the content key
- 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:
- the sender calculates a cryptographic hash of the content
- for each recipient, the sender broadcasts the hash encrypted with the recipient key
- 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?