Repository navigation
馃悶 Occasional test failures related to 0 nonces聽#708
Description
Activity
Negating zero
The issue with
negate_qis that inputtingZERO_MOD_Qshould result inZERO_MOD_Qas 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 (ingroup.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(andhashed_elgamal_encrypt) is that its input nonce needs to be from$[1, Q)$ while theNoncessequences that pass into it (in, e.g.,encrypt_selectionandencrypt_contestfromencrypt.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 forhashed_elgamal_encryptaround line 392) could filter out zero nonce selections in tandem with the change suggested in 馃悶 Incorrect generation of nonces for encryption of ballot selections聽#655. - Another solution could be to change the
Noncesclass 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.
Reacted by Shreyas Minocha- A fix (in
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.pyaltogether. 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.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.Yes, Hypothesis testing uses
elements_mod_q_no_zero(see line 29 ofelectionguard_tools/strategies/group.py). Having the decryption mediator property test use this too would prevent this testing error.
Is there an existing issue for this?
Current Behavior
Tests in
tests/unit/test_decrypt_with_shares.pyandtests/property/test_decryption_mediator.pyoccasionally fail, either inelgamal_encryptfromelgamal.py("ElGamal encryption requires a non-zero nonce") or ingroup.py, where negating a zero nonce during proof construction results in a value that's too large for the group.Log 1
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
> 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.
Environment
No response
Anything else?
I thought this might have something to do with #656 and the fact that the generators in
election_factory.pyset some sequence orders to zero, but that doesn't seem to fix it. Maybe it's related to #655?