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