1. A method for performing wildcard search of encrypted cloud stored data comprising: receiving, at a network intermediary, a document destined for a cloud service provider; encrypting, at a network intermediary, the document using a document encryption algorithm; generating a set of permuted keyword strings for each of some or all of the keywords in the document, the set of permuted keyword strings for each keyword being generated by adding a first character delimiter before the first character of the keyword and applying cyclic rotation of the characters of the keyword, including the first character limiter; encrypting the permuted keyword strings using an order preserving encryption algorithm; storing the encrypted permuted keyword strings in a database; and transmitting the encrypted document to the cloud service provider.