Cryptomata and obfuscation

Vision

The most ambitious dream of the Programmable Cryptography blog post is the idea of a “cryptomaton”. A cryptomaton could be a piece of code running in the cloud that could take input, maintain private internal state (even from the server running it), and produce provably correct output.

It differs from a hallucinated server in that it is non-interactive: rather than having the server’s internal state distributed among participants, a cryptomaton could be run even on a single untrusted server, or anywhere else. (In particular, hallucinated servers suffer from the weakness of failing if users go offline; cryptomatons would not have this drawback.)

Mathematical toolbox

A key weakness of multiparty computation and fully homomorphic encryption is that decryption of any output requires full permissions. (For example, in a calculation where the initial inputs are threshold encrypted, so that all participants would need to cooperate to decrypt them. With MPC and FHE, decrypting the output requires everybody’s cooperation as well.)

So for cryptomata, we need something else. The “holy grail” would be black-box obfuscation, and it would be perfect for our needs. But there is one problem — black-box obfuscation has been proven to be impossible.

Instead, we have our eyes on two closely related cryptographic primitives, indistinguishability obfuscation (iO) and functional encryption (FE), which are theoretically possible. Here’s what they’re about:

• Loosely speaking, an indistinguishability obfuscater hides the implementation of a program while allowing it to be run. More precisely, two programs that produce the same output would become indistinguishable when passed through an iO.

• Functional encryption is a variant of public-key cryptography: one party uses a public key to encrypt a value $x$; a second party decrypts with a secret key, and learns $f(x)$. This $f$ could be any function, and the secret key depends on the function.

The problem is that, unlike things like ZK or MPC/FHE, iO and FE are still not practical yet and far from real-world deployment.

Research priorities

Our research agenda is two-pronged: We’re interested in any research that would either:

• bring some of these primitives (obfuscation, functional encryption, …) closer to practice, or
• let us do interesting things with already-known primitives.

First prong: Making indistinguishability obfuscation practical

The current state of the art is this iO paper, but we will need huge improvements in performance to be able to obfuscate interesting calculations.

• Can we find cryptographically secure $k$-linear maps, for $k > 2$?

There are known constructions of obfuscation that rely on such maps as a black box.

Concretely, we want an efficiently computable $k$-linear map $G^k \rightarrow H$, where $G$ and $H$ are finite groups (of some large prime order $p$, say), in which the discrete logarithm problem is hard.

At the moment, the only well-studied construction is elliptic curve pairings, for the case $k = 2$: an elliptic curve pairing takes as input two points on an elliptic curve and returns as output an element of a finite field.

One promising approach to trilinear maps involves cup products on higher-dimensional abelian varieties. It seems likely that, if this idea works, similar constructions would lead to $k$-linear maps for $k > 3$ as well. But a number of interesting questions come up already in the trilinear case.

For these problems, choose a prime $p \approx 2^{256}$, so a computation is likely to be feasible if it runs in time polylogarithmic in $p$.

• Are there abelian surfaces over $\mathbb{F}_p$ in whose Néron-Severi group the discrete logarithm problem is hard?
• Can we efficiently compute a cup-product pairing among one Néron-Severi group element and two points on the surface?

• It would be great if there were more “cohomological groups” available on which to do cryptography. Specifically, we’re looking for a finite group where:

  • Group elements have short descriptions, and
  • One can test efficiently whether two group elements are equal. Known examples include:
  • Groups of roots of unity
  • Groups of points of abelian varieties
  • Néron-Severi groups of abelian varieties.

  Are there others?

Second prong: What can be done with already-known primitives?

The iO paper bootstraps its way from a certain limited functional encryption up to full indistinguishability obfuscation.

Can we get the affordances we want (selective decryption of outputs of functions; outputs automatically made public or encrypted for individual users) using lower-level cryptographic primitives? For example, what can we do if we build functional encryption for:

• Decryption (for some encryption scheme)
• ZK proof verification?

How hard is it to build “conditional decryption,” a program that will decrypt a ciphertext only if (say) a certain ZK proof is valid?