Unable to get n_bits to work

[GaurangTandon]

Hi, I run this command, which is similar to what's given in the readme:

python scripts/run_election.py --master_lookup data/san_francisco_nov_2016_master_lookup.txt --ballot_image data/san_francisco_nov_2016_ballot_image.txt --n_bits 16 --seats 2 --debug

And get this error:

Number of invalid votes = 210,593
Number of valid votes = 392,257
Number of voters = 192,416
100%|██████████████████████████████████████████████████████████████████████████████████████████| 31787/31787 [00:11<00:00, 2653.28it/s]
100%|██████████████████████████████████████████████████████████████████████████████████████████| 26667/26667 [00:04<00:00, 5489.52it/s]
100%|██████████████████████████████████████████████████████████████████████████████████████████| 41021/41021 [00:06<00:00, 6246.25it/s]
100%|██████████████████████████████████████████████████████████████████████████████████████████| 35349/35349 [00:09<00:00, 3854.97it/s]
100%|██████████████████████████████████████████████████████████████████████████████████████████| 32122/32122 [00:05<00:00, 5615.31it/s]
100%|██████████████████████████████████████████████████████████████████████████████████████████| 25470/25470 [00:06<00:00, 4106.13it/s]
100%|████████████████████████████████████████████████████████████████████████████████████████████████████| 6/6 [00:44<00:00,  7.42s/it]
Processing contest id = 9
Number of candidates = 12
Number of voters = 31,787
Round 0
Computing first preference tallies
Converting CandidateOrderBallots to FirstPreferenceBallots
  2%|██▎                                                                                          | 793/31787 [00:01<01:01, 503.92it/s]
multiprocessing.pool.RemoteTraceback: 
"""
Traceback (most recent call last):
  File "/usr/lib/python3.8/multiprocessing/pool.py", line 125, in worker
    result = (True, func(*args, **kwds))
  File "/home/gt/Downloads/shuffle-sum-master/shuffle_sum/ballots.py", line 130, in candidate_order_to_first_preference
    candidates = private_key_ring.decrypt_list(candidates)
  File "/home/gt/flask-venv/lib/python3.8/site-packages/damgard_jurik/crypto.py", line 355, in decrypt_list
    return [self.decrypt(c) for c in c_list]
  File "/home/gt/flask-venv/lib/python3.8/site-packages/damgard_jurik/crypto.py", line 355, in <listcomp>
    return [self.decrypt(c) for c in c_list]
  File "/home/gt/flask-venv/lib/python3.8/site-packages/damgard_jurik/crypto.py", line 344, in decrypt
    c_prime = damgard_jurik_reduce(c_prime, self.public_key.s, self.public_key.n)
  File "/home/gt/flask-venv/lib/python3.8/site-packages/damgard_jurik/utils.py", line 24, in func_wrapper
    return func(*[mpz(arg) if isinstance(arg, int) else arg for arg in args],
  File "/home/gt/flask-venv/lib/python3.8/site-packages/damgard_jurik/crypto.py", line 280, in damgard_jurik_reduce
    t_1 = L(a % n_pow(j + 1))
  File "/home/gt/flask-venv/lib/python3.8/site-packages/damgard_jurik/crypto.py", line 263, in L
    assert (b - 1) % n == 0
AssertionError
"""

The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "scripts/run_election.py", line 83, in <module>
    result = stv_tally(
  File "/home/gt/Downloads/shuffle-sum-master/shuffle_sum/protocols.py", line 199, in stv_tally
    fpb_ballots, tallies = compute_first_preference_tallies(cob_ballots, private_key_ring, public_key)
  File "/home/gt/Downloads/shuffle-sum-master/shuffle_sum/protocols.py", line 44, in compute_first_preference_tallies
    fpb_ballots = list(tqdm(pool.imap(cob_to_fpb, cob_ballots), total=len(cob_ballots)))
  File "/home/gt/flask-venv/lib/python3.8/site-packages/tqdm/std.py", line 1185, in __iter__
    for obj in iterable:
  File "/usr/lib/python3.8/multiprocessing/pool.py", line 868, in next
    raise value
AssertionError

The script runs fine when I do not specify the n_bits parameter. Could you please let me know what the intended value of that parameter is?

I could not find related documentation anywhere. Thanks for making this great work available online!

[nickboucher]

This is very interesting - thanks for sharing the issue!

The n_bits parameter is used to set the number of bits used in the public/private key that is generated. At first glance, I'm not sure why it's failing.

Does it also fail for other non-default values (perhaps larger than 16)?

[GaurangTandon]

Thanks, I tried with --n_bits 32 and surprisingly it worked! The elected candidates result for reference, although it should not be affected by n bits parameter: AHSHA SAFAI, KIM ALVARENGA

It failed with 20. It seems to be working for 26. Very strange indeed.

EDIT: 26 also failed but very late into the process run.

[nickboucher]

It's been a while since I've read through the Damgard-Jurik paper, but perhaps the number of bits must be a power of 2? Alternatively, perhaps we assumed that n_bits was a power of 2 somewhere in the code.

Given that 32 bits works, and the default of 64 bits works, there is at least some anecdotal evidence that this is the case.

I don't have the bandwidth to investigate this now, but if anyone sees this issue and can:

• Verify that n_bits only works for a power of 2
• Provide evidence for why this is the case

...I would be then be happy to review and accept a PR that either repairs any assumptions in the code or clearly documents any requirements.