Using Yao's principle to find a lower bound 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!
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&gt;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$.