Skip to content
Crypto.world

Research

NARAD: Non-colluding Aggregator-oblivious Record-And-Decrypt

Electronic voting needs two things that usually conflict: no one should learn how an individual voted, and anyone should be able to check that the published tally is right.

NARAD: Non-colluding Aggregator-oblivious Record-And-Decrypt
arXiv
2607.07596
Published
2026-07-08
Authors
Akshit Vakati Venkata, Rajat Dugar, Ayush Adarsh

AI summary

Overview

Research area: Cryptography and security — specifically electronic voting built on additively homomorphic (Paillier) encryption, "aggregator-oblivious" secure aggregation, and blockchain-based audit trails.

Technical level: Advanced. The paper assumes familiarity with the Paillier cryptosystem, the Decisional Composite Residuosity (DCR) assumption, group arithmetic modulo N², and standard cryptographic proof structure. The implementation discussion (WebAssembly, native C, Solana programs) is more accessible but still aimed at engineers.

Scope (one sentence): The paper specifies, proves correct, implements and measures an end-to-end voting architecture in which voters encrypt packed multi-candidate ballots under self-generated keys, a collector and an aggregator jointly recover only the sum, and Solana provides the immutable ciphertext record.

What This Paper Is About

Electronic voting needs two things that usually conflict: no one should learn how an individual voted, and anyone should be able to check that the published tally is right. The authors avoid a trusted key dealer entirely — each voter generates their own secret key, and the work of tallying is split between two server roles so that neither one, alone, can link a ciphertext to a vote. The goal is to take aggregator-oblivious aggregation from a theoretical protocol to a measured system, with browser-side encryption, bit-packing so an entire multi-candidate ballot fits in one ciphertext, and a blockchain record that makes tampering with the input set detectable.

Key Contributions

  1. A combined architecture. Aggregator-oblivious Paillier encryption is paired with an immutable on-chain record: clients encrypt in the browser through WebAssembly, aggregation runs in a native C library (libtommath), and a Solana program records every ciphertext and enforces the election lifecycle stages.

  2. Six explicit assumptions and full correctness proofs. The paper states six assumptions (valid modulus; invertible non-trivial aggregator key; packing capacity k·b ≤ ⌊log₂N⌋; per-slot bound; sum bound; secret key reused as masking randomness) and proves product homomorphism, exact mask cancellation, sum recovery, and per-candidate count correctness.

  3. A privacy analysis and a packing scheme. Privacy is argued under DCR for the additive layer plus a Diffie–Hellman-style assumption on the masking base H, with separate propositions for individual vote privacy, collector obliviousness and aggregator obliviousness. A bit-packing scheme places a whole multi-candidate ballot in one ciphertext, reducing client work, on-chain transactions, storage and tally cost by a factor of k (the candidate count), with slot width b free and only the product k·b bounded by log₂N.

  4. A measured proof-of-concept and a worked example. The implementation is evaluated on its own real parameters, tallies 50,000 ballots exactly in under one second, and is accompanied by a full worked numerical example in the appendix. The code is open-source.

Main Findings

  • Exact tally at scale on real parameters: the proof-of-concept tallies 50,000 ballots exactly in under one second.

  • Capacity envelope: with b = 25 bits per slot and a 255-bit modulus (⌊log₂N⌋ = 254), the scheme supports k ≤ ⌊254/25⌋ = 10 candidates, up to 2²⁵ − 1 = 33,554,431 votes per candidate, and — as the abstract puts it — about 335 million ballots in total.

  • Packing pays off proportionally to candidate count: a single ciphertext per voter instead of one per candidate cuts client work, on-chain transactions, storage and tally cost by a factor of k. The slot width b itself is unconstrained; only k·b must stay within log₂N.

  • Mask cancellation is exact, not approximate: because the voter's secret key skᵢ doubles as the masking randomness and as the exponent of the auxiliary value auxᵢ = pk_A^{skᵢ}, raising the ciphertext product to sk_A and dividing by the collector's aux removes every mask, leaving (1 + S·N)^{sk_A}; applying L and multiplying by sk_A⁻¹ mod N returns S exactly.

  • Duty separation limits the damage of a compromise: a compromised aggregator learns only the sum, and individual ballots stay protected under DCR even if sk_A leaks. This is the paper's stated reason for preferring aggregator-oblivious encryption over running a conventional trusted key dealer inside a secure enclave (SGX has suffered practical side-channel attacks that can extract keys from "isolated" enclaves).

  • What the system does not guarantee: no cryptographic enforcement that v_{i,j} ∈ {0,1} (no range proofs yet), no coercion resistance, no collusion resistance without enclaves, and no availability guarantee — a withholding aggregator can refuse to publish. The authors also note the test validator is not Byzantine fault-tolerant and that mainnet deployment is needed for production security.

  • Integrity is tamper-evident, not tamper-proof: each ciphertext is a finalized Solana transaction, so insertion, deletion or modification of the ballot set at the host diverges from the chain and is detectable by any auditor; the tally itself is a deterministic function of public inputs and can be recomputed by anyone holding the ciphertexts and aux.

  • A bug worth recording: the reference implementation originally failed correctness by setting sk_A equal to H, which is why Assumption 6.2 explicitly rules out a degenerate public key and the code now validates parameters before each run.

