Public cloud storage is a fundamental cloud computing service. Currently, most owners of large data outsource their data to cloud storage services-even high-profile owners such as governments. However, public cloud storage services are not optimal for ensuring the possession and integrity of the outsourced data, a situation that has given rise to many proposed provable data possession check schemes (PDP). A PDP scheme allows data owners to efficiently, periodically, and securely verify that a cloud storage provider possesses the outsourced data. Most of the currently available provable data possession check schemes make selective (i.e., probabilistic) checks using random data blocks to verify data integrity rather than checking the entire dataset. Therefore, these schemes are considered inadequate by critical infrastructure sectors that involve highly sensitive data (critical data). In this paper, a new and efficient deterministic data integrity check scheme called cryptographic-accumulator provable data possession (CAPDP) is proposed. The CAPDP surpasses the common limitations exhibited by other currently proposed schemes. The underlying scheme of the CAPDP is based on a modified RSA-based cryptographic accumulator that has the following advantages: 1) it allows the data owner to perform an unlimited number of data integrity checks; 2) it supports data dynamics; 3) it is efficient in terms of communication, computation and storage costs for both the data owner and the cloud storage provider; 4) the verification operation in the proposed scheme is independent of the number of blocks being verified; 5) it minimizes the burden and cost of the verification process on the data owner's side, enabling verification to be performed even on low-power devices; and 6) it prevents tag forgery, data deletion, replacement, and data leakage attacks and detects replay attacks. Moreover, the prototype implementation and experimental results show that the scheme is applicable in real-life applications.