University of Florida
Abstract
Transparency and security are essential in our voting system, and voting
machines. This paper describes an implementation of a stateless, transparent
voting machine (STVM). The STVM is a ballot marking device (BMD) that uses a
transparent, interactive printing interface where voters can verify their paper
ballots as they fill out the ballot. The transparent interface turns the paper
ballot into an interactive interface. In this architecture, stateless describes
the machine's boot sequence, where no information is stored or passed forward
between reboots. The machine does not have a hard drive. Instead, it boots and
runs from read-only media. This STVM design utilizes a Blu-ray Disc ROM (BD-R)
to boot the voting software. This system's statelessness and the transparent
interactive printing interface make this design the most secure BMD for voting.
Unlike other voting methods, this system incorporates high usability,
accessibility, and security for all voters. The STVM uses an open-source voting
system that has a universally designed interface, making the system accessible
for all voters independent of their ability or disability. This system can make
voting safer by simultaneously addressing the issue of voters noticing a vote
flip and making it difficult for a hack to persist or go unmitigated.
AI Insights - Malware tests showed the STVM cannot keep malicious code after reboot, blocking persistent attacks seen in other BMDs.
- A see‑through housing lets inspectors spot foreign parts instantly, raising tamper‑detection confidence.
- The paper lists vote‑flip attack vectors—software ballot re‑ordering and hardware key‑logging—to guide hardening.
- Prototype‑stage STVM already meets many auditability criteria used in risk‑limiting post‑election audits.
- Authors note gaps like limited field testing and side‑channel leakage, calling for deeper security analysis.
- Suggested reading includes “Security Analysis of Voting Systems” and “Designing Voting Machines for Verification” for deeper technical insight.
- The transparent interface turns a paper ballot into a dynamic, verifiable display, letting voters confirm each choice before printing.
Abstract
Much research in electoral control -- one of the most studied form of
electoral attacks, in which an entity running an election alters the structure
of that election to yield a preferred outcome -- has focused on giving decision
complexity results, e.g., membership in P, NP-completeness, or fixed-parameter
tractability. Approximation algorithms on the other hand have received little
attention in electoral control, despite their prevalence in the study of other
forms of electoral attacks, such as manipulation and bribery. Early work
established some preliminary results with respect to popular voting rules such
as plurality, approval, and Condorcet. In this paper, we establish for each of
the ``standard'' control problems under plurality, approval, and Condorcet,
whether they are approximable, and we prove our results in both the weighted
and unweighted voter settings. For each problem we study under either approval
or Condorcet, we show that any approximation algorithm we give is optimal,
unless P=NP. Our approximation algorithms leverage the fact that Covering
Integer Programs (CIPs) can be approximated within a factor of $O(\log n)$.
Under plurality, we give an $O(m)$-approximation algorithm, and give as lower
bound $\Omega(m^{1/4})$, by using a known lower bound on the Minimum $k$-Union
(M$k$U) problem. To our knowledge, this is the first application of M$k$U in
computational social choice. We also generalize our $O(m)$-approximation
algorithm to work with respect to an infinite family of voting rules using an
axiomatic approach. Our work closes a long list of open problems established 18
years ago.