pith. sign in

arxiv: 2512.17613 · v2 · submitted 2025-12-19 · 💻 cs.CR

A Post-Quantum Secure End-to-End Verifiable E-Voting Protocol Based on Multivariate Polynomials

Vikas Srivastava , Debasish Roy , Sihem Mesnager , Nibedita Kundu , Sumit Kumar Debnath , Sourav Mukhopadhyay This is my paper

Pith reviewed 2026-05-16 21:01 UTC · model grok-4.3

classification 💻 cs.CR
keywords post-quantum cryptographye-votingmultivariate polynomialsMQ problemend-to-end verifiabilitycryptographic protocolNP-hard problemselection security
0
0 comments X

The pith

Multivariate polynomials form the basis for the first post-quantum secure end-to-end verifiable e-voting protocol.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper designs an electronic voting system whose security holds even if quantum computers become available. It replaces number-theoretic assumptions vulnerable to Shor's algorithm with the hardness of solving systems of multivariate quadratic equations over finite fields. The resulting protocol maintains voter privacy while allowing anyone to verify that all votes are counted correctly. The construction uses only standard cryptographic building blocks and aims to be efficient enough for practical deployment. If the underlying problem stays hard, the scheme provides long-term protection for digital elections without new quantum-resistant number theory.

Core claim

The authors construct the first end-to-end verifiable e-voting protocol whose security reduces to the NP-hard multivariate quadratic problem rather than to factoring or discrete logarithms. The protocol achieves ballot secrecy, integrity, and public verifiability by embedding multivariate polynomial techniques into standard primitives for registration, voting, and tallying. Concrete parameters are chosen so that the scheme remains efficient while inheriting post-quantum resistance from the presumed intractability of the MQ problem.

What carries the argument

A voting protocol built from multivariate polynomial-based primitives whose security is reduced directly to the hardness of the multivariate quadratic (MQ) problem.

If this is right

  • Current number-theoretic e-voting systems can be replaced by a construction whose security does not collapse under quantum algorithms.
  • Voters and observers obtain mathematical assurance that ballots are recorded and tallied correctly without trusting any single party.
  • Election infrastructure can adopt polynomial-based cryptography to achieve post-quantum security using only familiar primitives.
  • The design shows that NP-hard problems can support full-featured protocols such as voting while remaining practical.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If performance benchmarks confirm low overhead, the protocol could be piloted in local elections to test real-world scalability.
  • Similar multivariate constructions might be adapted for other privacy-critical applications such as secure surveys or anonymous credentials.
  • Parameter optimization studies could further reduce ciphertext sizes while preserving the claimed hardness.

Load-bearing premise

The concrete multivariate quadratic instances used in the protocol remain computationally hard for both classical and quantum computers, and the protocol adds no new vulnerabilities or side-channel leaks.

What would settle it

An efficient classical or quantum algorithm that solves the specific MQ instances arising from the protocol parameters, or a concrete attack that breaks voter privacy or prevents correct verification while the MQ assumption still holds.

Figures

Figures reproduced from arXiv: 2512.17613 by Debasish Roy, Nibedita Kundu, Sihem Mesnager, Sourav Mukhopadhyay, Sumit Kumar Debnath, Vikas Srivastava.

