שאלה 3 סעיף a
לא ברור מה הנתונים בסעיף זה. נתונות לנו
t+1
התפלגויות אבל יש לנו נתונים רק לגבי
D0
וגם Dt.
איפה הנתונים של שאר ההתפלגויות ?
ועוד שאלה: האם בנתון הראשון חסר ערך מוחלט ?
ועוד שאלה: מה אנחנו צריכים להראות ?
מה זאת האות E ?
There is no further information on $D_1,\dots,D_{t-1}$.
There are no missing absolute values.
$\mathbb{E}$ means expectation.
n בשאלה 1 סעיף א', האם אנחנו מניחים שההודעות הן מאורך מסויים
או שאיננו מניחים דבר על האורך של ההודעות?
תודה
$m\in \{0,1\}^*$, i.e, it could be of any length.
As we defined in class, $E$ gets as input the public key $pk$, the message $m$, and randomness $r$.
Note that the same attacker $A$ should work for an encryption of any $m\in\{0,1\}^*$, and of course that $m$ is not given by the encryption in the clear.
$E_{pk}(m)$ is indeed distributed over may possible ciphers. Remember that otherwise public-key encryption (for arbitrary plaintext distributions) is impossible even against computationally bounded adversaries.
In question 3 (b), what does Esk(mi)c mean? (more specifically, the c)
Thanks
Let's say that A ~= B means that the distributions A and B are epsilon computationally-indistinguishable (for a specific epsilon).
Is it true that if A ~= B and B ~= C then C ~= D ?
I had a mistake. I wanted to ask this:
Is it true that if A ~= B and B ~= C then A ~= C ?
בשאלה 3 סעיף ב', בשביל מה צריך את ההתפלגויות האלה אם בקלטים שהאלגוריתם יש ביט שונה מאלו שבהתפלגויות ?
וגם, בסעיף הזה אנחנו צריכים להוכיח שאי שיוויון שכולל הסתברויות הוא נכון, אז מה התוחלת קשורה בכלל ?
בשאלה 5 סעיף ב', האם האלגוריתם שאנו צריכים לבנות יכול לרוץ בזמן דומה לאלגוריתם A
אבל בתוחלת ?
בשאלה 5 סעיף ג', אם האלגוריתם יכול לקבל t
חתימות אז בפועל האלגוריתם משתמש ב t+1
זוגות של מפתחות. אז האם האלגוריתם שאנו צריכים לבנות יכול לשבור
( epsilon/(t+1) , 1 ) - existential-unforgeability of the underlying one-time scheme
לא הבנתי מה בדיוק צריך לעשות בשאלה 6.
האם מספיק להגריל 2 פולינומים עם מקדם חופשי שונה כמו שמתואר ואז לחשב את הקומבינציה הלינארית המבוקשת רק עבור 2 הפולינומים שהגרלנו ?
- Note that $D_0,D_t$ are exactly the distributions that the adversary distinguishes.
- Ok, so some very basic probability facts that you should be familiar with: (a) for any event $A$, $\Pr[A]=\Pr[I_A=1]=\mathbb{E}[I_A]$, where $I_A \in {0,1}$ is the indicator for the event $A$. (b) for any random variable $X$ on which $I_A$ may depend, $\Pr[A]=\mathbb{E}[I_A]=\mathbb{E}_X[\mathbb{E}[I_A|X]]=\mathbb{E}_X[\Pr[A|X]]$. (c) the expectation is linear $\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$.
- No need to talk about expectation, the worst-case time of $A'$ should be $O(Time(A))$. Note that $A'$ need not invert the OWF with probability $1$, but only $\epsilon/2n$.
- No. (Note that seeing $t$ signatures means seeing $t$ one-time signatures, under $t$ independently chosen keys. Hopefully, once you do the reduction it should become clear.)
- It's the same coefficients $b_1,b_2,b_3$ for every degree two polynomial $h$ (make sure you understand why).
האם באופן כללי במערכת חתימה האלגוריתם לייצור המפתחות סודי? האם יריבים יכולים להגריל מפתחות ולסמלץ תהליך חתימה?
In question 3b can we choose the two messages ** m , m' ** ?
There is no need to use anything specific about $m,m'$. You need to show that for any $m,m'$ if $A$ distinguishes an encryption of $m$ from an encryption of $m'$, then $A'$ (given $m,m'$ can distinguish an encryption of "1" from an encryption of "0".
Is there a mistake in question 2 ? Is there a chance that the public-key bit-encryption scheme that we need to construct is $2 \epsilon$-semantically-secure and not necessarily $\epsilon$-semantically-secure ?
In question 2:
What is the definition of $\epsilon$-hardcore-bit if the function $F$ depends on the public key $pk$ ?
Does it mean that for every key pair $(sk,pk)$, $B$ is $\epsilon$-hardcore-bit for the function $F_{pk}$ ?