Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
up vote 3 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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