# A mathematical problem in software watermarking

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$.

• Can you define "almost all" in your point 1)? Also, can you give more information on the relationship between this problem and watermarking? – cody Jul 2 '12 at 13:19

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