Skip to main content
2 of 3
inserted length requirement
user avatar
user avatar

One can't "get rid of" the factor 2.
However, there might be a way to replace it with $\:2\hspace{-0.03 in}-\hspace{-0.03 in}o(1)\:$ where that depends on $q$ and the advantage.

$||$ is concatenation.
Start with some encryption scheme $\mathcal{E}'\hspace{-0.04 in}$, and for any integer $n$ and probability $p$, let $\mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.02 in}$ be given by
$\;\;\;\;\;\;\;$ if $m$ has no ones and at least $n$ zeros then with probability $p$, $\;\;\; \mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.03 in}(m) \: = \: 00\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$
$\;\;\;\;\;\;\;$ else if $m$ has no zeros and at least $n$ ones then with probability $p$, $\;\;\; \mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.02 in}(m) \: = \: 1\hspace{-0.03 in}1\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$
$\;\;\;\;\;\;\;$ else $\;\;\; \mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.02 in}(m) \: = \: 0\hspace{-0.02 in}1\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$
.

(Decryption just removes the first two bits and then applies $\mathcal{D}\hspace{.02 in}'$.)

user991