Recent Forum Posts
From categories:
page »
A solution for Moed B by nbitanskynbitansky, 21 Feb 2014 21:08

1) if we knew the factors of m-1 then we could check if a given g is a p.r by raising it to the (m-1)/2 power and seeing it is -1… but this only suffices to show g is a p.r if we already knew that m is prime… so youre right, it's a problem and im not sure what to do here…

2)for calculating the integer k-th root of n (if exists).. you get a real number which is very close to an integer s and you know the k for which you are calculating the k-th root, then just raise s to the power of k and see that youre getting n… anyway in the procedure above we needed -not- to get an integer so in the numerical method beacuse we know the precision parameter delta i.e how at most far we are from the real root, if we see there is no integer at distance delta from what we have numerically calculated then we know there is no k-th root…

by daniel (guest), 19 Feb 2014 15:06

fix the link, guests are not allowed to post links.

by asdf (guest), 19 Feb 2014 13:12

I think that your idea is not fully right:

1. I don't see how one can verify whether an element, g, is a primitive element. I think that is why we were always told to select p=2q+1 (when both q,p are prime), this way it is easy to find an element whose order is 2 and another one whose order is q (by guessing and simple test) and then multiply them to get an order of 2q.
2. I didn't take Numerical Analysis. In the short google-ing I did I could only find algorithms for n-th root which depends on a precision parameter. So event if we knew that m is a power of a prime, I'm not sure it is that easy to find the root in a deterministic manner - I might be wrong because, as I said, I'm not familiar with Numerical methods.
3. I found this
lecture17.pdf which solves the problem.

Please comment if you know something I don't regarding 1 and 2.
Thank you for your time!

by asdf (guest), 19 Feb 2014 13:11

למה בסעיף ג' הסיכוי לכך ש- a_i שונה מ- 'a_i הוא 1 חלקי k?

שאלה 1 ג' בפתרון של מועד א' by עידן נוריק (guest), 19 Feb 2014 11:48

my idea:
given m, a primitive root g modulo m will show that m is a power of a prime… verifying that g is a primitive root is O(log^3(m)) (i think.. it's polynomial in size of input, anyway).
now that we know m is a power of a prime, we want to know that the power is 1. if the power is k, and m=p^k, then we know that p>2 and that k<log_p(m)<log_2(m). so we check (using efficient computations done in the reals) for each k from 2 to log_m if the k-th root of m is an integer. this is O(size of representation of m) steps and each step is done efficiently so i think the whole procedure is eventualy done in Poly time.

and we needed g as a witness…

by daniel (guest), 19 Feb 2014 10:57

You wrote it in lecture 6 slide 13. I can't find out why, besides the test that has shown it to be in P.

Determining if m is prime turns out to be in NP by asdf (guest), 19 Feb 2014 07:54
asdf (guest) 19 Feb 2014 07:52
in discussion Forum / Course Forum, Fall 2013/2014 » primitive elements in GF*(p^k)

I also wondered about this. I think they wrote it because it is trivial that 1 is not a generator.

by asdf (guest), 19 Feb 2014 07:52

אוקיי נראה לי שהבנתי לבד… פשוט בתרגול הצפנו ביט אחד ובכל שאר ההקשרים מצפינים הודעה שהיא איבר כלשהוא בחבורה…

by daniel (guest), 18 Feb 2014 10:30

הייתי שואל את זה בשעת קבלה אבל השאלה הזאת די משגעת אותי… בכל מקום (הרצאה, ספר, ויקיפדיה..) למעט בתרגול, נאמר לנו שצופן אל-גמאל בטוח אם הוא מתבצע בחבורה שקשה לחשב בה לוגריתם דיסקרטי.

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

אפשר הסבר שיסדר את זה? תודה (:

שאלה בקשר לבטיחות של אל-גמאל by daniel (guest), 17 Feb 2014 12:16

אפשר לקבוע אחת כזאת?


in lecture 6 slide 7 it says that for p>2 it's easy to find p-2 elements in GF*(p^k) that are not primitive.
did you mean the elements which correspond to degree 0 polynomials (constants…) which are not 0? if so, why write p-2 and not p-1?

thank you.

primitive elements in GF*(p^k) by daniel (guest), 16 Feb 2014 19:25
daniel (guest) 15 Feb 2014 18:48
in discussion Forum / Course Forum, Fall 2013/2014 » PRGs

אוקיי, כך גם אני חשבתי, תודה (:

ד"א, גם אם היה אפשר להשתמש בCPA,
איך אפשר לנצל זאת בשביל להבדיל בין פלט של פי' לבין מחרוזת אקראית?
הרי 2 חצאי הפלט מתפלגים (מבחינת מבחין מוגבל חישובית) אחיד ו2 החצאים גם ב"ת…

by daniel (guest), 15 Feb 2014 18:48
nbitansky (guest) 15 Feb 2014 17:10
in discussion Forum / Course Forum, Fall 2013/2014 » PRGs

I assume that $P$ is a PRG itself?
If so, then your construction does meet the requirements of a PRG. The attack model we defined only says that it is impossible to efficiently distinguish between a random string and a pseudo-random string (there are no CPA attacks in this model).

by nbitansky (guest), 15 Feb 2014 17:10
daniel (guest) 15 Feb 2014 16:32
in discussion Forum / Course Forum, Fall 2013/2014 » PRGs

שלום, בתרגיל 1 שאלה 6 סעיף ב הצענו את המחולל הפסאודו אקראי הבא:

כאשר P הוא מחולל פסאודו אקראי אחר.

נאמר לנו שזה אינו מחולל פסאודואקראי חוקי, ושתחת מתקפת
chosen plaintext attack
אפשר להבדיל בהסתברות גבוהה בינה ובין מחרוזת חלקה.

אפשר בבקשה הסבר על למה זה נכון?

PRGs by daniel (guest), 15 Feb 2014 16:32
ציון מגן
דרורית (guest) 29 Jan 2014 07:02
in discussion Forum / Course Forum, Fall 2013/2014 » ציון מגן

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


ציון מגן by דרורית (guest), 29 Jan 2014 07:02

Yes, we stressed several times that for this application one must use a deterministic eval (note that here there are no privacy issues, we don't care about hiding $f$, so this is ok).

by nbitanskynbitansky, 20 Jan 2014 17:38
page »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License