Critical infrastructure systems like finance, energy, transport, and healthcare provide very vital and crucial services to the government sectors, private organizations and general public. These services need reliable and scalable infrastructure to support their dynamically growing needs. Cloud computing provides such a reliable and scalable, as well as cost-effective infrastructure to support the ever increasing needs of those critical infrastructure providers. The critical sectors like healthcare, finance, energy and many other government and private organizations as well as individuals are moving their data to cloud storages. While enjoying the benefits of cloud, the users also face the challenges of data security and privacy. The distributed nature of cloud challenges the traditional form of securing the information in almost all domains of the society, and hence a new set of rules for securing information need to be defined. New avenues are to be explored to defend against the threats posed towards sensitive data hosted in cloud. In this paper an efficient, privacy-preserving Remote Data Possession Checking protocol is proposed for verifying the integrity of data stored in cloud. This Remote Data Possession Checking (RDPC) protocol uses random sampling of data blocks in order to eliminate the need for accessing the entire data file each time it is verified. Also an exhaustive security and performance analysis of the proposed protocol is performed under various parameter values. The experimental results show that the proposed protocol is efficient in terms of performance when compared to many existing schemes, and require only minimum number of data blocks to detect the corrupted blocks with high probability.