Hash-Chained Append-Only Ledgers as a Lightweight Tamper-Evidence Primitive for Remote E-Voting: A Game-Based Security Analysis

Abstract

Abstract: Remote electronic voting systems require tamper-evident records of ballot submissions, yet the ledger integrity problem - ensuring that the record cannot be silently altered after the fact - has received less formal treatment than ballot-phase cryptography. Existing approaches rely on distributed blockchain consensus, digital signatures on bulletin boards, or external hash-tree timestamping services, each introducing dependencies on specialized infrastructure, continuously trusted parties, or computationally intensive proof systems. This paper provides a formal security analysis of a hash-chained append-only ledger instantiated in a standard relational database with quorum replication, establishing that equivalent tamper-evidence guarantees are achievable under the sole assumption of collision resistance of the instantiated hash function. We define five security properties in the Bellare-Rogaway game-based framework. Tamper-evidence (Proposition 1) bounds any PPT adversary's advantage at 2q(λ) · Adv^CR_H, with a tight reduction to collision resistance. Fork-resistance (Proposition 2) establishes that an adversary corrupting fewer than a quorum threshold of replicas cannot cause divergent chain histories at honest replicas. Retrospective modification resistance (Proposition 3) establishes that post-close modifications are detectable by any auditor holding a real-time replica copy. Cross-ledger binding security (Proposition 4) extends these results to the dual-ledger construction of the Arcaunt architecture, in which a public ballot ledger and a temporal credential ledger are cryptographically bound at insert time, making modifications to either detectable through the other with advantage bounded by 4q(λ) · Adv^CR_H. Selector integrity (Proposition 5) establishes that the last-valid-vote rule - operating on insertion sequence rather than timestamps, making it immune to clock manipulation - is integrity-secure conditional on credential security, formally delineating the boundary between ledger and credential security domains. We apply an eight-metric comparative framework to seven e-voting integrity architectures - hash-chaining, bulletin boards, homomorphic tallying, mixnet-based systems, blockchain, KSI timestamping, and VVPAT hybrids - establishing three findings: tamper-evidence basis is universal but mechanism-specific; fork-resistance is architecturally necessary specifically for revoting-based systems; and auditability complexity is inversely correlated with cryptographic sophistication. The hash-chained relational ledger achieves collision-resistance-based tamper-evidence with O(n) verification accessible to any SQL-capable auditor - a design point unoccupied by existing systems under the same combination of properties. Prototype validation on a Firebird 5.0 implementation confirms that each proposition is instantiated by a specific database trigger mechanism, with 6ms mean ballot submission latency and O(n) verification complexity empirically confirmed.