# Traitor-tracing PRF

I'm looking for a pseudorandom function (PRF) with "traitor-tracing" properties.

More specifically, I'd like there to be multiple equivalent keys, so I can give different parties different keys, but have them yield the same operation. In a standard PRF, there is a single key $k$, and everyone who uses the PRF is given the same key $k$. But if one of the participants is hacked and the key $k$ is published on the Internet, I have no way of knowing which participant was hacked.

So, it would be nice if we could construct a PRF-like object with the following properties:

• The object is a function $F: \mathcal{K} \times \{0,1\}^m \to \{0,1\}^n$, where $\mathcal{K}$ is some keyspace.

• There is a key generation process that, instead of outputting a single key $k \in \mathcal{K}$, outputs multiple equivalent keys $k_1,k_2,\dots,k_p \in \mathcal{K}$. These should have the property that $F(k_1,x)=F(k_2,x)=\cdots = F(k_p,x)$ for all $x$ (or for almost all $x$). Also, $F(k_i,\cdot)$ is a secure pseudorandom function (PRF).

• Given a single key $k_i$, it is hard to compute another key $k'$ such that $F(k_i,x)=F(k',x)$ for all $x$ (or for most $x$). Or, just as good: there exists a traitor-tracing identification algorithm $T$ such that, for any adversary $A$ who, on input $k_i$, computes a derived key $k'$ such that $F(k_i,x)=F(k',x)$ for all $x$ (or for most $x$), $T(k',k_1,k_2,\dots,k_p)$ has a high probability of outputting $i$.

This would allow traitor tracing. This object would allow us to share a PRF key among up to $p$ participants: a central authority generates $p$ equivalent keys $k_1,\dots,k_p$ and gives $k_i$ to the $i$th participant. Now they can each use their own key. If one of the participants is hacked and their key is stolen, we can identify who is responsible.

Can this be done? Is there any way to construct such an object?

• If that would allow traitor tracing then indistinguishability obfuscation is impossible. $\hspace{1.61 in}$ – user991 Mar 13 '14 at 22:35
• 2. Do any other alternative approaches occur to you, for dealing with this problem? Namely, the problem that one of the participants might have their server hacked and their key stolen, and if that happens, it'd be nice if there was some way to track down which participant was responsible (which participant didn't secure their server well enough). Any creative ideas? – D.W. Mar 13 '14 at 23:23
• I was referring to the fact that it would be quite hard to show that your assumptions about $F$ suffice for traitor tracing, not that such traitor tracing is implausible. $\:$ There may be a way to achieve black-box traitor tracing, which involves having the key generation process output extra info that allows a tracer to (possibly adaptively) $\:$ (continued ...) $\;\;\;\;$ – user991 Mar 13 '14 at 23:44
• (... continued) $\:$ compute $x$ values such that querying on them should reveal what key the adversary got. $\:$ (I'm not aware of any candidate constructions for that.) $\:$ Alternatively, one could hope for a scheme in which a semi-honest key generator cannot find an $x$ value for which different keys give different outputs, but that such values nonetheless exist. $\;\;\;\;$ – user991 Mar 13 '14 at 23:46
• @RickyDemer, I realized there is a big hole in my reasoning. The argument only shows that if the PRF can be evaluated in NC1, then it's implausible that something like I described can be used for traitor tracing (since we have good reason to believe that indistinguishability obfuscation of NC1 functions is possible). However, if the PRF lives in a higher complexity class, then I think that kind of reasoning goes away, since if I understand correctly, we only know plausible constructions for obfuscation of NC1. Is that right? – D.W. Mar 14 '14 at 15:20

The properties you list do not suffice for traitor-tracing, since it's
not necessarily easy to find a compatible key from a leaked circuit.
In particular, if the traitor tracing property holds and key generation
process produces keys that satisfy the equality property for all $x$,
then indistinguishability obfuscation of the functions $\: x\mapsto F(k\hspace{.02 in},\hspace{-0.03 in}x) \:$ is impossible.

On the other hand, when equality is only required to hold for all-but-a-small-number-of
$x$ values, one can construct a PRF with black-box secret-key traitor tracing
from a puncturable PRF whose punctures allow indistinguishability obfuscation.

The key generator would choose $k$ and a set of domain elements uniformly-without-replacement,
choose subsets of that set according to parameters, puncture $\: x\mapsto F(k\hspace{.02 in},\hspace{-0.03 in}x) \:$ at those subsets,
change the outputs of each punctured program on the set it was punctured at
in a way that depends on details, apply indistinguishability obfuscation to the
modified punctured programs, and then output the obfuscated programs.
To evaluate, one would just apply the obfuscated program to the input.
To trace, one would query the evaluator on a large enough subset of the originally chosen
set and base the response on what values are returned, in a way that depends on details.

("secret-key traitor tracing" is as opposed to "public-key traitor tracing".)

• Thank you! The first paragraph doesn't rule out all constructions, right, since we don't know whether indistinguishability obfuscation is possible beyond NC1? Are there any guesses/conventional wisdom about whether indistinguishability obfuscation is likely to be feasible for higher complexity classes? Your construction from a puncturable PRF is elegant... but alas, I was hoping for something efficient in practice, and with known constructions for indistinguishability obfuscation, I'm afraid this will be highly inefficient. – D.W. Mar 14 '14 at 15:19