in Computer Networks
147 views
0 votes
0 votes
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}| $
in Computer Networks
by
147 views

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
4