Do companies like CipherCloud really have the option to use homomorphic encryption? I was reading How is CipherCloud doing homomorphic encryption? and was wondering:

Is there a technically feasible way for companies like CipherCloud to use homomorphic encryption (HE) while preserving full functionality in a third party SaaS app (e.g. Salesforce)? Furthermore, can it be done without requiring that the third party SaaS app be modified?

I believe is not completely possible because of the use of “Top n” functions (e.g. customer charts) and the common use of the SQL distinct keyword.

For example, suppose the application uses the top 10 customers (global sales) this month. For the DB query it would imply something like select top 10 customerField from sales order by orderTotalField desc. Issue here is that 2+ different customerFields can be the same customer if we use HE, and that would result in incorrect values, maybe not even 10 different customers.

Let me elaborate a little more: HE Database has a table with 3 fields customerName, dailySales and date. John is the customer with most sales but has, say, 8 HE equivalent values. The application ask for the top ten sales, by customer, by year. The query is then, Select cutomerName, sum(dailySales), Year(date) from datatable group by customerName, Year(date) order by Sum(dailySales) descending. As you see, the database needs to group in this case depending on sales for each customerName, and will fail for this example. Hope I'm clear here to establish the problem with HE in first instance.

What do you think, do they have a choice? If so, please elaborate :)
Is there a technically feasible way for companies like CipherCloud to use homomorphic encryption (HE) while preserving full functionality in a third party SaaS app (e.g. Salesforce)? 


Fully homomorphic encryption can theoretically1 compute any function. Therefore, if a computer can perform a task on plaintexts, then fully homomorphic encryption could theoretically be used to perform that exact same task on ciphertexts.

It seems like your doubt stems from an equality check. From your example, you seem to believe that because there are say two rows in the database that belong to the same user, that FHE would not be able to combine the sales amounts of those two rows. In other words, how would FHE know that the two encrypted customerName values are the same?

The answer is, the FHE computation wouldn't need to know that the two customerName values are the same. Instead, it would compute an encrypted bit. If they are the same, the encrypted bit encrypts 1, else it encrypts 0. This is a very feasible computation with FHE. Once it knows that bit, it would sum in the bit times the dailySales value. Thus, if the bit is 1, the dailySales value is added in. If the bit is 0, the dailySales value is not added in (since 0 times anything is 0).

Thus, given your table, say you want to know the top 1 customer. Presumably you have a table of encrypted customerName values. For each encrypted customerName value, you'd step through every entry in the sales table, computing the bit for that row, then adding in the bit times the dailySales value for that row. You'd save the result along with the customerName value. Once you've done that for every possible customerName, you'd use FHE to find the one with the largest encrypted sum, and return that to the user. The user could then decrypt the values and learn who was the top customer.

This is a good example of how, yes, FHE allows you to compute any function, but the method of doing it sometimes requires some tricks.


  Furthermore, can it be done without requiring that the third party SaaS app be modified?


In general I would expect that the answer is no, w/o modification it could not be done. There are maybe a few corner/special cases where it could possibly.

For example, if dailySales value in the database is an int32, then an encrypted version will definitely not fit in the int32 slot. In which case the DB would have to be modified. If, however, the DB had originally been setup to store everything as, say, an unlimited size string, then FHE encrypted values could be encoded as a string (pick your favorite method) then stored that way.

The client software would either have to do the encryption itself, or a proxy could be used. So in that sense, the client would likely have to be modified (at least to point to the proxy). Let's assume you use a proxy. The client sends the entry to the proxy, the proxy encrypts it and submits it to the SaaS app. 

The proxy would also have to be smart enough to translate queries. For example a query for the top customer would not be able to be run directly on the SaaS app. Instead the proxy would have to translate it into a query for the entire table, then run the process I described previously.

The proxy would only know the customer's public key, so the proxy couldn't return the plaintext answer. The customer would receive an encrypted answer to the query which it would have to decrypt.

I imagine this would be the process that would have to be done.

Note, the client doesn't really have to send FHE encrypted values to the proxy. The client could encrypt the values with AES, then send the AES key encrypted with the FHE public key. The proxy uses that encrypted key to homomorphically decrypt the values. The output is the user's values encrypted with FHE. Using this technique, the client would have to do very little FHE encrypting.

1. I say theoretically as FHE is still not practical today.