As the popularity of cloud storage increases, data security issues have attracted significant attention from both academia and business sectors. Among these issues, data integrity auditing is of particular importance. To date, numerous data integrity auditing protocols for cloud storage have been available in the literature. Most of them are based on public key cryptography. In this paper, we examine the key technique involved in public key data integrity auditing in cloud storage. The concept and the security model of quasi-linearly homomorphic signature(QLHS) scheme are introduced. Its relationship with secure public key data integrity auditing in cloud storage is demonstrated. An efficient instantiation of the quasi-linearly homomorphic signature scheme is presented. The performance of a provable data possession(PDP) protocol using our QLHS scheme is analyzed. The comparison demonstrates that our approach is more efficient in terms of computation, communication, and storage space for cloud users.