1. A method for performing prefix search of encrypted cloud stored data comprising: receiving, at a network intermediary, a search request with a search term directed to encrypted files stored in a cloud storage service, the cloud stored encrypted files being encrypted using an order-preserving encryption algorithm; generating a minimum possible plaintext string using the search term as prefix and padding the search term to a first character length using one or more trailing characters indicative of a minimum possible value related to the search term; generating a maximum possible plaintext string using the search term as prefix and padding the search term to the first character length using one or more trailing characters indicative of a maximum possible value 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 cloud stored 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 from 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; sending the cloud service search request with the encrypted prefix search term to the cloud storage service; and receiving a search result from the cloud storage service.