שאלה 3 סעיף e

האם A

צריך לרוץ בזמן פולינומיאלי ?

בשאלה 6 אנו מתבקשים למצוא את מספר הפולינומים ממעלה 4 שמקיימים משהו

למה הפולינום f

בדוגמה בשאלה הוא ממעלה 3 ?

האם הפולינומים שאנו מחפשים צריכים להיות מתוקנים ?

(כלומר עם מקדם עליון השווה לאחד)

בשאלה 4 האם

z2

יכול להיות תלוי בתוצאה של הפעלת הפונקציה על

z1 ?

Regarding Q2:

We are asked to describe a probabilistic algorithm that outputs x for (g,g^x), what is the required probability from A'?

And another question regarding Q2: I don't really understand the algorithm A and the difference between it and A', does A has an input?

Thanks

$A$ is an algorithm that succeeds in computing discrete log only for a $\delta$-fraction of $\mathbb{Z}_p^*$. You are required to construct an algorithm $A'$ that solves discrete log for **any** $x\in\mathbb{Z}_p^*$, with probability 1. However, this algorithm only runs in polynomial time in expectation (over its own random choices), and not in the worst case.

אני קצת מסתבך עם ההבנה של הדרישה מאלגוריתם

A'

מבחינת הסתברותי אל מול דטרמינסטי.

בתרגיל עצמו מצוין שהוא אלגוריתם הסתברותי , בעוד שפה ציינת שהוא מוצא את איקס בהסתברות 1. האם זה לא כמו להגיד שהוא דטרמיניסטי?

או שדטרימינסטי או הסתברותי זה משהו שמדבר על זמן ריצה?

לפי מה שאני מבין ממה שכתבת,

אני נדרש למצוא אלגוריתם הסתברותי בזמן הריצה כך שרץ בזמן המצוין באופן הסתברותי(בממוצע?) , אבל מוצא את איקס בהסתברות 1, האם זו הכוונה?

As for the first question, you can construct an algorithm that repeatedly tries to solve the problem, each time using new randomness, the question is how long would it take him in expectation. If you don't feel comfortable with expected time. You may show that there exists an algorithm that runs in (worst-case) time $\mathsf{time}(A) \cdot \frac{n}{\delta}$, and solves the problem with probability at least $1-e^{-n}$. (If you do, please write that we said it was ok in the forum, so that the grader will know.)

Regarding Q6:

Is 1 considered a linear factor or not?

Is 2 considered a linear factor or not?

Thank you

We said explicitly linear factors means polynomials of the form $ax+b$.

Then a can be 0 (as 0 is in Z3).

Otherwise there can't be any degree three polynomial which factors into 4 linear factors (since a multiplicity of 4 degree 1 polynomials will always results in a degree four polynomial).

Am I wrong?

Regarding Q2,

Your tip for us is to run A on inputs of the form $(g, g^{x+r})$. What can we assume about $time(A)$ vs. the complexity of computing multiplication $mod p$, does $time(A) >> log^{2}(p)$?

Regarding Q5,

Can I assume that when A outputs H(x) = H(x') then x != x'?

שאלה 7 סעיף b

האם ניתן להניח כי H

שנתון בשאלה הוא דטרמיניסטי ?

it is given that for all x in Z*p, P(H(g,g^x)) = x is 1/2+epsilon.

1/2+epsilon > 1/2 + epsilon/2, so I don't understand the question. why isn't just using H will suffice?

$\tilde{H}$ works for $(1/2+\delta)\cdot (p-1)$ elements in $\mathbb{Z}_p^*$. It could be that for any $x\leq t$, $\tilde{H}$ only succeeds with probability $1/2$, implying it's no better than random guessing. You need to show that can construct $\tilde{H}_t$ that ,**for any** $x\leq t$, has a $\delta/2$ advantage over random guessing.

השורה האחרונה מבלבלת.

התכוונתי אם זה בסדר שבמקרה הגרוע ביותר האלגוריתם ירוץ בזמן גרוע.. אבל בממוצע יעמוד בדרישה

Yes, this is what expected time means. If you don't feel comfortable with expected time, you may show that there exists an algorithm that runs in (worst-case) time $\mathsf{time}(A) \cdot \frac{n}{\delta}$, and solves the problem with probability at least $1-e^{-n}$. (If you do, please write that we said it was ok in the forum, so that the grader will know.)

Q5:

could it be that the algorithm A that inverts H returns x in a better probability then asked?

it returns an x' such that H(x)=H(x'), and the probability that x==x' is 2^-s.

If you're claiming that $\Pr[A(H(x))=x' \neq x]\geq \epsilon(1-2^{-s})$, then you may want to think about it again. In any case, you should prove your answer.

Let's describe $H$ and $A$ that give a negative example. First, let $H':\{0,1\}^{n+1} \rightarrow\{0,1\}^{n-1}$ be a CRH that shrinks by two bits. Consider $H:\{0,1\}^{n+1}\rightarrow \{0,1\}^n$ defined as follows. For any input $(00x)$, where $x\in\{0,1\}^{n-1}$, $H$ returns $(0,x)$. For any other input $y$, $H$ returns $(1,H'(y))$. Show how to construct an adversary that inverts $H$ with probability $1/4$, but is useless for finding collisions (namely, when it inverts $H(x)$ it always returns $x$ itself). (Note that in this case what you are asked to show trivially holds because $\epsilon-2^{-s} = -1/4 <0$.) Now, find yourself the bug in your proof.

guybr, where were you wrong? im having the same mistake ):

and to nir, if i define A(0x)=00x; A(1y)=~random n+1 long string~ does A not invert H with probability > 1/2?

half of {0,1}^n are of the form 0x and A inverts them properly…

$A$ gets $H(z)$ for a uniform $z\in \{0,1\}^{n+1}$. In any case, $A$ never finds a collision, when it inverts $H(z)$, it necessarily returns $z$ itself. BTW, you are expected to individually solve the exercise (with at most one partner), in particular, you should figure out on your own where you are wrong.