Ask questions re assignment 1.

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

בקשר לשאלה 5:

אנחנו לא יודעים מראש את איברי החבורה,

האם אנו צריכים לבדוק לכל איבר ב

Zm

האם הוא זר ל

m ?

אם כן אז איך ?

You are right. (Think what happens when you run the generator test suggested for a residue that is not co-prime with $m$.)

In general, testing whether two numbers are co-prime is done using gcd algorithm you saw in class. Another way to check if a number $a$ is co-prime with $m$ is to check whether $a^{\Phi(m)}=1 \mod m$ (try to think why this is true). The latter method is only applicable when you know $\Phi(m)$, which as you saw in class is easy to compute when you know the prime factorization of $m$.

In question 4:

Does A run in polynomial time ?

How does A behave on inputs that don't belong to the image of the PRG ?

What are we required to show about the relationship between s and delta ? What does it mean "meaningful" ?

If you'd like, for concreteness, you can assume that $A$ runs in polynomial time. More generally, you can show $A'$ whose running time is the same as that of $A$ plus some polynomial.

You have no guarantee on the behavior of A except what is given in the question (i.e. that it inverts w.p. $\delta$)

Well meaningful was left for your liberal interpretation meant to make you understand why item (a) is not enough. Anyhow, let's say for concreteness, that meaningful means that $\epsilon \geq \delta/2$.

בשאלה 4 האם ניתן להניח כי התמונה של ה

PRG

היא בגודל 2 בחזקת n ?

(שזה שקול לכך שהפונקציה חח"ע)

שאלה 3 סעיף a

לא נראה לי שהסעיף הזה נכון. למשל

Take D0 be constantly 1

Take D1 distributed like U1

Take A be the identity function

Take epsilon = 0.25

ורק אחד מהא"ש מתקיים.

יכול להיות שבא"ש השני פונקציית ההסתברות צריכה להיות גם גדולה או שווה ל

(1 - epsilon) / 2

?

You are absolutely right, thanks!

The more intuitive (but equivalent) way to state the claim is:

$D_0,D_1$ are $\epsilon$-indistinguishable **for any** (polytime, respectively unbounded) $A$ iff **for any** (polytime, respectively unbounded) $A$, it holds that $\underset{b\gets\{0,1\},d\gets D_b}{\Pr}[A(d)=b]\leq \frac{1+\epsilon}{2}$ (in the problem set, we forgot to put the quantifiers).

What is the difference between $\mathbb{Z}_p$ and $\mathbb{Z}_p^*$?

For any integer $m$ (including a prime $m=p$), $\mathbb{Z}_m$ is the group of residues modulo $m$, $\{0,1,\dots,m-1\}$, with the $+_{\mod m}$ operation.

$\mathbb{Z}_m$ is the group of residues modulo $m$ that are co-prime to $m$, with the $\cdot_{\mod m}$ operation. For a prime $m=p$, the group thus consists of $\{1,2,\dots,p-1\}$.

Question 2:

Does "have the same distribution" mean the encryptions are distributed uniformly? Or the same as M's distribution in Zp? and can I assume M is distributed uniformly?

The message M need not be uniformly distributed.

A, B having the same distribution is **not** the same as both of them being uniform.

in question 5(b), is there a more efficient (time and memory) way of checking if an element is a generator besides generating a set of all its powers and checking its size is m-1?

because I tried it this way, and just one iteration drained my laptop's memory and took quite a while (it didn't finish, and even if it did, I wouldn't have time for 100000 until next week's due date)

thanks

Read again the intro to problem 5, there's an efficient algorithm to test whether an element is a generator.

About question 4:

If I solved (b), can I drop (a) ? Obviously the algorithm I gave in (b) fullfills the requirements declared in (a). Also the question about the relation between s and delta is not cleat to me, since a PRG is a OWF even if s==1 ….

Yes, if you want you can drop item (a). The question on the relation between $s$ and $\delta$ is re item (a) and is meant for understanding why it's not satisfactory (e.g. if $s=1$, the bound in 4.a could be meaningless).

שאלה 3.

אני קצת נאבק עם המושגים הבסיסיים:

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

סעיף ב שאלה 3

יש שמה שתי שאלות לגבי חוסר ההבחנה בין שתי ההתפלגויות, האחת בהבדל של שתיים במינוס אן, והשנייה בהבדל אחד חלקי עשר.

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

האם העובדה שהסתברותית הן לא ניתנות להבחנה במידת אפסילון גוררת בהכרח שהן לא ניתנות להבחנה בעזרת אף אלגוריתם במידת אפסילון?

אני נאבק פה גם עם חוסר השימוש באנגלית, מקווה שהייתי ברור

תודה

1. The question is in place, we should have been more explicit about it. You can assume if you want that $A$ is deterministic. (Although the claim is also true for a probabilistic $A$, where the probability is also over $A$'s coins)

2. Yes if two distributions are $\epsilon$-indistinguishable, they are of course $\epsilon'$- indistinguishable for any $\epsilon'>\epsilon$. Yes statistical indisitnguishability implies computational indistinguishability. (it's important that you understand why both of the above are true, it follows directly from the definitions)

5.b

assum we sample a number from 1 to 2^61-2, for example n= 2^60.

if we try to calculate square(n), we suppose to get 2^120 but as much as i know we are limited to 64 bits calculations.

how we should handle such cases?

thanks

It will certainly be easier to use a programming language that supports integers of unbounded size. Both Python and Scheme

do that, and everyone who took the intro CS course at TAU was familiar with one of these two languages at some point. In addition, the code for **modular exponentiation** in Python appears in the text of the homework.

Finally, Sage supports integers of unbounded size, and examples of using Sage can be found in the presentations of the last

two lectures.

Hi,

Would it be possible to upload the assignments' grades to this website?

It will make it easier for us to monitor our grades this way.

Thanks!