# Tag Info

6

Do the post-quantum ciphers also automag/tically address the 1st problem? Not really, however to explore that in any detail, we need to explore what the 1st problem is. If $P=NP$ is proven true, what does that practically mean? Well, it might have absolutely no practical ramifications, or it might mean that virtually all known cryptographical systems ...

1

Homework it is. Basically what OP is asked to do is to show that $g: \{0, 1\}^{m} \to \{0,1\}^{2m}$ is or is not $2^\sqrt {m}$-one-way function. Or in other words adversary A time-success ratio for inverting function $g$ is better/worse than $2^\sqrt {m}$ E: So we have basically two tasks. First we have to determine how big is average ...

2

I think you can prove $g$ is not guaranteed to be one-way by the following counter example. First let $S$ be the set of all strings in $\{0,1\}^{2m}$ that starts with $m$ zeroes. Take any OWF $f$ of the type you describe. Consider the function $f'$ that is identical to $f$ except on all inputs $x \in S$ it acts as the identity function. I.e. for all \$x \in ...

Top 50 recent answers are included