8
$\begingroup$

Let $f_k(x)$ be a boolean function of two arguments with two properties:

  1. The function $f$ can be efficiently computed.

  2. The output is always 0 or 1, and for any fixed $k$, if we choose $x$ randomly, $\Pr[f_k(x)=1]$ is tiny (say, exponentially small).

Question: Is there a generic way to, given $k$, obfuscate an arbitrary such function? In other words, can all functions with this property be obfuscated?


Here's what I know. The function $f_k(x)=1$ if $x=k$ or $0$ otherwise can be obfuscated (it's called a point function). The function $f_k(x)=1$ if $d(k,x)<t$ or $0$ otherwise can be obfuscated, where $d(\cdot,\cdot)$ is the Hamming distance and $t$ is a constant threshold (see the fuzzy vault scheme of Juels and Sudhan). These are simple examples of functions that meet these properties and can be obfuscated. Perhaps all functions in this class can be obfuscated?

I also know that there is no generic scheme that can obfuscate all functions -- but perhaps it's possible to find a generic scheme that obfuscates all functions in this class.


Motivation: This would be useful for verification of biometrics. Think of $k$ as the template for the user, and $x$ as the biometric that's submitted to the system; $f$ verifies whether the user should be accepted.

Password verification is a simple case of this that corresponds to $f_k(x)=1$ iff $x=k$; here $k$ is the saved password stored when the user set up their account, and $x$ is the password entered by the user during the authentication process. Password hashing is a method of obfuscating this verification function. The fuzzy vault scheme is suitable for biometric schemes where we think the sensor might introduce random bit errors. But there are other biometric schemes that might involve more complex procedures for verifying the proposed biometric, and I'm wondering if there is any generic result that demonstrates all such verification schemes can be obfuscated.

I'm fine with any reasonable form of obfuscation (including indistinguishability obfuscation).

$\endgroup$
  • $\begingroup$ Not an answer, but a pointer: what you are looking for resembles the obfuscation of evasive functions (although their exact definition differ from yours), and obfuscating evasive functions has been studied in several papers. I will provide a more complete answer later, there exist many scheme for obfuscating interesting subclasses of 'mostly-zero' functions. $\endgroup$ – Geoffroy Couteau Mar 1 at 23:39
  • $\begingroup$ @GeoffroyCouteau, awesome, that sounds like just the sort of thing I'm looking for. Thank you. I look forward to your answer! $\endgroup$ – D.W. Mar 2 at 0:51
10
$\begingroup$

I provide a summary below of what is currently known (to my knowledge) regarding obfuscation of various class of "mostly-zero" functions.

From Indistinguishability Obfuscation


What we can obfuscate: all efficient functions

Which notion of security: indistinguishability obfuscation

Underlying assumptions: new, exotic, and relatively poorly understood assumptions.

Is it efficient? Nope.


You state in your question:

I also know that there is no generic scheme that can obfuscate all functions -- but perhaps it's possible to find a generic scheme that obfuscates all functions in this class.

However, as far as we know, it is perfectly possible that all efficiently computable functions (hence in particular all functions you are interested about) can be obfuscated with an iO scheme. We have a bunch of concrete candidates, and there has been a large body of work on the underlying assumptions. Providing a complete treatment would be out of scope for this question (I count more than 160 papers on the subject since 2013), but roughly, all known constructions of iO rely on exotic assumptions: either the existence of graded encoding schemes, whose security is poorly understood and with many (many) existing attacks, the latest being this one, or recent assumptions regarding the weak pseudorandomness of some extreme families of low depth pseudorandom generators -- some assumptions made in the three latest results (1, 2, 3) in this area have already been broken. Furthermore, none of the iO schemes we currently know of would be concretely efficient. Still, as a theoretical feasibility result, all functions you care about can be obfuscated (under exotic assumptions), where the obfuscation security notion is that of indistinguishability obfuscation.

From Multilinear Maps


What we can obfuscate: evasive low-degree polynomial modulo a prime

Which notion of security: virtual black box obfuscation (the strongest possible notion)

Underlying assumptions: new, exotic, and relatively poorly understood assumptions.

Is it efficient? Nope.