Figure 1
Figure 1. Figure 1: Multivariate Encryption • MQE.Kg: It generates a secret key (L, F, T ) and a public key P = L ◦F ◦ T , where L : F m q → F m q and T : F n q → F n q are two invertible affine maps, and F : F n q → F m q is an easily invertible function, known as “Central Map”. Thereby, P is a system of m ∈ Z number of multivariate polynomials in n ∈ Z number of variables. • MQE.Enc: Given a message x ∈ F m q and a public k… view at source ↗
Figure 2
Figure 2. Figure 2: Multivariate Signature as x’s signature. Note that F −1 (y) signifies one (among perhaps many) pre-images of y under F. • MQS.Ver: If equality x ?= P(w) holds, a message-signature pair (x, w) is accepted by the verifier, otherwise rejects [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: System architecture and communication flow of [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Communication flow in the Registration Phase of E2E-PQ-EVot • Vu computes c, r ← Comm(CANj ) and sends c to Poll-Officer. Here Comm is a secure commitment protocol. From i = 1, . . . , L, Poll-Officer computes σi ← MQS.Sign(skSP O , CANi ∥ c) • Poll-Officer sets ˜σ = (σ1, . . . , σL) and sends ˜σ to Vu. • From i = 1, . . . , L, if MQS.Ver(CANi ∥ c, σi , pkSP O ) = 0, returns ⊥ Vu obtains the signature Σ = … view at source ↗
Figure 5
Figure 5. Figure 5: Communication flow in the Voting Phase of E2E-PQ-EVot • Count-Center obtains Bu j from Bulletin Board. • Count-Center computes MQE.Dec(Bu j , skECC ) to obtain Σ||CANj . In the fol￾lowing, Count-Center checks the validity of the signature Σ for CANj . If the verification succeeds, then add 1 in front of CANj in the bulletin board • Count-Center repeats the process of each of the Bu j and publishes the fina… view at source ↗
read the original abstract

Voting is a primary democratic activity through which voters select representatives or approve policies. Conventional paper ballot elections have several drawbacks that might compromise the fairness, effectiveness, and accessibility of the voting process. Therefore, there is an increasing need to design safer, effective, and easily accessible alternatives. E-Voting is one such solution that uses digital tools to simplify voting. Existing state-of-the-art designs for secure E-Voting are based on number-theoretic hardness assumptions. These designs are no longer secure due to quantum algorithms such as Shor's algorithm. We present the design and analysis of \textit{first} post-quantum secure end-to-end verifiable E-Voting protocol based on multivariate polynomials to address this issue. The security of our proposed design depends on the hardness of the MQ problem, which is an NP-hard problem. We present a simple yet efficient design involving only standard cryptographic primitives as building blocks.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims to present the design and analysis of the first post-quantum secure end-to-end verifiable e-voting protocol constructed from multivariate polynomials. Security is asserted to rest on the NP-hardness of the MQ problem rather than number-theoretic assumptions vulnerable to quantum algorithms such as Shor's; the construction is described as using only standard cryptographic primitives.

Significance. If a concrete security reduction to a hard MQ instance with explicit, attack-resistant parameters were supplied and verified, the work would constitute a meaningful contribution by supplying a post-quantum alternative for end-to-end verifiable voting, an area currently dominated by schemes whose long-term security is threatened by quantum computers.

major comments (2)
  1. [Abstract] Abstract: the central claim that 'the security of our proposed design depends on the hardness of the MQ problem' is not supported by any concrete parameter tuple (field size q, number of variables n, number of equations m, degree d) or by an explicit reduction showing that an adversary breaking end-to-end verifiability or privacy yields an efficient MQ solver for the specific polynomials used in the protocol. NP-hardness alone does not establish cryptographic hardness for the chosen instance.
  2. [Security analysis] Security analysis section (wherever the reduction is claimed): no proof sketch, game sequence, or hybrid argument is supplied that relates the voting properties (ballot privacy, verifiability) to the MQ assumption; without this, the post-quantum security assertion remains an unverified assertion rather than a theorem.
minor comments (2)
  1. [Abstract] The abstract states the protocol is 'simple yet efficient' yet supplies no concrete complexity figures, communication cost, or comparison table against existing post-quantum or classical e-voting schemes.
  2. [Introduction] Notation for the multivariate polynomials and the mapping from votes to polynomial instances is not introduced in the abstract and should be defined at first use in the main body.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive criticism. We agree that the post-quantum security claims require concrete parameters and an explicit reduction to be fully rigorous, and we will revise the manuscript to address both points.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that 'the security of our proposed design depends on the hardness of the MQ problem' is not supported by any concrete parameter tuple (field size q, number of variables n, number of equations m, degree d) or by an explicit reduction showing that an adversary breaking end-to-end verifiability or privacy yields an efficient MQ solver for the specific polynomials used in the protocol. NP-hardness alone does not establish cryptographic hardness for the chosen instance.

    Authors: We accept this observation. The current manuscript relies on the general NP-hardness of MQ without specifying concrete parameters or a direct reduction. In the revised version we will add a concrete parameter set (q=2, n=80, m=80, d=2) chosen to meet current MQ security estimates against known attacks, together with a brief argument that breaking ballot privacy or verifiability yields an MQ solver for the polynomials instantiated in the protocol. revision: yes

  2. Referee: [Security analysis] Security analysis section (wherever the reduction is claimed): no proof sketch, game sequence, or hybrid argument is supplied that relates the voting properties (ballot privacy, verifiability) to the MQ assumption; without this, the post-quantum security assertion remains an unverified assertion rather than a theorem.

    Authors: We agree that a formal reduction is missing. The manuscript currently offers only an informal claim. In the revision we will insert a security theorem stating that any PPT adversary breaking ballot privacy (or verifiability) with non-negligible probability can be used to solve the underlying MQ instance with non-negligible probability, accompanied by a high-level game-hopping argument that replaces the multivariate polynomials with random ones and shows the distinguishing advantage is bounded by the MQ advantage. revision: yes

Circularity Check

0 steps flagged

No significant circularity; security reduces to external MQ hardness

full rationale

The paper's central security claim is a reduction to the established NP-hardness of the Multivariate Quadratic (MQ) problem, an independent mathematical result not derived from or fitted within the protocol construction. No self-definitional steps, fitted inputs renamed as predictions, load-bearing self-citations, uniqueness theorems imported from the authors' prior work, or ansatzes smuggled via citation appear in the abstract or described derivation. The protocol is presented as using standard cryptographic primitives with security depending on an external benchmark, making the chain self-contained against outside verification.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard cryptographic assumption that the MQ problem is hard; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption The Multivariate Quadratic (MQ) problem is NP-hard and remains hard for the parameters used in the protocol.
    Explicitly stated in the abstract as the foundation of security.

pith-pipeline@v0.9.0 · 5477 in / 1203 out tokens · 31081 ms · 2026-05-16T21:01:38.875879+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Post-quantum cryptography.Nature, 549(7671):188–194, 2017

    Daniel J Bernstein and Tanja Lange. Post-quantum cryptography.Nature, 549(7671):188–194, 2017

    work page 2017

  2. [2]

    A verifiable and practical lattice-based decryption mix net with external auditing

    Xavier Boyen, Thomas Haines, and Johannes M¨ uller. A verifiable and practical lattice-based decryption mix net with external auditing. InComputer Security– ESORICS 2020: 25th European Symposium on Research in Computer Security, ESORICS 2020, Guildford, UK, September 14–18, 2020, Proceedings, Part II 25, pages 336–356. Springer, 2020

    work page 2020

  3. [3]

    A ho- momorphic lwe based e-voting scheme

    Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabach` ene. A ho- momorphic lwe based e-voting scheme. InPost-Quantum Cryptography: 7th In- ternational Workshop, PQCrypto 2016, Fukuoka, Japan, February 24-26, 2016, Proceedings 7, pages 245–265. Springer, 2016

    work page 2016

  4. [4]

    Multivariate public key cryptography.Post-quantum cryptography, pages 193–241, 2009

    Jintai Ding and Bo-Yin Yang. Multivariate public key cryptography.Post-quantum cryptography, pages 193–241, 2009

    work page 2009

  5. [5]

    The role of the adversary model in applied security research.Computers & Security, 81:156–181, 2019

    Quang Do, Ben Martini, and Kim-Kwang Raymond Choo. The role of the adversary model in applied security research.Computers & Security, 81:156–181, 2019. 17

    work page 2019

  6. [6]

    Improved lattice-based mix-nets for electronic voting

    Valeh Farzaliyev, Jan Willemson, and Jaan Kristjan Kaasik. Improved lattice-based mix-nets for electronic voting. InInternational Conference on Information Security and Cryptology, pages 119–136. Springer, 2021

    work page 2021

  7. [7]

    Traceable ring signatures with post-quantum security

    Hanwen Feng, Jianwei Liu, Qianhong Wu, and Ya-Nan Li. Traceable ring signatures with post-quantum security. InTopics in Cryptology–CT-RSA 2020: The Cryptog- raphers’ Track at the RSA Conference 2020, San Francisco, CA, USA, February 24–28, 2020, Proceedings, pages 442–468. Springer, 2020

    work page 2020

  8. [8]

    freeman San Francisco, 1979

    Michael R Garey and David S Johnson.Computers and intractability, volume 174. freeman San Francisco, 1979

    work page 1979

  9. [9]

    CRC Press, 2016

    Feng Hao and Peter YA Ryan.Real-world electronic voting: Design, analysis and deployment. CRC Press, 2016

    work page 2016

  10. [10]

    Coercion-resistant electronic elections

    Ari Juels, Dario Catalano, and Markus Jakobsson. Coercion-resistant electronic elections. InProceedings of the 2005 ACM Workshop on Privacy in the Electronic Society, pages 61–70, 2005

    work page 2005

  11. [11]

    Post-quantum online voting scheme

    Guillaume Kaim, S´ ebastien Canard, Adeline Roux-Langlois, and Jacques Traor´ e. Post-quantum online voting scheme. InFinancial Cryptography and Data Security. FC 2021 International Workshops: CoDecFin, DeFi, VOTING, and WTSC, Vir- tual Event, March 5, 2021, Revised Selected Papers 25, pages 290–305. Springer, 2021

    work page 2021

  12. [12]

    Multi-candidate electronic voting scheme based on fully homomor- phic encryption

    Guopeng Liao. Multi-candidate electronic voting scheme based on fully homomor- phic encryption. InJournal of Physics: Conference Series, volume 1678, page 012064. IOP Publishing, 2020

    work page 2020

  13. [13]

    Short paper: Coercion-resistant voting in linear time via fully homomorphic encryption: Towards a quantum-safe scheme

    Peter B Rønne, Arash Atashpendar, Kristian Gjøsteen, and Peter YA Ryan. Short paper: Coercion-resistant voting in linear time via fully homomorphic encryption: Towards a quantum-safe scheme. InFinancial Cryptography and Data Security: FC 2019 International Workshops, VOTING and WTSC, St. Kitts, St. Kitts and Nevis, February 18–22, 2019, Revised Selected P...

    work page 2019

  14. [14]

    Introduction to quantum algorithms

    Peter W Shor. Introduction to quantum algorithms. InProceedings of Symposia in Applied Mathematics, volume 58, pages 143–160, 2002

    work page 2002

  15. [15]

    Generic construction of 1-out-of-n oblivious signatures.IEICE TRANSACTIONS on Information and Systems, 105(11):1836– 1844, 2022

    Yu Zhou, Shengli Liu, and Shuai Han. Generic construction of 1-out-of-n oblivious signatures.IEICE TRANSACTIONS on Information and Systems, 105(11):1836– 1844, 2022. 18

    work page 2022