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

Tag Info

New answers tagged one-way-function

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