1
$\begingroup$

I have some troubles with this proof from Foundations of Cryptography by Oded Goldreich p.52. Why exactly does the parsing of x to x'x'' take quadratic time in length x'x''? If I have |x'x''|=p(|x'|), and a x of this length. I will try step by step all prefix lengths |x'| in {1, 2, ..., |x|}, till I have p(|x'|)=|x|. So I determine at most p(1), p(2), ... p(|x|). I am not quite sure what to say about the complexity. And if I get an input of the form g(Un), why I cannot instantly request a successful f-inverter to get me the inverse of this. Don't I assume that every attacker knows how g works, say how the description is? (Kerckhoffs principle). Why is the chance dropping? And I do not get why f(desc(M),x) is weakly oney-way in the abstract sense. I mean we just showed it for f(desc(Mg),x).

enter image description here

$\endgroup$

0

Your Answer

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

Browse other questions tagged or ask your own question.