Voter registration systems are a critical - and surprisingly understudied - element of most high-stakes elections. Despite a history of targeting by adversaries, relatively little academic work has been done to increase visibility into how voter registration systems keep voters' data secure, accurate, and up to date. Enhancing transparency and verifiability could help election officials and the public detect and mitigate risks to this essential component of electoral processes worldwide. This work introduces cryptographic verifiability for voter registration systems. Based on consultation with diverse expert stakeholders that support elections systems, we precisely define the requirements for cryptographic verifiability in voter registration and systematize the practical challenges that must be overcome for near-term deployment. We then introduce VRLog, the first system to bring strong verifiability to voter registration. VRLog enables election officials to provide a transparent log that (1) allows voters to verify that their registration data has not been tampered with and (2) allows the public to monitor update patterns and database consistency. We also introduce VRLog$^x$, an enhancement to VRLog that offers cryptographic privacy to voter deduplication between jurisdictions - a common maintenance task currently performed in plaintext or using trusted third parties. Our designs rely on standard, efficient cryptographic primitives, and are backward compatible with existing voter registration systems. Finally, we provide an open-source implementation of VRLog and benchmarks to demonstrate that the system is practical - capable of running on low-cost commodity hardware and scaling to support databases the size of the largest U.S. state voter registration systems.