Transcript The Exact Multiplicative Complexity of Counting Votes

The exact multiplicative
complexity of counting votes.
René Peralta
Yale University
2004
Thanks to:
Michael Fischer
Joan Boyar
Ivan Damgaard…
Basic voting protocol
(referendum mode).
• registration authority
emits unforgeable and
untraceable ballots.
• voters cast sealed votes
into public bulletin board.
• counting program decides,
announces, and proves
outcome.
VOTES
OUTCOME?
• exact count.
• whether motion passes.
• something in between
…
It may be
desirable to
reveal no other
information.
• coercion.
• vote buying and selling.
Encrypted votes
Circuit computing a
function of votes
x4
x1
 
L
x3 x 4 x
x3
x2

5

L
x1
x4 x
x2

L
x2
5

Motion passes by
majority vote
x1

outcome of circuit
with encrypted
inputs is revealed
by a
discreet proof
(BDP)
The length of a discreet
proof is linear in the
number of (mod 2)
multiplications in the
circuit.
ADDITIONS are free!
Multiplicative
complexity.
any Boolean function can be
represented by a circuit using
only addition and multiplication
modulo 2.
Multiplicative complexity is the
number of multiplications
necessary and sufficient.
• (Shannon, Lupanov) : almost all
Boolean functions on n variables
have gate complexity about
2n n-1
(BPP 98):
Multiplicative complexity over
the basis ( , L , 1) is about
q (2n/2)
NOT MUCH ELSE
IS KNOWN!
We focus on concrete
multiplicative
complexity.
For symmetric functions of the
votes, computing the Hamming
weight is central to this problem.
RESULT
(Boyar, Peralta)
.
The multiplicative complexity of
computing the Hamming weight
of n bits is exactly
n – H(n)
e.g. if n = 37 = 100101 then the
optimal circuit contains 34
multiplications.