# Spaghetti code crypto – STOC 2014 Recaps (Part 6)

We return to our STOC recap programming with Justin Holmgren, who will tell us about an exciting new result in program obfuscation. (However, he doesn’t tell us how to say “indistinguishability obfuscation” 10 times fast).

Justin Holmgren on How to Use Indistinguishability Obfuscation: Deniable Encryption, and More, by Amit Sahai and Brent Waters

One very recent topic of study in cryptography is program obfuscation – that is, how to make a program maximally unintelligible, while still preserving the functionality. We will represent programs as circuits, which for most purposes is equivalent to any other representation. At some level, obfuscation of a program seems like it should be an easy task – any programmer knows that it’s easy to end up with unreadable spaghetti code, but theoretical treatment of the issue was lacking, and finding a construction with provable security properties has proven quite difficult.

In 2001, Barak et al. [1] precisely formulated black-box obfuscation, which says that if you can compute something given the obfuscated program, you could also compute it given black-box access to the program. This is a natural and very strong notion of obfuscation. If we could obfuscate programs according to this definition, we could easily solve many difficult problems in cryptography. For example, a public-key fully homomorphic encryption scheme could be constructed from an ordinary symmetric-key encryption scheme by obfuscating a program which decrypts two input ciphertexts, and outputs the encryption of their NAND. Unfortunately, [1] also showed that black-box obfuscation is impossible to achieve.

One weaker definition of obfuscation that [1] did not rule out is called indistinguishability obfuscation (iO). It requires that if two circuits $C_1$ and $C_2$ are functionally equivalent (for all $x$, $C_1(x) = C_2(x)$), then their obfuscations are indistinguishable. In 2013, Garg et al. [2] gave the first candidate construction for iO. This construction is not proven secure under standard assumptions (e.g. the hardness of factoring), but no attacks on the construction are currently known, and it has been proven that certain types of generic attacks cannot possibly work.

It isn’t immediately clear whether iO is useful. After all, what information is the obfuscation really hiding if it only guarantees indistinguishability from functionally equivalent programs? “How to use Indistinguishability Obfuscation: Deniable Encryption and More”, by Amit Sahai and Brent Waters [3], shows several applications of iO to building cryptographic primitives, and proposes iO as a “hub of cryptography”, meaning that constructions which use iO as a building block would be able to benefit from improvements in the efficiency or underlying computational assumptions of iO constructions.

As a first example of how to use iO, they show how to construct an IND-CPA public key cryptosystem based on one-way functions and iO. This uses a few other basic and well-studied cryptographic primitives (it is known that all of them exist if one-way functions exist). First, a pseudorandom generator is a deterministic function which takes as input a random string $s$, and computes a longer string $r$ which is indistinguishable from truly random. The length of $r$ can be polynomially larger than the length of $s$, but we will let $r$ be twice the length of $s$. A pseudorandom function family is parameterized by a secret key $k$ and an input $x$, and produces outputs of some fixed length. Oracle access to $f_k(\cdot)$ for some random unknown $k$ is computationally indistinguishable from oracle access to a truly random function. The main special property that [2] require is a puncturable pseudorandom function family. That is, for a secret key $k$ and an input $x$, a “punctured” key $k\{x\}$ can be computed. $k\{x\}$ allows one to compute $f_k(y)$ for all $y \neq x$, but essentially reveals no information about $f_k(x)$.

The power of iO comes from combining its indistinguishability guarantees with those of other cryptographic primitives, in what is known as the hybrid method. We will start with the security game played with a real scheme, and give a sequence of other games, each indistinguishable from the previous one to the adversary, such that the adversary obviously has no advantage in the last game. This will prove that the scheme is secure.

For example, a simple public key encryption scheme for one-bit messages (let $G$ be a PRG, and $F$ be a puncturable pseudorandom function family) would be the following.

• The secret key $SK$ is just a puncturable PRF key $k$.
• The public key $PK$ is the obfuscation of an Encrypt program. Encrypt takes a message $m$ and randomness $r$, and outputs $(G(r), F_k(G(r)) \oplus m)$.
• To decrypt a ciphertext $(c_1, c_2)$ given $SK$, one just computes $F_k(c_1) \oplus c_2$.

In the IND-CPA security game, there is a challenger and an adversary. The challenger generates the public and secret key, and gives the public key to the adversary. The challenger also generates an encryption of a random bit $b$, and gives this to the adversary. The adversary wins if he can guess the bit that the challenger chose.

In the first hybrid, the challenger encrypts by choosing a truly random $\tilde{r}$, and generating the ciphertext $(\tilde{r}, F_k(\tilde{r}) \oplus b)$. This is indistinguishable by the security property of a pseudorandom generator.

In the next hybrid, the program Encrypt which is obfuscated and given to the adversary uses a punctured key $k\{\tilde{r}\}$ instead of the full PRF key $k$. This is with high probability functionally equivalent, because $\tilde{r}$ is most likely not in the range of $G$. So by the security of iO, this hybrid is indistinguishable from the previous one.

Next, the ciphertext is generated by choosing a truly random bit $p$, and generating the ciphertext $(\tilde{r}, p \oplus b)$. This is also indistinguishable to the adversary, because the punctured key reveals nothing about $F_k(\tilde{r})$. That is, if these two hybrids were distinguishable, then given only $k\{\tilde{r}\}$, one could distinguish between a truly random bit $p$ and the true value $F_k(\tilde{r})$.

In this hybrid, it is clear (by analogy to a one-time pad) that no adversary can distinguish a ciphertext encrypting $0$ from a ciphertext encrypting $1$. So the original scheme is also secure.

Sahai and Waters achieve more than just public-key encryption – they also achieved the long-standing open problem of publicly deniable encryption. This is an encryption system for which if $Encrypt(m ; r) = c$, one can also compute a “fake” randomness $r'$ for any other message $m'$ such that $Encrypt(m'; r')$ is also equal to c, and $r'$ is indistinguishable from $r$. The motivation is that after a message is encrypted, coercing the encrypter into revealing his message is futile – there is no way of verifying whether what he says is the truth. Note that of course the decrypter could be coerced to reveal his secret key, but there’s nothing that can be done about that.

The basic idea of the deniable encryption scheme is that the encryption public key is again an obfuscated program – this program takes a message and randomness string. If the randomness string has some rare special structure (it is a hidden sparse trigger), it is interpreted as encoding a particular ciphertext, and the program will output that ciphertext. Otherwise, the program encrypts normally. There is also a public obfuscated Explain program, which allows anybody to sample a random hidden sparse trigger, but not test whether or not a string is a hidden sparse trigger.

At present, iO obfuscation is known to imply some very powerful primitives, including for example multi-input functional encryption. It is still open to construct fully homomorphic encryption for iO, or even collision resistant hash functions from iO, or to show that no such reduction is possible.

[1] On the (Im)possibility of Obfuscating Programs, Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, Yang, 2001.
[2] Candidate Indistinguishability Obfuscation, Garg, Gentry, Halevi, Raykova, Sahai, Waters, 2013.
[3] How to Use Indistinguishability Obfuscation: Deniable Encryption, and More, Sahai, Waters, 2014.

1. I may be wrong, but isn’t for deniable encryption the case that one want, if $\textrm{Encrypt}(m;r)=c$, to produce on input $(m,c)$ a “fake randomness” $r^\prime$ indistinguishable from $r$ such that $\textrm{Encrypt}(m;r^\prime)=c$ (and not for an arbitrary $m^\prime$ — the message itself is the same, but the “explanation” (randomness used) for the encryption of $m$ into $c$ can be “faked”)?