NARAD: Non-colluding Aggregator-oblivious Record-And-Decrypt
Source: arXiv:2607.07596 · Published 2026-07-08 · By Akshit Vakati Venkata, Rajat Dugar, Ayush Adarsh
TL;DR
This paper addresses the critical challenge of enabling secure and privacy-preserving electronic voting without relying on a trusted key dealer. The novel system, NARAD, uses an aggregator-oblivious architecture based on the Paillier additive homomorphic cryptosystem where each voter locally generates their own secret key and encrypts their ballot in-browser. The tally is computed by two non-colluding server roles: a collector that aggregates auxiliary masking values from voters, and an aggregator that uses this aggregate to cancel random masks and recover the overall vote sum without decrypting individual ballots. The design is anchored on six explicit cryptographic assumptions and proven correctness properties. It achieves ballot privacy, tally verifiability, and input/output integrity while avoiding trust concentration and key escrow. A bit-packing method compacts multi-candidate ballots into one ciphertext, greatly improving efficiency. The use of the Solana blockchain provides an immutable record and election lifecycle enforcement, while native C code enables performant modular arithmetic. Secure enclaves are proposed to strengthen tamper resistance and prevent cross-role collusion in practice. The open-source proof-of-concept scales to tens of thousands of ballots tallying in under one second, with a thorough formal treatment and worked numerical example provided.
Key findings
- The system supports up to 10 candidates (k=10) and 25-bit bit-packing slots (b=25), fitting ballots into 255-bit modulus N.
- With these parameters, the scheme can tally up to about 335 million ballots (2^25 - 1 votes per candidate).
- The proof-of-concept implementation tallies 50,000 ballots exactly in under one second.
- Ballot privacy is preserved under the Decisional Composite Residuosity (DCR) and Diffie–Hellman-style assumptions, with no party learning individual votes.
- Mask cancellation via homomorphic operations recovers the exact plaintext sum without decrypting individual ciphertexts (Theorem 7.4).
- The collector learns nothing about ballots as it only receives auxiliary values independent of the votes (Proposition 8.2).
- The aggregator learns only the aggregate sum S and not individual ballots despite holding the aggregate secret key (Proposition 8.3).
- The Solana blockchain ensures input integrity by immutably recording each ciphertext and enforces election stages.
Threat model
The adversary is assumed honest-but-curious and controls either the collector or the aggregator, but not both simultaneously (non-colluding). The adversary cannot break standard cryptographic assumptions (DCR or Diffie-Hellman on the masking base). The collector sees only auxiliary values independent of ballots, the aggregator sees ciphertexts and aggregated auxiliary value but cannot decrypt individual ballots. Adversaries do not corrupt voters' browsers or collude across roles. The trusted party is offline after setup, and no party holds full keying material apart from the aggregator's secret key, which only reveals the aggregate sum, not individual votes.
Methodology — deep read
Threat model & assumptions: The threat assumes honest-but-curious adversaries controlling collector or aggregator individually, but not both (non-collusion). The aggregator cannot decrypt individual ballots, only the aggregate sum, and the collector sees only auxiliary values unrelated to votes. Privacy assumes the DCR assumption on Paillier encryption and a Diffie-Hellman-type assumption on the masking base H. The trusted party is offline after setup, and there is no trusted key dealer; each voter independently generates their secret key.
Data: In elections, each voter produces a packed ballot xi encoding multiple binary votes (vi,j) per candidate j, with constraints ensuring no overflow. Voters generate ciphertext ci = H^{ski} (1+N)^{xi} mod N^2 and auxiliary value auxi = pkA^{ski} = H^{skA*ski} mod N^2. Ciphertexts are recorded on-chain (Solana) immutably, and auxiliary values sent to the collector.
Architecture / algorithm: The protocol features four parties: Trusted party (generates N, H), voters (generate secret keys and encrypt ballots), collector (multiplies auxiliary values), and aggregator (holds secret key skA, multiplies ciphertexts, raises to skA, cancels mask by dividing aggregated aux, and applies L-function then multiplies by inverse of skA mod N to recover sum). Bit-packing packs k candidates each with b bits into one plaintext integer xi < N, preserving slot independence. The structural innovation is reusing the voter’s secret key ski as the masking randomness ri, enabling exact mask cancellation when raising the product ciphertexts to skA and dividing by the aggregate aux = product of auxi.
Training regime: Not applicable (cryptographic system, not ML).
Evaluation protocol: The correctness proofs are formal theorems on homomorphic properties, mask cancellation, and exact recovery under stated assumptions. Empirically, the system is benchmarked on real parameters with up to 50,000 ballots tallying in <1s. The integrity is verified by cross-checking ciphertexts on chain and deterministic tally.
Reproducibility: The implementation is open-source on GitHub including browser-side WebAssembly encryption and native C tally (libtommath). A fully worked numerical example reproduces the full pipeline. The dataset consists of synthetic ballot encryptions, not public election data.
Full example: A voter encrypts a 3-candidate ballot as bits [0,1,0], packs into integer m=2^{25}, chooses sk_i randomly, computes ciphertext ci=H^{sk_i}(1+N)^m, computes aux_i=pkA^{sk_i}, sends ci on-chain and aux_i to collector. Collector multiplies all aux_i into aux, sends to aggregator. Aggregator computes product ciphertext Π, exponentiates Π^{skA}, cancels mask by multiplying by aux^{-1}, applies L-function, multiplies by skA^{-1} mod N to get sum S exactly. Then unpacks S per bit-slot to get per-candidate tallies.
Technical innovations
- Use of aggregator-oblivious additive homomorphic encryption under Paillier with self-generated voter randomness replacing trusted key dealer.
- Reusing voter secret key as encryption mask randomness to enable exact mask cancellation by combining collector's aggregated auxiliary values and aggregator's exponentiation.
- Bit-packing multi-candidate ballots into single Paillier plaintext integer allowing scalable tally with reduced client work and on-chain footprint.
- Integration with Solana blockchain for immutable ciphertext recording and election lifecycle enforcement.
- Use of WebAssembly in browsers for client-side encryption and native C library (libtommath) for efficient server-side modular arithmetic.
Baselines vs proposed
- Helios baseline: relies on trusted key dealer holding decryption key; NARAD removes this by voter key generation and non-colluding roles.
- NARAD tally time: 50,000 ballots in under 1 second, no comparable public timings provided for prior aggregator-oblivious systems.
Limitations
- No cryptographic range proofs enforcing vote validity (votes must be 0 or 1), relying instead on voter honesty (Assumption 6.4).
- Trust in the initial trusted party to generate modulus N; no distributed key generation implemented.
- Single aggregator can withhold tally publication; no threshold aggregation or active availability guarantees yet.
- Privacy requires non-collusion between collector and aggregator; collusion enables deanonymization.
- No coercion resistance; voters can reveal their secret key to prove individual votes.
- Test deployment validator is not Byzantine fault-tolerant; production deployment needed for stronger security.
Open questions / follow-ons
- How to integrate zero-knowledge range proofs for enforcing ballot validity (0/1 votes) without excessive cost?
- Can distributed key generation eliminate the trusted party setup trust?
- How to design threshold decryption or multi-aggregator protocols to improve availability and resist withholding attacks?
- What practical defenses or hardware designs could mitigate collector-aggregator collusion risks further?
Why it matters for bot defense
From a bot-defense and CAPTCHA perspective, this paper demonstrates a robust cryptographic architecture for privacy-preserving aggregation without centralized trusted dealers. Its approach of splitting trust among non-colluding roles and using homomorphic encryption with mask cancellation can inspire decentralized anti-bot signal aggregation that preserves user privacy. The integration of immutable blockchain records and client-side WebAssembly processing aligns with modern tamper-evident and client-trusted computations. The bit-packing method for efficient multi-feature encoding may be adapted for large-scale, bandwidth-sensitive telemetry aggregation. However, its reliance on non-collusion and absence of cryptographic input validity proofs highlight the practical challenges of deploying privacy-preserving aggregates in adversarial settings typical for bot defense systems, signaling key areas for further development.
Cite
@article{arxiv2607_07596,
title={ NARAD: Non-colluding Aggregator-oblivious Record-And-Decrypt },
author={ Akshit Vakati Venkata and Rajat Dugar and Ayush Adarsh },
journal={arXiv preprint arXiv:2607.07596},
year={ 2026 },
url={https://arxiv.org/abs/2607.07596}
}