2
$\begingroup$


This is a HW question, so I'm not expecting any answers, just a general guidance/help.

Definition. Given $\underset{\neq0}{\underbrace{s}}\in\left\{ 0,1\right\} ^{n}$, a function $f:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} ^{n}$ will be called s-difference-preserving if for all $x,y\in\left\{ 0,1\right\} ^{n}$ s.t. $x\neq y$: $x\oplus y=s\iff f\left(x\right)=f\left(y\right)$ (where $\oplus$ is the bitwise xor operation).

Given a difference-preserving (that is, there exists such s so it is s-difference-preserving) function $f$, we talk about algorithms that find such $s$.

We need to prove that every such random (las-vegas) algorithm worst case (w.c. input) average (on the randomness of the algorithm) complexity is $\Omega\left(\sqrt{2^{n}}\right)$. Where by complexity, we talk about query-complexity. That is, how many times we need to query f, to find a value for an input $x$ - that is, find $f\left(x\right)$.

What I know and tried so far:

I assume this is a classic problem for Yao's principle.
So I want to find a distribution, and an optimal deterministic algorithm for it (optimal on average, on that distribution), such that its query-complexity is \Omega\left(\sqrt{2^{n}}\right) on average on that distribution.

Given an $s$, it's easy to create an s-difference-preserving function, since any $s$ defines a partition of pairs on $\left\{ 0,1\right\} ^{n}$. So we just need to choose a different value for every pair $x,y$ s.t. $x\oplus y=s$.

I also know $f\left(0\right)=f\left(s\right)$, and that to find $s$ for a fuction, it's enough to find a pair $x,y$ s.t. $f\left(x\right)=f\left(y\right)$, and then calculate $x\oplus y$.

I thought of defining $\forall i\in\left[\sqrt{2^{n}}\right]:\ s_{i}=i\cdot\sqrt{2^{n}}-1$. And create $s_{i}$-difference-preserving function $\forall i\in\left[\sqrt{2^{n}}\right]$.

Define a uniform distribution on them and have the deterministic algorithm check the values of every $s_{i}$. This is done in $\sqrt{2^{n}}$ queries on average.
But I don't know how to prove this algorithm is optimal for that distribution. Furthermore, I suspect it isn't, since then I would be able to do the same with $s_{i},\ \forall i\in\left[2^{n}\right]$ and “prove” a lower bound of $2^{n}$ which is probably not true.

I would love any help with this.
Also, not as part of the HW, but because I'm interested (these are questions we don't need to submit a solution to), can you think of any deterministic algorithm for the general problem? can you think of any monte carlo random algorithm (with 0.5 chance of success)?

I hope this is not too long, and written clearly enough. Would appreciate any help. Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Suppose that there exists a Las Vegas algorithm $A^f$ asking $q(n)=o\big(2^{n/2}\big)$ queries. Let $Q_f\subseteq\{0,1\}^n$ be the random variable which denotes the set of queries raised by the algorithm with oracle $f$.

Sample $f$ from the uniform distribution over the collection of all difference preserving functions, and choose $s\in\{0,1\}^n$ uniformly at random, both independently from your algorithm's coins. Let us now ask what is the probability that there exists $g,g':\{0,1\}^n\rightarrow\{0,1\}^n$ such that $g,g'$ agrees with $f$ on $Q_f$, $g$ is $s$-difference preserving, and $g'$ is not. We denote this probability by $p_A$. Note that if $p_A>0$ then your algorithm cannot respond correctly on all inputs, since there exists $f,s$ such that $f|_{Q_f}$ has both $s$-preserving and non $s$-preserving extensions.

If $f|_{Q_f}$ does not have an $s$-preserving extension, then either there exists $x\in Q_f$ such that $x\oplus s\in Q_f$, or we have $x,y\in Q_f$ with $f(x)=f(y)$. For the first case, Note that $x\oplus s$ is uniformly distributed over $\{0,1\}^n$ and independent of $Q_f$, thus the probability that there exists such $x$ is bounded by $\sum\limits_{x\in Q_f}\frac{|Q_f|}{2^n}\le\frac{q^2(n)}{2^n}=o(1)$. A similar bound is obtained for finding a collision for a random $f$ (the preimage of any element in the range of $f$ is of size 2). Additionally, $f$ is not $s$ preserving with probability $\ge\frac{1}{2^n}$, so we can also (with high probability) find a non $s$ difference preserving extension for $f$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for your answer! I'm not sure why there exists such an $x\in Q_{f}$ if $f|_{Q_{f}}$ doesn't have the extension. What about the case where there exists $x,y\in Q_{f}$ s.t. $f\left(x\right)=f\left(y\right)$ but $x\oplus y\neq s$ ? $\endgroup$
    – Idra
    Nov 4, 2018 at 21:54
  • $\begingroup$ Also, unless I'm mistaken, that $f|_{Q_{f}}$ extension that is not s-preserving, should be still preserving for another s, as our algorithms only receive preserving functions, and need to find their s. $\endgroup$
    – Idra
    Nov 4, 2018 at 22:04
  • 1
    $\begingroup$ I edited to make $f$ random as well, which should answer your questions. $\endgroup$
    – Ariel
    Nov 4, 2018 at 22:46
  • $\begingroup$ Thanks! I'm still wondering. If there exists $x,y\in Q_{f}$ s.t. $f\left(x\right)=f\left(y\right)$ we can't extend it for any s. What if $Q_{f}$ always contain such elements? In fact, it seems to me almost a requirement for the algorithm to decide... $\endgroup$
    – Idra
    Nov 4, 2018 at 22:54
  • 1
    $\begingroup$ $f$ is a random difference preserving function. Think of it as choosing $u\in\{0,1\}^n$ at random and then choosing, for each $x\in\{0,1\}^n$, a random value for $f(x),f(x\oplus u)$. Let $Q_f^i$ where $1\le i\le q(n)$ be the set of the first $i$ queries raised by the algorithm, and let $j$ be the minimal index such that $Q_f^j$ contains a collision. Note that $Q_f^{j-1}$ is independent of $u$, hence the probability of hitting $x\oplus u$ for some $x\in Q_f^{j-1}$ in the $j$'th iteration is bounded by $\frac{|Q_f^{j-1}|^2}{2^n}$. $\endgroup$
    – Ariel
    Nov 5, 2018 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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