A lower bound on the insecurity of CipherCloud? CipherCloud claims to support , among other things, searchable encryption. A bunch of speculation seems to suggest they did this via some breathtakingly  incompetent means( unfortunately such speculation &quot;appears&quot; to be copyrighted)
Regardless of their actual methodology, if we assume their encrypted data is searchable by the cloud providers they work with without changes to the providers(e.g. salesforce), then doesn't this result for order preserving encryption constitute a lower bound on how insecure their system  could be(and a pretty poor one at that)?
The result deals with the security of the ideal functionality of an order preserving encryption (OPE) scheme.  This is the ideal model of a  scheme where you can sort  $c=enc_k(m)$ by numerical comparison of $c$. Any scheme where you search encrypted cipher texts with existing queries in a database must meet this requirement. This appears to suggest that the absolute best case for CipherCloud is that their encryption leaks roughly the $1/2m$ high-order bits of a given message* . This seems drastically unsafe for low entropy messages such as social security numbers, credit card numbers, earnings reports, and most other data you might want to search on in say a sales application.
*Per the paper, where M is the size of the message space(i.e. $M=2^l$ for $l$ length messages) &quot;Intuitively, Theorem 4.2 implies that for $r\approx b \sqrt{M}$, where b is a large enough constant (say $b \ge 8$),there exists an adversary $A$ whose r-window one-wayness is very close to 1.&quot;
That paper refers to the numerical ordering, while what would be relevant for searchable encryption without changes to the providers is the substring ordering. $\:$ (Thus, their bound does not apply.)

What do you mean by "existing queries in a database"?

If your assumption holds, then
{
Encryption must be deterministic (given the key), since different encryptions of the

same message (with the same key) must be substrings of each other (and thus equal).

There must be a noticable $\big($though not necessarily $\theta\hspace{.01 in}(1)\big)$ chance of breaking authenticity via a

single ciphertext only (by submitting a random substring of it). $\:$ The scheme must be malleable by

almost the same amount, again with just a single ciphertext only and for basically the same reason.
}

"without changes to the providers" is a rather stiff assumption. $\:$ For example, one could easily shut

down active attacks by splitting the ciphertexts into two columns and having the cloud just search the

left column, while the right column has message authentication codes which are only relevant to the user.