Multi-user broadcast authentication is an important security service in wireless sensor networks (WSNs), as it allows a large number of mobile users of the WSNs to join in and broadcast messages to WSNs dynamically and authentically. To reduce communication cost due to the transmission of public-key certificates, broadcast authentication schemes based on identity (ID)-based cryptography have been proposed, but the schemes suffer from expensive pairing computations. In this paper, to minimize computation and communication costs, we propose a new provably secure pairing-free ID-based signature schemes with message recovery, MR-IBS, and PMR-IBS. We then construct an ID-based multi-user broadcast authentication scheme, BASIS, based on MR-IBS and PMR-IBS for broadcast authentication between users and a sink. We evaluate the practical feasibility of BASIS on WSN hardware platforms, MICAz and Tmote Sky are used in real-life deployments in terms of computation/communication cost and energy consumption. Consequently, BASIS reduces the total energy consumption on Tmote Sky by up to 72% and 17% compared with Bloom filter-based authentication scheme based on a variant of ECDSA with message recovery and IMBAS based on a ID-based signature scheme with message appendix, respectively.