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 G_{q }of the ring of integers Z_{p}, 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 G_{q}. The range of integers that can be encoded in a single ciphertext is given by the order q of G_{q}, so we’re looking for a procedure to map numbers from Z_{q }into G_{q}. 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 G_{q }is 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

1 2 3 4 5 6 7 | var y = m.add(BigInt.ONE); var test = y.modPow(pk.q, pk.p); if (test.equals(BigInt.ONE)) { this.m = y; } else { this.m = y.negate().mod(pk.p); } |

The first line is a technicality, it adds 1 to the input because the subgroup G_{q }does 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:

1 2 3 4 5 6 7 8 9 | var one = leemon.str2bigInt("1", 2, 1); var t1 = leemon.add(bigIntInZq, one); var t2 = leemon.powMod(t1, encryptionSetting.q, encryptionSetting.p); if (leemon.equals(t2, one) == 1) { return t1; } else { return leemon.sub(encryptionSetting.p, t1); } |

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 G_{5} for a choice of safe prime 11 = (2 x 5) + 1.

The quadratic residues are thus G_{5 }= {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 G_{5}. 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, a*_{1}+*a*_{2}≡*b*_{1}+*b*_{2}(mod*n*) (compatibility with addition)

[2] Compatibility with subtraction,

- if
*a*then_{1}= b_{1 }mod n and a_{2}= b_{2}mod n,*a*_{1}–*a*_{2}=*b*_{1}–*b*_{2}(mod*n*) (compatibility with subtraction)