A computationally efficient message verification strategy that achieves non-repudiation and resilience to computational denial of service attacks in conjunction with a broadcast authentication protocol that authenticates messages using a combination of a digital signature and a TESLA MAC. When messages are received at a receiver, the verification strategy separates the messages into messages with the same sender identification. The strategy then determines whether the TESLA MAC authenticator is valid for each message and discards those messages that do not have a valid TESLA MAC. The strategy collects the messages that have a valid TESLA MAC for each sender identification and performs a batch verification process on the group of messages to determine if the messages in the group have a valid digital signature. This strategy verifies each message in the group of messages if the batch verification process shows that the group of messages has a valid digital signature.