A mathematical problem in software watermarking

Question

I am wondering if there are any existing works/ideas that are related to the following problem. A solution of this problem can be probably useful in software watermarking.

Given,

• Two sets $\mathcal{W}$ and $\mathcal{H}$ (whose sizes are typically between 10 and 50)
• A bijection $f: \mathcal{W} \rightarrow \mathcal{H}$

The problem is to construct a function $\mathcal{F}$. The domain of $\mathcal{F}$ is the set of sequences of elements of $\mathcal{W}$, and the codomain is the set of sequences of elements of $\mathcal{H}$. The desired properties of $\mathcal{F}$ are given below.

Notation: $S_i$ represent the $i^{th}$ element of sequence $S$.

Definition: $\mathcal{F}$ behaves normally $\ $for a sequence $WS$ of length $N$ iff $\mathcal{F}(WS) = HS$, length of $HS$ is $N$, and $HS_i = f(WS_i)$ for $1 \leq i \leq N$.

Construct $\mathcal{F}$ and compute a sequence $P$ (of elements of $W$) of length $N$ such that:

1) $\mathcal{F}$ behaves normally for almost all sequences of elements of $W$

2) $\mathcal{F}$ and $P$ satisfy following constraints

$\ $ a) $\mathcal{F}(P) = Q$, length of $Q$ is $N$

$\ $ b) $Q_i = f(P_i)$ for $1 \leq i < N$ (i.e., $\mathcal{F}$ behaves normally for the $P$’s prefix of length $N-1$)

$\ $ c) $Q_N \neq f(P_N)$

$\ $ d) it is computationally hard to discover the sequence $P$ with the knowledge of $\mathcal{F}$'s implementation and the bijection $f$.

Answer 1

There is a straightforward solution, using known techniques for obfuscating point functions.

Background. First, go read the following papers:

• Positive Results and Techniques for Obfuscation. Benjamin Lynn, Manoj Prabhakaran, Amit Sahai. Eurocrypt 2004.

• On Obfuscating Point Functions. Hoeteck Wee. STOC 2005.

Don't come back until you've read those papers, as my solution uses their scheme as a building block. Short summary: "A point function is a Boolean function that assumes the value 1 at exactly one point." A point function can be obfuscated in practice (e.g., in the random oracle model).

My solution. Choose the sequence $P$ randomly. Define the auxiliary function $g$ by $g(P)=1$ and $g(P')=0$ for all other sequences $P'$ over $W$. Note that $g$ is a point function. Now let $\hat{g}$ be an obfuscation of $f$, e.g., using the techniques described above. Choose $Q$ arbitrarily. Finally, define $F$ as follows: on input $X$, $F$ first checks whether $\hat{g}(X)=1$, and if yes, outputs $Q$, otherwise it behaves normally (i.e., outputs $f(X_1),f(X_2),\dots,f(X_N)$. This meets all of the requirements you identified. You can modify this construction in a straightforward way to hide $Q$ as well, if you wish to.

Comment. I'm pretty skeptical whether this will be useful for building an obfuscation scheme that will be secure in practice; my suspicion is that it will not be useful. You might be able to get some theoretical results, but I don't think those theoretical results will prove very useful in practice, because I expect there will be attacks that will work by violating the assumptions made in your security theorem (e.g., the attacker will use dynamic analysis to find $P$, and then all security is lost).