Program obfuscation for all circuits is a long-standing open problem and a very active area of research. Proposed solutions for this problem rely on heavy mathematical tools such as multilinear maps and it is unknown how to instantiate this primitive from more standard assumptions. Nevertheless, it turned out that it is possible to construct obfuscators for more restricted functionality classes from standard assumptions. One recent result in this area consists of an obfuscator for the pattern matching with wildcards functionality.
In this deliverable, we present practical obfuscators for two different functionality classes and build up on the results of Bishop. Due to the close relation between program obfuscation and functional encryption, this result tackles one of the main goals of WP4, the construction of practical functional encryption schemes. In more detail, we describe a new knowledge assumption called KOALA introduced by Beullens and Wee in the context of the FENTEC project.
Using this assumption, we present the practical virtual black box (VBB) obfuscators for the big subset functionality and the pattern matching with wildcards functionality. Therefore, we also present the comparison and analysis between the two different works.