$\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)$?


1 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.

  • $\begingroup$ If the g0 and g1 are not picked at random what will happen $\endgroup$
    – aaaabel
    Dec 30, 2017 at 15:09
  • $\begingroup$ @aaaabel: if they're not picked at random, that won't hurt security. In addition, that's another way of avoiding multiple plausible decryptions, e.g. if $g_0^{2^k} = g_1$ (and the order of $g_0$ is at least $2^{2k}$), then decryption will always be unique. $\endgroup$
    – poncho
    Dec 30, 2017 at 17:32
  • $\begingroup$ Is it will cause some problems that may occur upon decryption if these generators are not picked at random. $\endgroup$
    – aaaabel
    Jan 1, 2018 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.