A client device or other processing device comprises a file processing module, with the file processing module being operative to request proof from a file system that a file having a first format is stored by the file system in a second format different than the first format, to receive the proof from the file system, and to verify that the file is stored in the second format using the proof provided by the file system responsive to the request. The proof is based at least in part on application of a function to the file in the second format, and the function imposes a minimum resource requirement on generation of the proof. The file system may comprise one or more servers associated with a cloud storage provider. Advantageously, one or more illustrative embodiments allow a client device to verify that its files are stored by a cloud storage provider in encrypted form or with other appropriate protections.