Clustering protocols are often used in sensor networks. In many deployment scenarios, security is a key concern. In this paper we provide a secure solution to a commonly used clustering protocol, the LEACH protocol. We show that our protocol, the GS-LEACH protocol is more energy efficient than any of the secure flavors of LEACH. The GS-LEACH (grid-based secure LEACH) protocol uses pre deployment key distribution using prior knowledge of the deployment area. We also provide a detailed security analysis of our protocol and show that it is more secure than the secure versions of LEACH. Finally with the results of our simulation experiments we show that our protocol is very energy efficient and provides a longer network lifetime compared to the other flavors of LEACH.