Message authentication is one of the most effective ways to thwart unauthorized and corrupted messages from being forwarded in Wireless Sensor Networks (WSNs). For this reason, many message authentication schemes have been developed, based on either symmetric key cryptosystems or public-key cryptosystems. Most of them, however, have the limitations of high computational and communication overhead in addition to lack of scalability and resilience to node compromise attacks. To address these issues, a polynomial-based scheme was recently introduced. However, this scheme and its extensions all have the weakness of a built-in threshold determined by the degree of the polynomial, when the number of messages transmitted is larger than this threshold, the adversary can fully recover the polynomial.