Methodology in Plain English

A trusted party generates a Paillier modulus N = pq and a public base H, publishes (N, H), and goes offline — it never sees a ballot. The aggregator separately picks its own secret key sk_A and publishes pk_A = H^{sk_A}.

Each voter, in their own browser, picks a secret key skᵢ that is never shared, and encodes their whole ballot — one slot per candidate, 25 bits each — as a single integer xᵢ. From that they produce two things: a ciphertext cᵢ = H^{skᵢ}(1 + N)^{xᵢ} mod N², which goes to the aggregator and onto the chain, and an auxiliary value auxᵢ = pk_A^{skᵢ}, which goes to the collector. The auxiliary value depends only on public key material and the voter's secret key, never on the ballot, so the collector cannot read anything from it.

The collector multiplies all the auxᵢ into one group element aux and hands that single value to the aggregator. The aggregator multiplies all ciphertexts together, raises the product to sk_A, divides by aux, applies the L-function, and multiplies by sk_A⁻¹ mod N. The voters' random masks cancel in that step and what remains is the plain sum of all ballots, which is then unpacked slot by slot into per-candidate counts.

Correctness is argued by induction: a binomial lemma shows that a product of terms (1 + aᵢN) collapses to 1 + (Σaᵢ)N modulo N², which gives homomorphism; a second theorem shows the masking factor cancels; a third shows the L-function returns sk_A·S mod N, and since S < N the result is exact. Privacy is argued by reduction — each ciphertext is semantically secure under DCR plus the masking assumption, the collector's view is independent of the ballots, and the aggregator sees only the aggregate aux rather than any individual auxᵢ.

Why This Matters

Impact on research. Prior aggregator-oblivious work (Shi et al.; Joye and Libert; Leontiadis et al.) defined protocols and proved security but did not address browser-side encryption, multi-candidate packing, blockchain audit trails, or native-code performance. This paper closes that gap with a measured system on stated real parameters, and it makes an explicit architectural argument — with reasoning about enclave side channels — for why cryptographic duty separation beats a trusted key dealer in hardware. It also maps out precisely what remains unproven (range enforcement, coercion resistance), giving follow-on work a clear target list.

Real-world applications:

  • Multi-candidate public or organizational elections where ballot privacy and public verifiability are both required and a single election authority is not acceptable.
  • On-chain governance and DAO or cooperative voting, where an immutable record of exactly which ciphertexts were counted is itself the disputed question.
  • Low-cost internal ballots — student unions, board elections, shareholder resolutions — that need an auditable trail without funding a mix-net infrastructure.
  • Auditable polling and preferential voting, since the paper discusses how preferential voting fits the packing model and how the design scales to more or fewer candidates and voters.

Industry relevance. The design deliberately uses mainstream, deployable components: WebAssembly in the browser, libtommath for the heavy modular arithmetic, and a Solana program for stage enforcement and recording. The packing scheme converts candidate count from a multiplier on cost into a single ciphertext, which is the kind of saving that decides whether an on-chain voting deployment is economically viable. Notably, the paper does not report transaction fees or on-chain cost figures in the content available here; it frames on-chain cost versus capacity as a trade-off discussed qualitatively in its scaling section.

Future Directions

  1. Zero-knowledge ballot validity proofs. The most important open item by the authors' own account: integrating Pedersen commitments, Schnorr-style proofs, and a range proof (Bulletproofs or a Camenisch–Stadler Σ-protocol) on v(v−1) = 0, plus a sum proof that exactly one candidate is selected. The codebase already contains WASM-backed primitives (modular exponentiation, hashing, Fiat–Shamir challenges) but has not wired them into the voting flow.

  2. Removing the trusted setup. The trusted party knows the factorization of N. Distributed key generation would eliminate that residual trust.

  3. Threshold aggregation. Splitting sk_A across several aggregators would address both the availability gap (a withholding aggregator) and single-point key compromise.

  4. Enclave deployment and coercion resistance. Running collector and aggregator inside attested enclaves (Intel SGX or AWS Nitro Enclaves) is proposed to make the tally tamper-resistant and to prevent one host from colluding across both roles; receipt-freeness mechanisms in the Civitas line are named as the route to coercion resistance. Mainnet deployment is also needed, since the test validator is not Byzantine fault-tolerant.

Target Audience

Cryptographers and security researchers working on homomorphic encryption, secure aggregation or e-voting protocols will get the most from this paper, particularly those tracking the aggregator-oblivious line from theory toward deployed systems. It also suits blockchain engineers evaluating what on-chain voting can and cannot guarantee, and system architects deciding between enclave-based and cryptography-based trust assumptions. Readers need comfort with Paillier arithmetic and reduction-style security arguments; the implementation sections are approachable for strong engineers, and the appendix's worked numerical example makes the pipeline reproducible for those who prefer to check the algebra by hand.

Authors’ abstract

Electronic voting must keep individual ballots private while letting anyone verify the final tally. This paper presents an architecture that meets both goals without a trusted key dealer: each voter encrypts a ballot in the browser with a self-generated secret key under the Paillier additive homomorphic cryptosystem, and no party ever holds every key. Two server roles divide the tally. A collector combines the voters' per-ballot auxiliary values into a single group element;…

The full abstract on arXiv
Read the original paper