1. A method for performing prefix search of encrypted cloud stored data comprising: in response to receiving a search request at a network intermediary with a search term directed to order-preserving encrypted files stored in a cloud storage service, generating a minimum possible plaintext string and a maximum possible plaintext string using the search term as prefix and padding the search term using at least one trailing character indicative of a minimum possible value or a maximum possible value, respectively, related to the search term; encrypting the minimum possible plaintext string and the maximum possible plaintext string using the order-preserving encryption algorithm used to encrypt the order-preserving encrypted files; generating a minimum ciphertext from the minimum possible plaintext string and a maximum ciphertext from the maximum possible plaintext string; determining a set of common leading digits shared by the minimum ciphertext and the maximum ciphertext; generating a cloud service search request including the set of common leading digits as an encrypted prefix search term; and in response to transmitting the cloud service search request with the encrypted prefix search term to the cloud storage service, receiving a search result from the cloud storage service.