A client device or other processing device comprises a file processing module, with the file processing module being operative to provide a file to a file system for encoding, to receive from the file system a corresponding encoded file, and to verify that the file system stores at least a designated portion of an encapsulation of the encoded file. In an illustrative embodiment, the file processing module receives, in addition to or in place of the encoded file, a proof of correct encoding. 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.