A proof of retrievability (POR) mechanism is applicable to a file for providing assurances of file possession to a requesting client by transmitting only a portion of the entire file. The client compares or examines validation values returned from predetermined validation segments of the file with previously computed validation attributes for assessing the existence of the file. Since the archive server does not have access to the validation function prior to the request, or challenge, from the client, the archive server cannot anticipate the validation values expected from the validation function. Further, since the validation segments from which the validation attributes, and hence the validation values were derived, are also unknown to the server, the server cannot anticipate which portions of the file will be employed for validation.