Score:2

An exercise from a textbook

eg flag

Let $\varepsilon>0$ be a constant. Say an encryption scheme is $\varepsilon$-perfectly secret if for every adversary $\mathcal{A}$ it holds that $$ \operatorname{Pr}\left[\operatorname{PrivK}_{\mathcal{A}, \Pi}^{\mathrm{eav}}=1\right] \leq \frac{1}{2}+\varepsilon $$ Consider a variant of the one-time pad where $\mathcal{M}=\{0,1\}^{\ell}$ and the key is chosen uniformly from an arbitrary set $\mathcal{K} \subseteq\{0,1\}^{\ell}$ with $|\mathcal{K}|=(1-\varepsilon) \cdot 2^{\ell} ;$ encryption and decryption are otherwise the same. (a) Prove that this scheme is $\varepsilon$-perfectly secret. (b) Prove that this scheme is $\left(\frac{\varepsilon}{2(1-\varepsilon)}\right)$-perfectly secret when $\varepsilon \leq 1 / 2$ (c) Prove that any deterministic scheme that is $\varepsilon$-perfectly secret must have $|\mathcal{K}| \geq(1-2 \varepsilon) \cdot|\mathcal{M}| $

This is an exercise from Introduction to Modern Cryptography that I'm studying I already found Proving that a scheme is $\epsilon$-perfectly secret but I need to understand this in detail, Is there anyone who can explain it to me?

us flag
Welcome to crypto.stackexchange. What exactly don't you understand? How much of it do you understand? Can you be more specific?
Maarten Bodewes avatar
in flag
Could you also please [edit] your question title to be more specific? "An exercise from a textbook" is both too generic, and it might also let people conclude that you're just copy / pasting an exercise (and, to be honest, I cannot fully dismiss that yet).
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.