Timeline for Proving semantic security implies security from key-recovery attack
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 24, 2022 at 11:06 | vote | accept | Tom Finet | ||
| Oct 24, 2022 at 9:07 | comment | added | seanL | Yes you are correct. The only part that i don't belive is 100% correct (maybe I am wrong here) is that when there exits a key. $A$ will suggest a correct key with probability $\text{KRadv}[\mathcal{A}, \mathcal{E}]$, but even if this is incorrect the proof is still the same. | |
| Oct 24, 2022 at 9:01 | comment | added | Tom Finet | no need to view my comments, I have posted my updated attempt in my question. | |
| Oct 24, 2022 at 8:26 | comment | added | Tom Finet | Hence $\text{SSadv}[\mathcal{B}, \mathcal{E}]=|\text{KRadv}[\mathcal{B}, \mathcal{E}]-\frac{|\mathcal{K}|}{|\mathcal{M}|}\text{KRadv}[\mathcal{B}, \mathcal{E}]|=\text{KRadv}[\mathcal{B}, \mathcal{E}]\cdot(1-\frac{|\mathcal{K}|}{|\mathcal{M}|})$, since $\mathcal{E}$ is semantically secure, we have a negligible $\text{SSadv}$ and so a negligible $\text{KRadv}$. I know my reasoning is a bit all over the place, but is this correct? | |
| Oct 24, 2022 at 8:23 | comment | added | Tom Finet | So with probability $|\mathcal{K}|/|\mathcal{M}|$ attacker $\mathcal{A}$ can play the game on $(m_1, c)$, and return the correct key with probability $\text{KRadv}[\mathcal{A}, \mathcal{E}]$, but with probability $1-|\mathcal{K}|/|\mathcal{M}|$ attacker $\mathcal{A}$ cannot play the game because no key exists which takes $c$ to $m_1$, so we have probability $0$ of finding a key in this case. | |
| Oct 24, 2022 at 8:17 | comment | added | Tom Finet | For $c=E(k, m_0)$, we have $|\mathcal{M}|-|\mathcal{K}|$ messages that cannot be decrypted from $c$, and thus cannot be encrypted to $c$. Picking $m_1$ uniformly at random, we have a $1-|\mathcal{K}|/|\mathcal{M}|$ probability that $m_1$ cannot be encryped to $c$, and hence a $|\mathcal{K}|/|\mathcal{M}|$ probability that it can be encrypted to $c$. | |
| Oct 24, 2022 at 8:06 | comment | added | Tom Finet | Fix $c$ as $c=E(k,m_0)$. If we had perfect security, then we would have a key for all $|\mathcal{M}|$ messages since we have a key for message $m_0$. But here we have $|\mathcal{K}|/|\mathcal{M}|<1$ keys per message, i.e. so some messages will not have a key taking it to $c$. | |
| Oct 24, 2022 at 7:34 | comment | added | Tom Finet | I think what you are saying is that even though $c=E(m_0, k)$ we can still have some keys $k'$ such that $E(m_1, k')=c$, and so attacker $\mathcal{A}$ can still play the key recovery game. Am I correct? | |
| S Oct 23, 2022 at 20:02 | history | suggested | Tom Finet | CC BY-SA 4.0 |
added latex
|
| Oct 23, 2022 at 20:00 | review | Suggested edits | |||
| S Oct 23, 2022 at 20:02 | |||||
| S Oct 23, 2022 at 19:58 | review | First answers | |||
| Oct 24, 2022 at 9:07 | |||||
| S Oct 23, 2022 at 19:58 | history | answered | seanL | CC BY-SA 4.0 |