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