Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

New answers tagged

0

This would appear to be impossible. You require that $|x_1 - x_2| < \epsilon$ implies that $|f(f(x_a, k_a), k_b) - f(f(x_b, k_b), k_a)|<\delta$ ; this implies that $f(f(x_a, k_a), k_b)$ is continuous over $x_a$. Now Charlie knows $k_a, k_b$ and can compute the target value $f(f(x_a, k_a), k_b)$; a simple bisection search over the function $f(f(x, k_a)...


0

Not only do we "allow" to give $A$ (where $A$ is the adversary that inverts $f$) random strings which aren't in $\text{Im}(f)$, you hope that the random string is not in $A$'s range. First of all, it does not make sense to "disallow" strings which aren't in the image of $f$. $A$ is not some magic oracle, but rather a probabilistic turing machine which (...


0

Let $n\in \mathbb{N}$, and fix $x,y \in \{0,1\}^n$, $f(x,y)=G(x) \in \{0,1\}^{2n}$. By $f$'s definition, $$\forall x,y_1,y_2 \in \{0,1\}^n,\;f(x,y_1)=f(x,y_2).$$ Hence, if we define the function $f'\colon\{0,1\}^n\to \{0,1\}^{2n}$ by $f'(x)=f(x,0^n)$ we get that $\operatorname{Im}(f)=\operatorname{Im}(f')$ and $\lvert\operatorname{Im}(f')\rvert\le \lvert\{0,...


Top 50 recent answers are included