Cryptographic obfuscation is a powerful tool that makes programs “unintelligible” yet still runnable.
It essentially gives programs the ability to keep secrets. The practical applications of obfuscation
range from keeping secrets in banking applications to preventing software theft to providing secure
messaging applications. The cryptographic applications of obfuscation are also vast – a tool
that hides secrets in programs essentially enables all other cryptographic constructions. Despite
(or perhaps due to) its power, obfuscation is currently wildly inefficient and on shaky theoretical
ground. Its shaky theoretical ground in particular has resulted in a lack of engineering effort at
making it more efficient. In this work, we focus largely on efficiency.
We explore the concrete efficiency of multilinear maps, which are the basis of many cryptographic
obfuscation constructions. Multilinear maps are mathematical objects that allow oblivious
addition and multiplication of encrypted values. Using multilinear maps, we give the first
ever implementations of obfuscation and multi-input functional encryption (MIFE: a variant of
obfuscation) for branching programs. Along the way, we create the 5Gen framework for implementations
of multilinear map-based applications. We apply the 5Gen framework to experiment
with obfuscating point functions and MIFE of order-revealing encryption.
We also explore efficiency in the context of obfuscators and MIFE for circuits. Circuits are
more efficient than branching programs for many functions. We give the first MIFE construction for circuits and prove its security in an ideal model. Our scheme is efficient. To compare, we
implement all known circuit obfuscation schemes using the 5Gen framework, and experiment
with obfuscating a PRF. This results in the most complex PRF obfuscated to date – with 12 bits
Finally, recently Bishop et al. showed an obfuscation scheme for the specific functionality of
wildcard pattern-matching [BKM+18]. This is a simple type of string matching where strings
must match a pattern exactly except where there are wildcards. This obfuscation scheme simply
relies on the generic group model, with no multilinear maps. Inspired by their work, and the
deep connection of functional encryption to obfuscation, we give a function-private, public-key
functional encryption scheme for the same wildcard pattern-matching functionality. Our scheme
is the first such scheme and we prove its security in a generic model.