Abstract
Every year millions of Muslims from all around the world gather to perform their pilgrimage in Makkah, Saudi Arabia. Due to the massive number of pilgrims of different languages, cultures and countries, it is highly challenging for the authorities to manage and provide proper services to these pilgrims. In this paper, we propose a pilgrim tracking system with the help of Radio Frequency identification (RFID) that can be deployed to improve the present situation. We also investigate possible security and privacy issues and propose a new secure protocol which meets the requirements for this application. Our proposed authentication protocol provides privacy, security and it is efficient particularly for this application.