A Tale of Obfuscation, Punctured Programs and Leader Election

Nov 6, 2022

Credit: Boneh, Dan, et al. "Single secret leader election." Proceedings of the 2nd ACM Conference on Advances in Financial Technologies. 2020.

It is claimed that indistinguishability obfuscation (iO) is the panacea of all cryptographic problems. While I do not know if that is the case, I am recently studying Single Secret Leader Election (SSLE) in blockchain projects and the paper I read gives a beautiful construction via iO that I will introduce below.

Oracle and Obfuscation

Obfuscation is an interesting topic that has many practical applications. Meanwhile, many theoretical works make use of hypothetical oracles, i.e. black box machines that take an input and gives the corresponding output. Sometimes the reason we use an oracle is that we want to hide some secret in the oracle black box that we do not want the adversary interacting with it to know. Consider this hypothetical encryption scheme that encrypts a message \( m \) with randomness \( r \), using a symmetric key \( k \):

\[ \begin{align} \text{Enc}_k(m,r)&= (\text{PRG}(r), \text{PRF}(k,\text{PRG}(r))\oplus m) \text{,} \\ \text{Dec}_k(p,c)&= \text{PRF}(k,p)\oplus c \text{.} \end{align} \]

Note: PRG is a pseudorandom generator with an expansion factor of 2; PRF is a pseudorandom function family.

We observe that anyone using \( k \) for encryption can also use \( k \) for decryption, but what if we only want someone able to encrypt a message with \( k \) for us to read, but not able to decrypt other people's messages to us with the same \( k \)?

A trivial idea is to give everyone an encryption oracle \( \text{Enc}_k(m,r) \) without telling them anything about our key \( k \). They can use the oracle to encrypt messages but they cannot use the oracle to decrypt them. This is sound on paper but not practical because black-box oracles do not exist in real life. However, an intersting observation is that if we can obfuscate the program of an oracle so that it leaks no information, we can then give the obfuscated program to anyone. They can run the program themselves, thus avoiding the need of implementing an oracle, but will not be able to decode the obfuscated program for any useful information.

As a warm-up exercise, consider this hypothetical obfuscation scheme on circuit (i.e. program with a fixed length of input that terminates) \( \lambda \) with \( n \) bits of input:

This obfuscation works because the obfuscated circuit gives no information other than the output of the original circuit, which anyone queries the oracle can know anyway. However, it is also very inefficient because it uses an exponential number of gates (i.e. runs in exponential time). In cryptography it is generally bad to give our adversary exponential power, so we want to restrict our obfuscation to efficient ones. Is there an efficient obfuscation that hides all information?

The Impossibility Result

Unfortuantely, some theory guys constructed an unobfuscatable function: i.e. knowing any efficient implementation of it leaks some information that cannot be known by querying an oracle. To briefly summarize, assume that there exists an efficient obfuscator \( \mathcal{O} \) that transforms a circuit \( A \) to another obfuscated circuit with size at most \( \text{poly}(|A|) \). Define

\[ [f]= \begin{cases} 1 & \text{if statement } f \text{ is true; } \\ 0 & \text{otherwise. } \\ \end{cases} \]

Consider these three circuits:

\[ \begin{align} C_a(x)&=[x=a] \text{,} \\ D_a(A)&=[A(a)=1] \text{,} \\ Z(x)&=0 \text{.} \end{align} \]

Assume we sample \( a \) uniformly randomly from \( \{0,1\}^n \) for some \( n \). Then some adversary \( A^{X,D_a} \) with oracle access to \( (X, D_a) \) cannot distinguish between oracle \( (C_a, D_a) \) and oracle \( (Z, D_a) \) except with negligible probability.

However, if the adversary has access to the obfuscated circuits \( (X', D'_a) = (\mathcal{O}(X), \mathcal{O}(D_a)) \), then they can run \( D'_a(X') \) themselves and distinguish between \( (C_a, D_a) \) and \( (Z, D_a) \) with overwhelming probability.

Therefore, circuit tuple \( (C_a, D_a) \) with input size \( (n, \text{poly}(|C_a|)) \) is unobfuscatable: knowing any efficient implementation of it leaks some information that cannot be known by querying an oracle.

Indistinguishability Obfuscation

Fortunately, the impossibility result only proves that we cannot hide all information of the circuit. On the other hand, in our encryption scheme we only want to hide some information, namely our key \( k \): we do not really care if our adversary knows about the encryption scheme (it is common knowledge anyway), for example. Therefore, we are going to present the definition of an actually existing obfuscation scheme that can do what we want: the indistinguishability obfuscation (iO):

It is not very easy to appreciate the definition of indistinguishability; however, it actually implies that the obfuscation leaks the minimum amount of information possible to any efficient adversary, since we can substitute the program with anything that gives the same functionality, and the adversary will not be able to tell.

This may look a little like Voodoo magic, but we are going to provide a concrete example: we are going to prove that using \( \mathcal{iO}(\text{Enc}_k) \) as the public key is IND-CPA secure in a public-key encryption scheme, with a tool known as a puncturable PRF.

Puncturable PRF and Punctured Program

Puncturable PRF

A puncturable PRF is a PRF where any key \( k \) can be punctured on a input string \( x \) to get a punctured key \( k'=\text{PUN}(k,x) \) such that

  1. The puncturing does not affect evalutation of the PRF except at \( x \), i.e. for all input string \( y \neq x \), \( \text{PRF}(k, y)=\text{PRF}(k', y) \);
  2. The punctured key gives no information about the evalutation at \( x \), i.e. given only \( k' \), \( \text{PRF}(k,x) \) is computationally indistinguishable from a random string.

It is very easy to build a puncturable PRF from the standard GGM construction. Recall that the GGM construction uses a PRG \( G \) to construct a PRF:

To puncture say point $01$, we need to remove all information on the path from \( k \) to \( \text{PRF}(k, 01) \) while preserving the ability to evaluate other points:

We then notice that we can simply use intermediate sibiling nodes of the path as the punctured key: \( k' = (\text{PRF}(k, 1), \text{PRF}(k, 00)) \). This finishes the construction.

Punctured Program

We are now ready to show that an indistinguishability obfuscated version of our encryption scheme, \( \mathcal{iO}(\text{Enc}_k) \), is IND-CPA secure as a public-key encryption scheme.

TBD. See How to Use Indistinguishability Obfuscation: Deniable Encryption, and More p. 23 - 25.

Single Secret Leader Election

TBD. See Single Secret Leader Election p. 11 - 12.