How to find the decryption algorithm for this encryption scheme?

Question

$\mathrm{KGen}(\kappa)$: Let $(\mathcal G, g, q) \gets \mathrm{GenG}(\kappa)$ be a cyclic group of prime order $q$. Choose random generators $g_0, g_1 \gets_R \mathcal G$, random exponent $x \in_R \mathbb Z_q \setminus\{0\}$, compute $h = g^x$, return public key $pk = (\mathcal G, g, q, g_0, g_1, h)$ and private key $sk = x$.

$\mathrm{Enc}(pk, m)$: Parse the 2-bit $m$ into its bits $m_0m_1$. Choose random $r \in_R \mathbb Z_q$ and return $c = (c_1, c_2) = (g^r, g_0^{m_0}\cdot g_1^{m_1}\cdot h^r )$.

Given this key generation scheme and this encryption algorithm, how can I find the decryption algorithm $\mathrm{Dec}(sk,c)$?

Answer 1

How do decrypt? Lets do the easy part first:

Given the ciphertext $(a, b) = (g^r, g_0^{m_0} \cdot g_1^{m_1} \cdot h^r)$, with the private key, we can compute $a^{-x} b = g^{-rx} g_0^{m_0} g_1^{m_1} h^r = g_0^{m_0} g_1^{m_1}$

Now comes the tricky part, now that we know $g_0^{m_0} g_1^{m_1}$, how do we solve the discrete log problem to recover $m_0, m_1$?

Without making additional assumptions on the group $\mathcal G$, the best we can do (assuming that $m_0, m_1$ are known to be at most $k$ bits long) is a generic log algorithm that takes $O(2^k)$ time.

One way is to do this is to have precomputed the values $g_0^{-0}, g_0^{-1}, g_0^{-2}, ..., g_0^{-2^k+1}$ and $g_1^{0}, g_1^{1}, g_1^{2}, ..., g_1^{2^k-1}$, and for each $0 \le i < 2^k$, compute $g_0^{m_0} g_1^{m_1} \cdot g_0^{-i}$ and see if it matches any of the $g_1^j$ values; if so, then we have the decryption $m_0 = i$ and $m_1 = j$.

Of course, there is a possibility (given that $g_0, g_1$ was selected randomly) that the decryption might not be unique. This possibility can be checked at key generation time, and a different $g_0, g_1$ pair be selected.