Changes for ElectionGuard Elliptic Curves

[JohnLCaron]

Sent message to Josh Benaloh and Michael Naehrig:

I need some advice on how to implement these two functions in the egk-ec library, namely testing if an ElementModP is "in bounds" and testing if it is a "valid residual":

/**
 * Normal computations should ensure that every [Element] is in the modular bounds defined by
 * the group, but deserialization of hostile inputs or buggy code might not preserve this
 * property, so it's valuable to have a way to check. This method allows anything in [0, N)
 * where N is the group modulus.
 */
fun inBounds(): Boolean

/**
 * Validates that this element is a quadratic residue, ie in Z_p^r.
 * "Z_p^r is the set of r-th-residues in Z∗p", see spec 2.0 p.9
 */
fun isValidResidue(): Boolean

In the standard electionguard Integer group, they are implemented as

override fun inBounds() = element >= BigInteger.ZERO && element < groupContext.p

override fun isValidResidue(): Boolean {
    val residue = this.element.modPow(groupContext.q, groupContext.p) == groupContext.ONE_MOD_P.element
    return inBounds() && residue
}

Im trying to figure out what the equivalent implementation is for the Elliptic Curve P-256 group.

[JohnLCaron]

Michael's response:

These two functions are there to ensure that whenever you work on a supposed group element, it is indeed in the correct group. If an attacker can force someone to compute an exponentiation using a secret exponent on an element that is not in the correct group (and might have a small order for example), this can leak information about the secret exponent.

For elliptic curves we need to show the same thing, namely that the element is in the correct group. First of all that means you need to check that it is actually on the correct curve. That means, you need to check that the elliptic curve point (x,y) satisfies the curve equation y^2 = x^3 + a*x + b, where a and b are the fixed curve parameters. Your code already has the function isPointOnCurve, which should do exactly that.

Now, if the elliptic curve is a prime-order curve such as the standard curves P256 or P384, then this is enough. You don’t have to do anything else. But if the curve has a cofactor, you also need to check that the exponentiation with q (the prime group order of the generator we’re using) gives the neutral element, i.e., the scalar multiplication [q]P = 0 gives the point at infinity.

John:

So the constants for P-256 are:

{
"name": "P-256",
"type": "EllipticCurve",
"protocolVersion": "v2.1.0",
"constants": {
  "a": "ffffffff00000001000000000000000000000000fffffffffffffffffffffffc",
  "b": "5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b",
  "primeModulus": "ffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
  "order": "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
  "g.x": "6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296",
  "g.y": "4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5",
  "h": "1"
}
}

I'm assuming that primeModulus is analogous to P, and order is analogous to Q, and that h is the cofactor (so that "the curve does not have a cofactor").

Then, for ElementModQ:

override fun inBounds() = element >= BigInteger.ZERO && element < group.vecGroup.order
and for ElementModP:

override fun isValidResidue(): Boolean {
  return inBounds() && group.vecGroup.isPointOnCurve(this.ec.x, this.ec.y)
}

For the rest of the code, ElementModQ and ElementModP are used exactly as before as with the integer group. For example, wherever the spec uses inBounds() or isValidResidue().

Does that seem right to you? Any other places you forsee a problem switching to Elliptic curves?

Michael:

It would make the most sense conceptually to treat the underlying finite field like ElementModP before. And then, yes, primeModulus is analogous to P. Definitely, order is analogous to Q and that has the same purpose in the context of the ElectionGuard functionality as before for the finite field group. The difference now is that group elements are not mod p elements, they are built on top of that. Elliptic curve points, i.e., pairs of elements modulo the primeModulus, are the group elements now and take the place of ElementModP as group elements.

I’m just now thinking that the check that a given (x,y) is on the curve should probably include the check that both x and y are proper elements modulo primeModulus. So, wherever inBounds() and isValidResidue() are used in the finite field version, you now will have to check that all three of x.inbounds(), y.inBounds(), and (x,y).isPointOnCurve() are valid.

[JohnLCaron]

Michael:

There’s another issue that just came to mind, and that is hashing to ElementModQ. We need this for all the challenge values in the NIZK proofs. For the finite field version of ElectionGuard, Q is so close to a power of 2 that we can just hash and take the result modulo Q. This is not good anymore for the elliptic curve values for Q. Simply reducing mod Q now introduces a bias and yields outputs that are not uniform random anymore. To do this properly, one needs to implement what is in Section 5 of RFC 9380: Hashing to Elliptic Curves (rfc-editor.org). This produces a larger output before it is reduced modulo Q. You’ll need that algorithms expand_message in 5.3 and hash_to_field in 5.2, which uses expand_message. Note that you only need to do this for m=1 (and then their q = their p) and count = 1.

[JohnLCaron]

ElementP.isValidResidual:
2.A, 3.A, 5.A, 6.A, 15.A,
and in decryption

ElementQ.inBounds:
2.B, 5.B*, 5.C, 6.B*, 6.C, 9.A, 11.A, 12.A, 14.A, 15.C*