(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?


1 Answer 1


The answer to your question is yes this is possible, but if we don't use assymetric cryptography, we need an alternate source of assymetry. One option is using time-delayed schemes. In such schemes, the key for the MAC is not initially disclosed, but only after some time interval.

See here for TESLA that accomplishes this. TESLA has a drawback in that it requires an initial digital signature to send the initial parameters. A second variation of TESLA, uTESLA achieves this without digital signatures.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.