Traitor-tracing PRF

Question

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?

Answer 1

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".)