Why is the discrete log problem easy when the exponent comes from a binomial distribution?

I read in http://epubs.surrey.ac.uk/7219/2/esorics06.pdf that in exponential El Gamal the discrete log problem for recovering $m$ from $g^m$ can be made tractable when $m$ is drawn from a binomial distribution. Why is this?

-

Here's the deal. The discrete log problem is feasible in the special case where the exponent is known to come from a small range of possibilities (e.g., the exponent is not too large).

Suppose we are given $y=g^m$, and we want to find $m$. Suppose moreover we know that $m$ is small: $0 \le m < 2^{30}$, say. Then it turns out it is easy to recover $m$, without too much computation time.

• One very simple approach is to simply try all possible values for $m$: we compute $g^0$, $g^1$, $g^2$, \dots, $g^{2^{30}-1}$ and see which one of them matches $y$. This will always find $m$, and it takes about $2^{30}$ computations. It's feasible, but not super-fast: a few hours of computation, maybe.

• A smarter approach is to use a square-root algorithm. It turns out there are ways to solve this problem with about $2^{15}$ computations. (Here $2^{15} = \sqrt{2^{30}}$, which is why this is known as a square-root method. If we knew $0 \le m < M$, then these methods would require about $\sqrt{M}$ computations.) This is eminently feasible, and very fast: perhaps a few minutes of computation.

There are several square-root methods that achieve this running time, including the baby-step giant-step algorithm (sometimes also known as Shanks' method) or Pollard's kangaroo algorithm (sometimes also known as Pollard's lambda method).

For more on efficient discrete log algorithms when the exponent is known to be chosen from a small range of possibilities, see Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset.

What does this have to do with your question? Well, suppose we know that the exponent $m$ was drawn from a Binomial$(2^{30},1/2)$ distribution. Then we know that $0 \le m \le 2^{30}$, so we $m$ comes from a small range of possibilities, and we can recover $m$ using the methods above. Thus, it's not that there is anything particularly special about the binomial distribution, except that the binomial distribution is known to be bounded, and if this bound is small enough, then that lets us apply the methods above.

This situation often comes up in electronic voting. Suppose there are $N$ different voters. Let me sketch an approach for secure electronic voting using homomorphic cryptography.

We're going to have each voter encrypt their vote and published the resulting ciphertext somewhere for all to see. Each voter's ballot will be encrypted as follows: for some particular candidate (say, Smith), we encrypt $m_i$ using a suitable public-key encryption scheme, where $m_i=0$ if the $i$th voter did not vote for Smith and $m_i=1$ if the $i$th voter did vote for Smith. A voter's encrypted ballot is the concatenation of all of these ciphertexts, one per candidate, but for now let's focus on the part for Smith. Each of the $N$ voters does this and publishes the resulting ciphertexts.

We choose a suitable homomorphic public-key encryption algorithm such that $E(m_1) \times E(m_2) = E(m_1 + m_2)$. One standard way to achieve this is by encrypting $g^{m_i}$ using El Gamal encryption, so $E(m_i) = (g^{r_i}, h^{r_i} g^{m_i})$, where $r_i$ is random and chosen by voter $i$. Each voter publishes their encrypted vote; thus, for voter $i$, $E(m_i)$ is published.

Since the encryption scheme is homomorphic, everyone is able to compute an encryption of $m_1+\dots+m_N$, using the relation $E(m_1+\cdots +m_N) = E(m_1) \times \cdots \times E(m_N)$. Notice that $m_1+\dots+m_N$ is a tally of the total number of voters who have voted for candidate Smith, which is what we want to recover; and we have a public copy of an encryption of this.

Let $m=m_1+\dots+m_N$, so we have $E(m)$ and we want to recover $m$ to complete the tabulation of the votes. During tabulation, the authorities (who have a copy of the private key, shared in threshold form) will use threshold El Gamal decryption to decrypt $E(m)$, which yields the value $g^m$. Finally the authorities need to recover $m$. Fortunately, they can do this by taking the discrete log of $g^m$. This is feasible since we know that $m$ is in the range $0 \le m \le N$, and the number $N$ of voters can't be too large (e.g., we won't have more than a billion voters), so the above methods can be applied to compute this discrete log in this particular case. I hope that makes sense.

-
I'd add that lookup tables are especially useful here too. You must be willing to use more space, but for small plaintext spaces, it is very feasible. –  mikeazo May 13 '13 at 20:57