🐞 Occasional test failures related to `0` nonces

[shreyasminocha]

Is there an existing issue for this?

• [X] I have searched the existing issues

Current Behavior

Tests in tests/unit/test_decrypt_with_shares.py and tests/property/test_decryption_mediator.py occasionally fail, either in elgamal_encrypt from elgamal.py ("ElGamal encryption requires a non-zero nonce") or in group.py, where negating a zero nonce during proof construction results in a value that's too large for the group.

Log 1

tests/property/test_decryption_mediator.py:151: AssertionError
---------------------------------------------------------- Captured stdout call -----------------------------------------------------------
[388748:2022-07-15 14:12:37,483]:ERROR:elgamal.py.elgamal_encrypt:#L205: ElGamal encryption requires a non-zero nonce
------------------------------------------------------------ Captured log call ------------------------------------------------------------
ERROR    electionguard:logs.py:87 elgamal.py.elgamal_encrypt:#L205: ElGamal encryption requires a non-zero nonce

Log 2

tests/unit/test_decrypt_with_shares.py:140: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
src/electionguard/encrypt.py:124: in encrypt
    encrypted_ballot = encrypt_ballot(
src/electionguard/encrypt.py:480: in encrypt_ballot
    encrypted_contests = encrypt_ballot_contests(
src/electionguard/encrypt.py:538: in encrypt_ballot_contests
    encrypted_contest = encrypt_contest(
src/electionguard/encrypt.py:335: in encrypt_contest
    encrypted_selection = encrypt_selection(
src/electionguard/encrypt.py:231: in encrypt_selection
    encrypted_selection = make_ciphertext_ballot_selection(
src/electionguard/ballot.py:265: in make_ciphertext_ballot_selection
    proof = flatmap_optional(
src/electionguard/utils.py:118: in flatmap_optional
    return mapper(optional)
src/electionguard/ballot.py:267: in 
    lambda n: make_disjunctive_chaum_pedersen(
src/electionguard/chaum_pedersen.py:397: in make_disjunctive_chaum_pedersen
    return make_disjunctive_chaum_pedersen_one(message, r, k, q, seed)
src/electionguard/chaum_pedersen.py:465: in make_disjunctive_chaum_pedersen_one
    c0 = negate_q(w)
src/electionguard/group.py:179: in negate_q
    return ElementModQ(get_small_prime() - a)
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
cls = <class 'electionguard.group.ElementModQ'>, data = mpz(65521), check_within_bounds = True
def __new__(cls, data: Union[int, str], check_within_bounds: bool = True):  # type: ignore
    """Instantiate element mod T where element is an int or its hex representation."""
    element = super(BaseElement, cls).__new__(cls, data)
    if check_within_bounds:
        if not 0 <= element.value < cls.get_upper_bound():

>               raise OverflowError
E               OverflowError
src/electionguard/group.py:28: OverflowError

Expected Behavior

The tests consistently pass.

Steps To Reproduce

Running the tests in question a few hundred times is usually enough to trigger the error.

for i in (seq 1 200)
    poetry run pytest tests/unit/test_decrypt_with_shares.py
    if test $status -ne 0
        break
    end
end

for i in (seq 1 200)
    poetry run pytest tests/property/test_decryption_mediator.py
    if test $status -ne 0
        break
    end
end

Environment

No response

Anything else?

I thought this might have something to do with #656 and the fact that the generators in election_factory.py set some sequence orders to zero, but that doesn't seem to fix it. Maybe it's related to #655?

[eionblanc]

Negating zero

The issue with negate_q is that inputting ZERO_MOD_Q should result in ZERO_MOD_Q as the output, since $(Q - 0) \mod Q = 0 \neq Q$. Currently, it's returning the value of the small prime Q, which is out-of-bounds for an ElementModQ. A fix (in group.py, line 176) could be:

def negate_q(a: ElementModQorInt) -> ElementModQ:
    """Compute (Q - a) mod q."""
    a = _get_mpz(a)
    return ZERO_MOD_Q if a == 0 else ElementModQ(get_small_prime() - a)

Zero nonces

The issue with elgamal_encrypt (and hashed_elgamal_encrypt) is that its input nonce needs to be from $[1, Q)$ while the Nonces sequences that pass into it (in, e.g., encrypt_selection and encrypt_contest from encrypt.py) sample from $[0, Q)$. The likelihood of selecting such a zero nonce is greater in the tests since the value of $Q$ is smaller there than in practice.

There should be a check to ensure that if a zero nonce is obtained for these calls, nonces should continue to be sampled until a nonzero one is found.

• A fix (in encrypt.py, line 209 and similarly for the nonce argument for hashed_elgamal_encrypt around line 392) could filter out zero nonce selections in tandem with the change suggested in #655.
• Another solution could be to change the Nonces class overall to sample from $[1, Q)$ rather than from $[0, Q)$---this would be simple/universal. I'm not aware of any utility to possibly obtaining a zero nonce anyway or that the resulting change in probability distribution of nonces wouldn't be negligible.

[eionblanc]

update on zero nonces

I spoke with @benaloh about this yesterday. He favors a solution other than those I mentioned above: remove the "ElGamal encryption requires a non-zero nonce" flag from elgamal.py altogether. He expects this to warrant further discussion with @danwallach next month. I'll reiterate that this issue is certainly safe to wait until then since a zero nonce will "never" appear when $Q$ is as large as it is in non-test settings.

[danwallach]

For what it's worth, I agree that negate_q(0) should yield 0. That's what we do in the Kotlin and TypeScript codebases.

Josh is correct that zero will never occur by accident as a nonce. However, in property-based testing it will be almost guaranteed to happen, because the generators always try "corner case" inputs to make sure they work. So, you probably still want to use the elementsModQNoZero() or whatever it's called, when creating a nonce for testing purposes.

[eionblanc]

Yes, Hypothesis testing uses elements_mod_q_no_zero (see line 29 of electionguard_tools/strategies/group.py). Having the decryption mediator property test use this too would prevent this testing error.