Abstract: Data possession checking (DPC) is used in networked archival storage to check in real time if the remote server holds a file intact before the actual access to the file occurs. The authors present a practical DPC scheme. In a challenge-response protocol, the checker ascertains the possession of a file by asking the server to compute a hash value of some randomly appointed data blocks of the file and return it together with a corresponding verification block. With this random sampling verification method, the computational and communication overheads of possession checking are reduced while a sufficiently high confidence level is obtained. A challenge renewal mechanism based on verification block circular queue is also proposed to allow the dynamic increase of the number of effective challenges which can be issued by the checker. Analysis shows that the storage overhead on the checker side and the communications overhead between the checker and the server are constant. Experimental results show that the computational overhead of a check with a confidence level of 99.4% is 1.8ms, which is negligible compared with the cost of disk I/O; The computational overhead of file preprocessing is reduced by three orders of magnitude by avoiding using public-key cryptosystem.