1. A method implemented in a non-transitory machine-readable storage medium and processed by one or more processors of a machine configured to perform the method, comprising: establishing, on the machine, a tenant storage machine (TSM) in a cloud storage environment for an authenticated tenant, wherein establishing further includes creating the TSM as a Virtual Machine (VM) within the cloud storage environment for the authenticated tenant to access data of the authenticated tenant and the VM is just for access by the authenticated tenant; managing, from the machine, a tenant key store within the TSM for the authenticated tenant, the tenant key store including encryption keys for encrypting the data of the authenticated tenant within the cloud storage environment; and ensuring, from the machine, only TSM storage processes are given access to the tenant key store, wherein the TSM processes run within the TSM.