Methods and systems for secure cloud storage are provided. According to one embodiment, a trusted gateway device establishes and maintains multiple cryptographic keys. A request is received by the gateway from a user of an enterprise network to store a file. The file is partitioned into chunks. A directory is created within a cloud storage service having a name attribute based on an encrypted version of a name of the file. For each chunk: (i) a cryptographic key is selected; (ii) existence of data is identified within the chunk associated with one or more predefined search indices; (iii) searchable encrypted metadata is generated based on the identified data and the selected cryptographic key; (iv) an encrypted version of the chunk is generated; and (v) a file is created within the directory in which a name attribute includes the searchable encrypted metadata and the file content includes the encrypted chunk.