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.


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

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

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

Background. First, go read the following papers:

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.