PQKryvos: Post-Quantum Secure E-Voting With Flexible Ballot Formats and Public Tally-Hiding
Nicolas Huber (Paper author · University of Stuttgart), Ralf Küsters (Paper author · University of Stuttgart), Pascal Reisert (Paper author · University of Stuttgart)
Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 3 · Alpaca
Overview
In an era rapidly approaching the capabilities of quantum computing, the security of fundamental digital processes, including democratic elections, faces an existential threat. The talk "PQKryvos: Post-Quantum Secure E-Voting With Flexible Ballot Formats and Public Tally-Hiding," presented by Nicolas Huber, introduces a groundbreaking e-voting protocol designed to address this impending crisis. This work, a collaboration with Ralf Küsters and Pascal Reisert from the University of Stuttgart, represents the first post-quantum secure e-voting scheme that not only withstands the threat of quantum adversaries but also provides unprecedented flexibility in ballot formats and incorporates a crucial privacy feature: public tally-hiding.

Key moments
- 0:00 Introduction to PQKryvos: PQC, flexible ballots, tally-hiding
- 1:15 Why post-quantum security and arbitrary ballot formats matter
- 1:50 Explaining public tally-hiding and its privacy benefits
- 3:50 PQKryvos architecture: lattice commitments and R1CS SNARKs
- 5:45 Key innovation: bridging field mismatch for efficient proofs
- 6:30 Performance benchmarks: PQKryvos outperforms previous curve-based
- 7:50 Eliminating randomness aggregation overhead, unlike other protocols
PQKryvos: Post-Quantum Secure E-Voting With Flexible Ballot Formats and Public Tally-Hiding
Speakers: Nicolas Huber, Ralf Küsters, Pascal Reisert (Paper authors, University of Stuttgart)
Conference: PETS
YouTube: https://www.youtube.com/watch?v=p3zhlB8BNTw
Overview
In an era rapidly approaching the capabilities of quantum computing, the security of fundamental digital processes, including democratic elections, faces an existential threat. The talk "PQKryvos: Post-Quantum Secure E-Voting With Flexible Ballot Formats and Public Tally-Hiding," presented by Nicolas Huber, introduces a groundbreaking e-voting protocol designed to address this impending crisis. This work, a collaboration with Ralf Küsters and Pascal Reisert from the University of Stuttgart, represents the first post-quantum secure e-voting scheme that not only withstands the threat of quantum adversaries but also provides unprecedented flexibility in ballot formats and incorporates a crucial privacy feature: public tally-hiding.
PQKryvos tackles several critical limitations of existing e-voting systems. Most current cryptographic voting protocols rely on classical cryptographic assumptions, primarily elliptic curve cryptography (ECC), rendering them vulnerable to quantum attacks. Furthermore, these protocols often constrain elections to simplistic "one-person, one-vote" or single-choice scenarios, failing to accommodate the diverse and complex ballot formats found in real-world electoral systems, such as ranked-choice voting or independent candidate grading. Crucially, PQKryvos also integrates public tally-hiding, a mechanism that ensures only the final election outcome (e.g., the winner) is publicly revealed, rather than the full, detailed vote counts, thereby enhancing voter privacy without sacrificing verifiability.
The significance of PQKryvos lies in its holistic approach to e-voting security and practicality. By leveraging lattice-based assumptions and hash-based assumptions for its underlying cryptography, it provides robust post-quantum security. Its innovative design allows for arbitrary ballot formats and result functions, making it adaptable to a wide array of electoral procedures. The inclusion of public tally-hiding sets a new standard for privacy in verifiable e-voting. This protocol not only future-proofs e-voting against quantum threats but also makes secure, verifiable, and private digital elections a more realistic prospect for complex democratic processes worldwide.
Background
▶ Watch: Introduction to PQKryvos: PQC, flexible ballots, tally-hiding (0:00)
The concept of homomorphic e-voting forms the foundational premise for secure digital elections. In a typical homomorphic scheme, voters encrypt their ballots using a homomorphic encryption scheme. These encrypted votes (ciphertexts) can then be aggregated (e.g., added together) by election authorities without decryption. The resulting aggregated ciphertext, representing the sum of all votes, can then be decrypted to reveal the final tally. For instance, if candidates A and B are represented by vector encodings (e.g., [1,0] for A and [0,1] for B), voters encrypt their chosen vector. Adding these ciphertexts yields an encrypted sum like [2,1], which, upon decryption, reveals that candidate A received two votes and candidate B received one. This elegant approach allows for verifiable aggregation while maintaining individual voter privacy.
However, existing homomorphic e-voting protocols, while conceptually sound, suffer from significant limitations that PQKryvos aims to overcome. The most pressing issue is their reliance on classical cryptographic primitives, predominantly elliptic curve cryptography. ECC-based schemes are highly efficient today but are known to be vulnerable to attacks by sufficiently powerful quantum computers, rendering them insecure in a post-quantum world. This necessitates a shift to post-quantum cryptography (PQC), which is designed to resist both classical and quantum attacks.
Beyond quantum insecurity, many e-voting protocols struggle with flexibility in ballot formats. Traditional schemes often assume simple, categorical votes (e.g., choosing one candidate from a list). Real-world elections, however, employ a diverse range of methods, such as assigning grades to each candidate independently, ranked-choice voting, or multi-option ballots. Existing protocols are typically tailored to specific, often simplistic, formats, making them difficult to adapt to these complex scenarios. PQKryvos aims to support "arbitrary ballot formats," making it universally applicable.
A third significant challenge is the common practice of revealing the full election tally. While revealing the tally (e.g., Candidate A: 100 votes, Candidate B: 80 votes) can offer statistical insights, it also carries privacy risks. It might allow for inferring voter behavior, identifying small voting blocs, or compromising the privacy of voters in specific demographics. The goal of public tally-hiding is to address this by allowing external observers to verify the election's integrity while only revealing the final election result (e.g., "Candidate A won" or "Candidates X, Y, Z received high grades")—not the raw vote counts. This balances transparency with enhanced voter privacy.
PQKryvos builds upon a previously established framework called Kryvos. The original Kryvos framework, proposed a few years prior, introduced an alternative to homomorphic encryption: homomorphic commitments. In this approach, voters commit to their votes rather than encrypting them. These commitments are then aggregated, and zero-knowledge proofs (ZKPs) are used to demonstrate the correct computation of the election result from the aggregated commitments. The initial instantiation of Kryvos utilized Pedersen commitments and Groth16 SNARKs. While Groth16 SNARKs are highly versatile due to their compatibility with Rank-1 Constraint Systems (R1CS) and offer succinctness, they suffer from two critical drawbacks: they are not post-quantum secure, and they require a trusted setup, which is generally undesirable in security-sensitive applications like voting. PQKryvos specifically addresses these limitations by replacing the non-PQC components with post-quantum secure alternatives.
Key Findings
▶ Watch: Explaining public tally-hiding and its privacy benefits (1:50)
PQKryvos makes several pivotal contributions to the field of secure e-voting, fundamentally advancing its capabilities and resilience. The most significant finding is that it is the first post-quantum secure e-voting protocol designed to directly support arbitrary ballot formats and provide public tally-hiding. This combination addresses long-standing limitations in current e-voting systems, which are typically either quantum-vulnerable, inflexible in their ballot support, or reveal too much voter information.
The protocol achieves its post-quantum security by replacing the classical cryptographic components of the original Kryvos framework with primitives based on lattice-based assumptions and hash-based assumptions. Specifically, it integrates lattice-based commitments (constructed over a cyclotomic ring) and a post-quantum secure zero-knowledge proof system compatible with R1CS. This strategic replacement ensures that the entire e-voting process remains secure against attacks from future quantum computers, a critical requirement for long-term security.
A key technical breakthrough in PQKryvos lies in its efficient instantiation of these post-quantum components. The protocol successfully bridges a critical mismatch between the field requirements of lattice-based commitments and the fields typically used by R1CS-friendly zero-knowledge proof systems. This ingenious solution dramatically improves efficiency: proving the validity of a commitment to 250 values, a fundamental operation, was reduced from approximately 300,000 constraints and 181 seconds of proving time to just 30,000 constraints and 5 seconds of proving time. This represents a 36-fold speedup and makes the protocol even more efficient than the previous elliptic curve-based instantiation, demonstrating that post-quantum security does not necessarily come at a performance cost.
Furthermore, PQKryvos introduces an important advantage over other existing post-quantum e-voting protocols. Many such protocols rely on approximate zero-knowledge proofs for commitments, which can lead to a significant growth in the randomness associated with aggregated commitments. To maintain performance, these protocols often resort to "randomness reduction during aggregation," which introduces a "quite large overhead"—for instance, one reported a 31-minute overhead for specific operations. In contrast, PQKryvos utilizes exact proofs, effectively eliminating this "tally overhead" and ensuring consistent, efficient performance even as votes are aggregated. This distinction highlights PQKryvos's superior design in maintaining efficiency without compromising security or introducing practical bottlenecks.
Technical Deep Dive
▶ Watch: PQKryvos architecture: lattice commitments and R1CS SNARKs (3:50)
The core of PQKryvos lies in its innovative adaptation and instantiation of the existing Kryvos framework for post-quantum security. The original Kryvos framework operates on the principle of homomorphic commitments rather than homomorphic encryption. In this model, voters use a homomorphic commitment scheme to commit to their votes. These individual commitments are then aggregated to form a commitment to the election tally. Simultaneously, designated "carers" (or election authorities) aggregate their respective shares of the commitment openings to obtain an opening for the actual tally. To ensure integrity and verifiability, zero-knowledge proofs (ZKPs) are employed at two crucial stages: first, to prove that the committed values (votes) are valid, and second, to prove that the computed election result has been correctly derived from the election tally.
The original Kryvos framework used Pedersen commitments and Groth16 SNARKs. While Groth16 SNARKs are powerful, supporting arbitrary computations expressible as Rank-1 Constraint Systems (R1CS), they have two major drawbacks in a post-quantum context: they are based on elliptic curve cryptography, making them vulnerable to quantum attacks, and they require a trusted setup, which is a single point of failure and often undesirable in sensitive applications like elections.
PQKryvos addresses these limitations by replacing these components with their post-quantum secure counterparts. The protocol utilizes a post-quantum secure ZKP system that is also compatible with R1CS, ensuring generality for arbitrary ballot formats. Crucially, it replaces Pedersen commitments with lattice-based commitments. These commitments are constructed over a cyclotomic ring, where the commitment key n is defined. The commitment itself is computed using a small random value and a matrix-vector multiplication, exhibiting a "mostly linear structure." This linearity is highly advantageous in R1CS-based ZKPs, where linear operations are "essentially free," and multiplications of witness values are the primary cost (analogous to exponentiation in other systems).
The primary technical hurdle in integrating lattice-based commitments with R1CS-friendly ZKPs lies in a field mismatch. Lattice-based cryptography often requires specific algebraic fields (e.g., cyclotomic rings) to achieve its security properties, while common R1CS-friendly ZKP systems are optimized for different underlying fields (e.g., finite fields with specific characteristics). Without a careful bridge, proving the validity of a commitment within the ZKP system would be prohibitively expensive. This "mismatch" meant that simply instantiating a lattice commitment directly into an R1CS would result in an enormous number of constraints. The speaker highlighted this with a stark comparison: proving the validity of a commitment to 250 values would typically require around 300,000 constraints, leading to a proving time of approximately 181 seconds.
The core innovation of PQKryvos is its method for bridging this mismatch efficiently. While the specific details are reserved for the paper, this technique is described as "the key to an efficient solution." By intelligently structuring the proof, PQKryvos drastically reduces the complexity. After implementing this bridging technique, the same proof (validity of a commitment to 250 values) now requires only about 30,000 constraints and takes just 5 seconds to compute. This represents a remarkable 36-fold improvement in proving time and a 10-fold reduction in constraints. Furthermore, this optimized post-quantum instantiation is now more efficient than the original elliptic curve-based Kryvos instantiation, demonstrating that post-quantum security can be achieved with superior performance.
The talk presented benchmark results comparing PQKryvos (dashed lines) against the previous curve-based instantiation (solid lines). For a "majority election type" (where voters assign grades to each candidate), PQKryvos can prove the validity for hundreds of candidates in less than 2 seconds, whereas the previous version would take over 10 seconds. These benchmarks affirm the practical viability and superior performance of the new protocol.
Finally, PQKryvos offers a significant advantage regarding randomness management during aggregation. Other post-quantum e-voting protocols that use lattice commitments often rely on approximate proofs. In these schemes, the randomness used in commitments (computed as matrix * small_randomness) can accumulate and grow substantially during the aggregation of multiple commitments. To maintain acceptable performance, these protocols often need to "reduce randomness during aggregation," a process that can introduce a "quite large overhead." For example, one such protocol reported a 31-minute overhead for specific operations. PQKryvos circumvents this issue entirely by using exact proofs for its commitments, eliminating the need for randomness reduction and consequently avoiding any "tally overhead." This ensures consistent and efficient performance throughout the election process, from individual voting to final tally verification.
Demo / Proof of Concept
▶ Watch: Performance benchmarks: PQKryvos outperforms previous curve-based (6:30)
The talk primarily focused on the theoretical framework, cryptographic constructions, and performance benchmarks rather than a live demonstration of the PQKryvos system. The speaker referred to "detailed benchmarks" and the "paper" for further technical specifics and results, indicating that the presentation's emphasis was on the design and analytical validation of the protocol's efficiency and security properties. While no live demo was shown, the extensive performance comparisons against previous instantiations serve as a strong proof of concept for the protocol's practical viability.
Defensive Implications
▶ Watch: Eliminating randomness aggregation overhead, unlike other protocols (7:50)
The development of PQKryvos carries profound implications for defenders involved in securing electoral systems and critical infrastructure. As the threat of quantum computing looms, the immediate need to transition to post-quantum cryptography (PQC) is paramount. PQKryvos provides a concrete, high-performance blueprint for how e-voting can be future-proofed, offering a secure alternative to current quantum-vulnerable protocols. Defenders should prioritize research and adoption of PQC-enabled systems in any long-term e-voting strategy.
The protocol's ability to support arbitrary ballot formats is a game-changer for election administrators. Traditional e-voting systems often impose rigid constraints on election types, limiting their applicability. With PQKryvos, defenders can implement secure e-voting solutions that accommodate the full spectrum of real-world electoral processes, from simple majority votes to complex ranked-choice systems or multi-candidate grading, without compromising security. This flexibility reduces the need for custom, potentially insecure, solutions for different election methods.
Public tally-hiding significantly enhances voter privacy, a cornerstone of democratic elections. By revealing only the final election result (e.g., the winner) and not the detailed vote distribution, PQKryvos protects voters from statistical inferences, potential coercion, or undue influence based on granular voting patterns. Defenders can leverage this feature to build more trustworthy systems that assuage public concerns about privacy in digital elections, fostering greater participation and confidence.
The inherent verifiability through zero-knowledge proofs is crucial for maintaining election integrity. Even with tally-hiding, the correctness of the election outcome can be publicly and independently verified without revealing any individual votes or the hidden tally. This transparency is vital for auditing election results and building public trust, allowing anyone to confirm that the declared winner was indeed derived correctly from the cast ballots.
Furthermore, the demonstrated efficiency gains are highly significant. The substantial reduction in proving time (e.g., from 181 seconds to 5 seconds for a critical proof component) makes large-scale PQC e-voting practical. Performance has historically been a major barrier to the widespread adoption of cryptographic voting schemes. PQKryvos shows that PQC e-voting can be not only secure but also efficient enough for real-world deployment, even outperforming some classical cryptographic counterparts. This efficiency removes a significant hurdle for defenders considering robust e-voting solutions.
Finally, the protocol's design to avoid tally overhead is an important consideration. Defenders should be wary of PQC protocols that rely on approximate proofs and necessitate randomness reduction during aggregation, as this can introduce substantial performance bottlenecks (e.g., 31 minutes of overhead). PQKryvos's use of exact proofs ensures consistent, high performance throughout the aggregation process, offering a more robust and scalable solution for future e-voting implementations.
Key Takeaways
- First of its Kind: PQKryvos is the pioneering post-quantum secure e-voting protocol that natively supports arbitrary ballot formats and provides public tally-hiding, addressing critical gaps in existing systems.
- Post-Quantum Foundation: It achieves security against quantum adversaries by leveraging lattice-based commitments and a post-quantum secure zero-knowledge proof system, replacing classical cryptographic components of the original Kryvos framework.
- Efficiency Breakthrough: A key innovation involves efficiently bridging the field mismatch between lattice-based commitments and R1CS-friendly ZKPs, leading to a dramatic performance improvement (e.g., a 36-fold speedup from 181 seconds to 5 seconds for a fundamental proof operation).
- Superior Performance: PQKryvos not only achieves post-quantum security but also outperforms previous elliptic curve-based instantiations in terms of efficiency and avoids the "tally overhead" issues present in other PQC protocols that rely on approximate proofs.
- Enhanced Privacy and Flexibility: The protocol significantly enhances voter privacy through public tally-hiding (revealing only the final result, not the full tally) and offers unprecedented flexibility by accommodating diverse, real-world ballot formats.
- Practical Verifiability: Despite hiding the full tally, the system maintains complete verifiability through zero-knowledge proofs, ensuring that the election outcome can be publicly confirmed as correctly computed from the aggregated votes.
About the Speaker(s)
The talk "PQKryvos: Post-Quantum Secure E-Voting With Flexible Ballot Formats and Public Tally-Hiding" was presented by Nicolas Huber. He is one of the paper's authors and is affiliated with the University of Stuttgart. The work is described as a joint effort, with the paper also authored by Ralf Küsters and Pascal Reisert, both also associated with the University of Stuttgart. Their collective research focuses on advancing the security and practicality of cryptographic protocols, particularly in the domain of e-voting, with a strong emphasis on post-quantum resilience.
Reviews
Dr. Zero (Offensive Security Researcher) — SOLID
PQKryvos actually achieves the holy grail of making a post-quantum implementation faster than the legacy elliptic curve version it replaces. The researchers solved a nasty field mismatch between lattice commitments and R1CS ZKPs to drop proving time from three minutes to five seconds. It's brilliant math, even if applying it to the cursed domain of e-voting means they're solving the one part of the system that isn't actually broken.
Heather Calloway (CISO) — WEAK
This is deep cryptographic research, not a boardroom strategy session, so keep it away from your executive committee. However, for your enterprise architecture directors, it provides a crucial signal about the Post-Quantum Cryptography (PQC) transition: the severe performance penalties of PQC zero-knowledge proofs are actively being solved.
→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026
All talks from Privacy Enhancing Technologies Symposium (PETS) 2026