Ask questions about the lecture.
אפשר לקבל הסבר מדוע המוד
OFB
הוא סינכרוני בעוד שהמוד
CBC
הוא לא סינכרוני ?
Consider a situation where an unknown number of ciphertext blocks are lost on their way to the receiver, and then communication is restored such that all subsequent ciphertext blocks are received. In the CBC mode, the state is the last ciphertext block. If the ciphertext blocks $C_i, C_{i+1}$ are received correctly, plaintext block $P_{i+1}$ can
be correctly recovered. Therefore CBC is self synchronizing.
By way of contrast, if an unknown number of ciphertext blocks are lost in the OFB mode, the receiver has no way of
recovering from this failure. Therefore OFB is synchronous.
האם יש אפשרות לקבל קישור אל דוגמאות ההרצה הרבות של סייג' שהיו בשיעור?
אני מודע לכך שיש כמה במצגות, אך המגוון בדוגמאות בשיעור היה רחב ונראה מאוד מועיל.
Regarding Yao's garbled circuit,
האם ההצעה הבאה להתמודד עם
malicious bob
תעבוד ?
בשער האחרון שהוא בעצם הפלט של הפונקציה שאנו רוצים לחשב, במקום שאליס תצפין את הביט 0 או 1, היא יכולה להגריל באקראי 2 מחרוזות
u,v
ולהצפין את 0 יחד עם v
ולהצפין את 1 יחד עם u.
עכשיו במקום שבוב ישלח לאליס את תוצאת החישוב כביט יחיד הוא יהיה חייב לשלוח גם את המחרוזת המתאימה.
ועוד שאלה בקשר לעמוד האחרון במצגת היום:
למה הפונקציה h
מופעלת על האיברים
0,..,n
בניגוד לפונקציה f ?
בנוסף, ישנם רק n
ערכים של הפונקציה f
אבל n+1
ערכים של הפונקציה h.
Hi,
First, I wish to apologize for not noticing your question earlier, and consequently taking so long to respond.
If the parties are really malicious, they can deviate from the protocol in ways that will bypass your nice construction.
For example, suppose the goal is to compute $x \oplus y$, where x and y are bits. I am the bad guy, and I really do not
want to see the outcome 0 (it causes me to lose some huge wager). So I perform the computation, not knowing the other
side's bit. But once I realize the outcome is 0, I just quit. What would the other side do? S/he not necessarily knows my
preferences, and why I quit.
In general, it is hard to deal with such behavior (and possibly worse ones) unless the good guys are in a real majority. And
then we want to commit to inputs in a way that will later enable the good guys to reconstruct them if the bad guys quit, and
will also not let the bad guys change their mind, etc. etc. One has to use zero knowledge, heavy polynomial tricks for dealing
with reconstructing secrets, possibly Byzantine agreement, etc. All of this is out of the scope in our course.
As to h and f - these are typos, which I will soon fix.
Benny
In lecture 7 slide 52 it says that QNR*QNR = QR.
I tried a small example with q= 3, p = 5
and multiplied 2*7 = 14 which is not QR.
Am i doing something wrong?
Hi,
In the last assignment (#4) you wrote that "Oblivious transfer is not privately computable if the parties are computationally unbounded" and that you've mentioned it in class (can't recall that moment..:) ). While this is clearly true for the constructions of OT we've seen in class (which relied on computation assumptions) I don't understand why this is true for the general OT problem.
Does the statement mentioned above should be trivial from the definition of OT? or there is some theorem somewhere which proves it (if there is can you please attach a reference?)?
Thanks,
Yehonatan
The statement claiming that 1-out-of-2 OT is not privately computable in the computationally unbounded model is not trivial, but is not too difficult to prove either. Consider, for example, the function $F_2(x,y)$ from assignment 4. Suppose the sender (who holds pairs $(s_0,s_1)$) is the one to send the first message in the protocol. It must send the same distribution of messages on $(s_0,s_1)=(0,1)$ and $(s_0,s_1)=(0,2)$, for otherwise if the receiver bit is 0 (so the outcome is 0 in these cases), the receiver will learn something about the input $s_1$, which is supposed not to happen. Likewise if $(s_0,s_1)=(0,1)$ and $(s_0,s_1)=(2,1)$, etc. (this is the relation $\sim$ on rows, alluded to in the lecture and in a previous message in the forum - regarding assignment 4, I believe). At the end of the day, sender must send the very same first message, regardless of its input. Now receiver must also do the same, regardless of having b=0 or b=1, by the definition of 1-out-of-2 OT. This goes on and on and in any finite number of communication rounds they will not be able to come up with a communication that will let receiver get $s_b$.
Regarding "The magic square in Zpq" (Lecture 7, slide 38)
It seems incomplete so I wanted to know some more details
If X is in QRpq then X is in QRp and also in QRq? (And vice versa?)
Or are there other cases when X is in QRpq?
Indeed, x is a quadratic residue mod pq iff
x is a quadratic residue mod p and x is a quadratic residue mod q.
In lecture 6 page 37,
what is the reason that $x^{(p-1)(q-1)} = 1 \ \ (mod \ pq)$ ?
The line should read
So for every $x\in Z_{pq}^* , x^{(p-1)\!\cdot\!(q-1)}=1 \pmod {pq}$
(the first x was missing).
This follows from the fact that $Z_{pq}^*$ has (p-1)(q-1) elements, it is a group wrt multiplication modulo pq, and that every group element raised to a power which is the group order, yields the group identity element (1 here).
בנוגע למבחן משנת 2002 שנשלח לנו במייל:
לא ברור לי מה אני אמור לדעת על
AES
בעקרון, ממה שאני זוכר וכתוב לי במחברת, עברנו על ה
DES
באופן מעמיק יותר.
ואילו על כל החומר שרשום במצגת בנוגע ל
AES
ובפרט במפתח שמסודר כמטריצה וסידורי שורות לא נגענו
הדבר היחיד שאני יודע שהוא קונקרטי אולי לשאלה על
DES and AES
, זה שהם אמורים להיות מימושים שמחקים יצירה של פרמוטציה פסאודו אקראית כאשר ההצפנה היא פר בלוק
(האם זה בהכרח פרמוטציה, גם במקרה של
AES)
האם אני ממש רחוק מהאמת?
אם כן- אשמח לדעת מה עוד צריך לדעת בנושא .
אם לא- האם הידע הזה מספיק לפתרון השאלה?
תודה רבה.
DES and AES both are permutations when the key is fixed (for sure) and we believe they are pseudo random permutations when the key is fixed but not known.
We talked a bit about inner structure of AES, and a bit more about inner structure of DES. For example, both are arranged in rounds, where
each round by itself is fairly weak, but after cascading them for multiple rounds, the result seem hard to break.