The nVotes voting system uses an ElGamal re-encryption mixnet to ensure ballot privacy. When using ElGamal encryption it is necessary to first encode protected data into the plaintext space where ElGamal operates in. Once encoded in this space, the information can be encrypted. When decrypting, the reverse process occurs; first the ciphertexts are decrypted, and then the plaintexts are decoded back into the original data.

The plaintext (and also ciphertext) space for semantically secure ElGamal is the multiplicative subgroup Gof the ring of integers Zp, where p is a safe prime modulus, p = 2q + 1. The standard procedure to encode data is to first convert into an integer (a universal data type that can hold any information), and then map that integer into Gq. The range of integers that can be encoded in a single ciphertext is given by the order q of Gq, so we’re looking for a procedure to map numbers from Zinto Gq. I recently looked for a reference for this simple procedure and found none that explains it well, so I’m writing it here.

Encoding with the Legendre symbol

One reference we can find is this from Advances in Cryptology – EUROCRYPT 2017.

First of all, when using a safe prime p = 2q + 1, the multiplicative subgroup Gis precisely the set of quadratic residues mod p, this is in fact what makes the scheme semantically secure as stated above. Given this, the above suggests the simple m x (m/p) as our encoding procedure. But why is (m/p) x m guaranteed to be a quadratic residue? The reference contains hints, which we expand below.

First of all, the legendre symbol is defined as

Because the range of input integers is q, which is always < p, then there are only two possibilities for encoding. The expression (m/p) x m reduces to leaving m unchanged (1 x m) or reversing its sign (-1 x m). In particular, if m is already a residue, then (m/p) x m is still a residue since (1 x m) = m.

Second, we have that

Third, the first supplement of the law of quadratic reciprocity states

since p is a prime, then p mod 4 has only two possible values (1 and 3), so

if p ≡ 3 (mod 4) then −1 is a nonresidue modulo p

Fourth, or modulus p is a safe prime p = 2q + 1, where q is also a prime. This means that

q = 1 mod 4 or q = 3 mod 4

Expanding each case[1]

q = 1 mod 4 ⇒ 2q = 2 mod 4 ⇒ 2q + 1 = 3 mod 4 ⇒ p = 3 mod 4

similarly

q = 3 mod 4 ⇒ 2q 4 = 6 mod 4 ⇒ 2q = 2 mod 4 ⇒ p = 3 mod 4

Therefore in both cases, for a safe prime p, we have that

p = 3 mod 4

Now we combine each of the previous 4 steps of the argument in reverse. By step 4 we have that:

p = 3 mod 4

which by step 3 implies that

-1 is a nonresidue modulo p

which by step 2 implies that

(-1 x m) is a residue if m is not a residue

which by step 1 implies that

(m/p) x m is a residue if m is not a residue

Also by step 1 we saw that

(m/p) x m = 1 x m is a residue if m is a residue

Therefore in all cases

(m/p) x m is a quadratic residue modulo p for a safe prime p = 2q + 1

which is what we set out to prove.

Example code, Helios and Univote

Let’s look at how this is implemented in two open source e-voting projects with ElGamal encryption, Helios by Ben Adida and UniVote by the Bern E-voting group. Because vote encryption takes place at the voting booth running in the browser the code is javascript. In Helios we can find the ElGamal encoding of integers in elgamal.js file, which is also included in the nVotes voting booth

The first line is a technicality, it adds 1 to the input because the subgroup Gdoes not include the value zero. The subsequent lines implement the (m/p) x m encoding. If you recall, the legendre symbol has two possible values 1 and -1. The first branch of the if statement leaves m unchanged, the (1 x m) case. The second branch corresponds to changing m’s sign, the (-1 x m) case. The expression in the if statement applies Euler’s criterion to calculate the legendre symbol

This shows that the javascript code is in effect calculating (m/p) * m. We can see a similar method in UniVote, the code is found here:

Again, we are adding 1, and then branching based on the Euler criterion. There is a small difference, whereas above the value (1 x m) was calculated, in this case we have the value p – m. But because modular congruence is compatible with subtraction[2], then

-m mod p = (0 – m) mod p = p – m mod p

So both expressions, -m and p – m are equivalent, mapping the input m to quadratic residue.

Example values

Here we show some concrete encoding examples for small p. Let’s first print the values in G5 for a choice of safe prime 11 = (2 x 5) + 1.

The quadratic residues are thus G5 = {1, 3, 4, 5, 9}. Now let’s see if the encoded in the allowed range q=5 actually map to residues.

where we can see that the encoded values are indeed in G5. Let’s run another test for p = (2 x 11) + 1

Again, the encoding works.

Summary

In this post we have seen how encrypting in ElGamal first requires encoding data into the correct subgroup, and how this can be done with the expression (m/p) x p in terms of the legendre symbol. We also saw why this works, using several properties of modular arithmetic. Two implementations with this technique were shown, in which the Euler criterion was used to determine residuosity. Finally we saw some real value examples of subgroups and encodings for small values of p and q.


[1] We are using two properties here

  • if a = b mod n, then k a = k b (mod n) for any integer k (compatibility with scaling)
  • if a = b mod n, a1 + a2 ≡ b1 + b2 (mod n) (compatibility with addition)

[2] Compatibility with subtraction,

  • if a1 = bmod n and a2 =  b2 mod n, then a1 – a2 = b1 – b2 (mod n) (compatibility with subtraction)