0
$\begingroup$

I am currently studying a course in cryptography, and I have this exercise about OWF. enter image description here

enter image description here

I'm failing to prove that this is an inverter to f. Am I in the right direction at all? Thank you!

$\endgroup$
1
  • $\begingroup$ Transcribe those as text, and use MathJax for mathematical notations (or ask others to edit them in for you), images take up a lot of bandwidth for people on cellular network. $\endgroup$
    – DannyNiu
    Mar 28 at 1:14

2 Answers 2

1
$\begingroup$

Assume $g$ is not an OWF. What does it mean for $g$? How can this knowledge about $g$ help You find a preimage of $f$? What does it mean about $f$ being OWP?

$\endgroup$
0
$\begingroup$

What is the probability that the $x$ you got ( from your reduction ) is the correct pre-image of $y$ with $f$? I.e., $\Pr[f^{-1}(y) = x]$?

$\endgroup$
3
  • $\begingroup$ i thought its 1/2 but lets say n= 100. assume all permutations of {0,1}^n such that they contain 5 zeros are mapped to 1111100000. also assume f(1111110000)=1111100001 (6 4 zeros). now if (g^-1)(111110000) = 1111110000 then f^-1 is right at only one out of about 250 times. $\endgroup$
    – Niv Peretz
    Jul 3, 2023 at 8:04
  • $\begingroup$ I get it that that cannot be a one-way permutation but I can't prove it formally $\endgroup$
    – Niv Peretz
    Jul 3, 2023 at 8:04
  • $\begingroup$ let's say n=10 * $\endgroup$
    – Niv Peretz
    Jul 3, 2023 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.