Usage of FHE in obfuscation?

Question

FHE (Fully Homomorphic Encryption) is a cryptographic encryption schema in which it is possible to perform arithmetic operations on the ciphered text without deciphering it.

Though there is no really efficient crypto-system with this property at this time, several proofs of concepts show that this kind of cryptography does actually exist. And, that, maybe one day, we might find an efficient crypto-system with the FHE properties.

For now, the usage of FHE is mainly directed towards "Cloud Computing" where one want to delegate a costly computation to a remote computer without spreading his data away. So, the principle is just to send out encrypted data and the Cloud will apply a given computation on the data and send back the encrypted answer without having knowledge of what is inside.

The link with code obfuscation is quite obvious as if we can perfectly obfuscate data, then we can also perfectly obfuscate the algorithm by coding it into a universal Turing machine. But, the Devil is always in the details. A recent paper [1] presents a way to use the FHE for obfuscation, but in a too stronger way (in my humble opinion).

My question is the following: Suppose we have an efficient FHE schema, suppose also that our goal is to slow down the analysis of a program (and not totally prevent it). Then, what would be the most efficient usage of the FHE in obfuscation ?

Answer 1

I was about to say "this sounds a lot like something that the INSIGHT team wants to hire an intern to investigate this summer" but then I looked at your username and location :)

I think this question is very difficult to answer unambiguously because you are seeking a mechanism to efficiently slow down manual analysis. I'll put what I think is an answer forward anyway.

It seems that you have two high-level choices, "encrypt program code" or "encrypt program data". Encrypting program data seems less powerful because a manual analysis can still glean a lot of clues about the program by observing its structure, so it seems that what you would want to do to slow down analysis is deny the analyst the ability to see program structure.

What if you transformed a program into a bytecode language and an interpreter, similar to what VMProtect and others do. Then, you encrypt the buffer of bytecode and use FHE to access the buffer when you are executing code.

Answer 2

Fully homomorphic encryption is not as good as it might seem for obfuscating code. While it is true that you could compute on an encrypted Turing machine, the benefits to obfuscating a closed system are not that great, simply for the reason that any input or output to the system must be encrypted or decrypted. Thus any reverse engineering of the program would simply start by extracting the encryption keys from this encryption or decryption code.

The benefit only becomes substantial when the IO is encrypted and decrypted by a third party, in which case it is impossible to decrypt the code without gaining access to that third party. So in circumstances where you want to obfuscate a pure computation, you could use homomorphic encryption to run a fully opaque botnet. For example, the controller could send hashes to crack or bitcoin data to mine, and it would be impossible to know from looking at the client what codes is being run without outside information.

Of course, the key part here is that the encryption/decryption keys are stored remotely, and thus cannot be extracted from the obfuscated program.

Answer 3

What is functional encryption for all circuits and indistinguishability obfuscation for all circuits ?

1. A proposed indistinguishability obfuscation for NC1 circuits where the security is based on the so called Multilinear Jigsaw Puzzles (a simplified variant of multilinear maps).
2. Pair the contribution in 1 with Fully Homomorphic Encryption and you get indistinguishability obfuscation for all circuits.
3. Combine 2 with public key encryption and non-interactive zero-knowledge proofs and you functional encryption for all circuits. I believe that prior to this, functional encryption for all circuits was not possible.