<p>There is a straightforward solution, using known techniques for obfuscating point functions.</p>

<p><strong>Background.</strong> First, go read the following papers:</p>

<ul>
<li><p><a href="http://www.cs.princeton.edu/~mp/pub/ob.pdf" rel="nofollow">Positive Results and Techniques for Obfuscation</a>. Benjamin Lynn, Manoj Prabhakaran, Amit Sahai.  Eurocrypt 2004.</p></li>
<li><p><a href="http://www.cs.columbia.edu/~hoeteck/pubs/obf-point-stoc05.pdf" rel="nofollow">On Obfuscating Point Functions</a>.  Hoeteck Wee.  STOC 2005.</p></li>
</ul>

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

<p><strong>My solution.</strong> 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.</p>

<p><strong>Comment.</strong> 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).</p>

CC BY-SA 3.0
2013-02-28T02:10:32.840Z
2013-02-28T02:10:32.840Z
D.W.
<p>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.</p>

<p>Given,</p>

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

<p>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.</p>

<p><strong>Notation:</strong>
$S_i$ represent the $i^{th}$ element of sequence $S$.</p>

<p><strong>Definition:</strong>
$\mathcal{F}$ <em>behaves normally</em> $\ $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$.</p>

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

<p>1) $\mathcal{F}$ behaves normally for <em>almost all</em> sequences of elements of $W$</p>

<p>2) $\mathcal{F}$ and $P$ satisfy following constraints</p>

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

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

<p>$\ $  c) $Q_N \neq f(P_N)$ </p>

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

CC BY-SA 3.0
2012-07-02T13:19:14.167Z
Can you define "almost all" in your point 1)? Also, can you give more information on the relationship between this problem and watermarking?
cody
<reference-request><co.combinatorics><cr.crypto-security>
A mathematical problem in software watermarking
Anand
# A mathematical problem in software watermarking

(Asked by: username_0 on 2012-07-01)

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

**Tags:** reference-request, co.combinatorics, cr.crypto-security
> **Comments:**
> **username_1**: Can you define "almost all" in your point 1)? Also, can you give more information on the relationship between this problem and watermarking?  

---

## 1 answers

### Answer by username_2 on 2013-02-28. Score: 3

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](http://www.cs.princeton.edu/~mp/pub/ob.pdf). Benjamin Lynn, Manoj Prabhakaran, Amit Sahai. Eurocrypt 2004.
* [On Obfuscating Point Functions](http://www.cs.columbia.edu/~hoeteck/pubs/obf-point-stoc05.pdf). 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).


---