Barak et al. study in this paper the possibility of achieving even stronger notions of obfuscation (such as virtual grey box obfuscation, or virtual black box obfuscation) for the class of evasive functions. A class of function is evasive if, for any fixed input $x$, a random function from the class evaluates to $0$ on $x$ with overwhelming probability. While their results are mainly negative, Barak et al. also provide an interesting positive result: under a new perfectly-hiding multilinear encoding assumption, which is the same kind of assumption that is used in constructions of iO schemes (hence suffers from comparable weaknesses and gives comparable (in)efficiency), there exists a virtual black box obfuscator for evasive functions that tests if a low-degree polynomial evaluates to zero modulo some large prime. Virtual black box obfuscation is the ultimate security notion for obfuscation: while iO states that it should be infeasible to distinguish two functionally equivalent obfuscated circuits, VBB states that everything that the adversary sees, given the VBB obfuscation of the function, can be simulated given only black-box access to the function. It is known that VBB is in general impossible to achieve; hence, this work shows that this impossibility does not seem to hold anymore for this restricted class of evasive functions.

From LWE


What we can obfuscate: conjunctions, compute-and-compare functions

Which notion of security: distributional virtual black-box

Underlying assumptions: the well-studied (conjectured quantum-resistant) LWE assumption (or entropic variants of it)

Is it efficient? Not really, but depending on the primitive to obfuscate, it can be doable.


There has been recently a large body of work identifying interesting classes of "mostly-zero" functions, which can be obfuscated under the plain (or variants of) LWE assumption, which is a well-studied assumption.

1) Conjunctions. Several papers have proposed schemes to obfuscate functions of the form

$f : (x_1, \cdots, x_n) \rightarrow \bigwedge_{i \in I} y_i$,

where each $y_i$ is either $x_i$ or $1-x_i$, and $I$ is a subset of $[1, \cdots, n]$. This paper shows how to obfuscate this class of function under an "entropic variant" of the ring-LWE assumption. Obfuscating a 64-bit function takes a few hours, and evaluating the obfuscated program takes a few seconds. The security notion achieved is that of distributional VBB obfuscation, a variant of the notion of VBB obfuscation which also relies on the entropy of the obfuscated function.

2) Compute-and-compare functions. This is a very nice result achieved independently in this paper and in this paper. Assuming only the plain LWE assumption, they show how to compute a very large class of interesting evasive functions: the functions that have two secret values $(\alpha, \beta)$ hardcoded and, on input $x$, evaluate an arbitrary function $f$ on $x$ and output $\alpha$ if and only if $f(x) = \beta$ (and $\bot$ otherwise). This captures as a particular case conjunctions, point functions, but also much more. Their construction also achieves distributional virtual black-box obfuscation.

From Group-Based Assumptions


What we can obfuscate: conjunctions, pattern matching, hyperplanes membership

Which notion of security: distributional VBB

Underlying assumptions: from entropic DDH to the generic group model

Is it efficient? It can be reasonably efficient


Many constructions have also been designed under various assumptions in standard discrete-log-hard abelian groups. Most notably:

1) Conjunctions can also be obfuscated in the generic group model, and achieve distributional VBB, as shown by this very nice recent paper.

2) Pattern Matching. Two recent works have considered the task of obfuscating functions that test whether a given input string contains a pattern, with "wildcards" (i.e., the pattern can contain wildcards * that correspond to "any value there"), and achieve distributional VBB for patterns having some entropy. These are very nice results, and are in addition relatively efficient compared to everything that I've discussed so far. The first of these paper achieves security in the generic group model, while the second achieves security in the standard model, under a knowledge-of-exponent style assumption (i.e., something plausible, but far from being the most well understood assumptions).

3) Hyperplane Membership Testing. Eventually, this paper shows how to obfuscate hyperplane membership testing (i.e., checking whether an input vector belongs to a secret obfuscated hyperplane), which generalize point functions to a much larger class. The obfuscation is relatively efficient and is proven secure under a strong variant of the DDH assumption.

Note: there exists also DDH-based obfuscation scheme for re-encryption functions, but those do not fit into your notion of mostly-zero functions.

From One-Way Functions


What we can obfuscate: point functions

Which notion of security: distributional VBB

Underlying assumptions: exponentially strong one-way functions, one-way permutations, or deterministic encryption

Is it efficient? Yes


To conclude this overview, the weakest of all these "mostly-zero" functions that you want to obfuscate are point functions, which are equal to zero everywhere, except on a specific point. Such functions can be obfuscated, depending on the exact notion of obfuscation achieved, assuming the existence of exponentially strong one-way functions (here) or one-way permutation (here), or deterministic encryption (here) all being highly plausible assumptions (the second one being even a fundamental assumption of cryptography). Obfuscation of point functions has been studied in depth and has many applications in cryptography. Note that to achieve stronger notions of obfuscation for point functions (e.g. to achieve composability, or non-malleability), one typically rely on stronger DDH-like assumptions (e.g. here and here).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.