Skip to content

Benaloh's Dense Probabilistic Encryption Revisited

Authors: Laurent Fousse; Pascal Lafourcade; Mohamed Alnuaimi
Year: 2010
Venue: arXiv preprint

type: theory collection: misfiled status: auto

Links: arXiv:1008.2991

Summary

Auto-extracted summary (unreviewed)

Revisits Benaloh's 1994 dense probabilistic (additively homomorphic) encryption scheme, which improved the expansion factor of Goldwasser-Micali. The authors show that the original key-generation condition is insufficient and can make decryption ambiguous, give a corrected necessary and sufficient condition with a full proof of correctness, compute the failure probability of the original scheme (close to 1/3 for the suggested parameters r = 3^k), and analyse the consequences for applications such as e-voting, where a bad key can invert an election result.

Abstract

In 1994, Josh Benaloh proposed a probabilistic homomorphic encryption scheme, enhancing the poor expansion factor provided by Goldwasser and Micali's scheme. Since then, numerous papers have taken advantage of Benaloh's homomorphic encryption function, including voting schemes, computing multi-party trust privately, non-interactive verifiable secret sharing, online poker... In this paper we show that the original description of the scheme is incorrect, possibly resulting in ambiguous decryption of ciphertexts. We give a corrected description of the scheme and provide a complete proof of correctness. We also compute the probability of failure of the original scheme. Finally we analyze several applications using Benaloh's encryption scheme. We show in each case the impact of a bad choice in the key generation phase of Benaloh's scheme. For instance in the application of e-voting protocol, it can inverse the result of an election, which is a non negligible consequence.
Source: arxiv

Extracted details

Field Value Source Confidence
contribution shows that the original description of Benaloh's scheme is incorrect and can give ambiguous decryption llm 0.85
contribution corrected description of the scheme with a complete proof of correctness llm 0.85
contribution necessary and sufficient condition on the public key for unambiguous decryption llm 0.85
contribution explicit failure probability of the original key generation llm 0.85
contribution impact analysis on applications (e-voting, multi-party trust, verifiable secret sharing, online poker) llm 0.85
schemes Benaloh dense probabilistic encryption llm 0.85
schemes Goldwasser-Micali llm 0.85
schemes additively homomorphic public-key encryption llm 0.85
tasks e-voting llm 0.85
tasks multi-party trust computation llm 0.85
tasks non-interactive verifiable secret sharing llm 0.85
interaction other llm 0.85
limitations the scheme's rarity in real implementations limits the observed impact llm 0.85
limitations no performance comparison with other homomorphic schemes is reported llm 0.85
key result probability of an incorrect public key in the original scheme: close to 1/3 (suggested parameters r = 3^k where decryption is efficient) llm 0.85

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: Paillier 5 [p.1], Goldwasser-Micali 4 [p.1], Secret sharing 3 [p.1], RSA 2 [p.3]
  • technique: Non-interactive 3 [p.1]
  • topic: Homomorphic encryption 9 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/misfiled/fousse-2010_benalohs-dense-probabilistic-encryption-revisited.pdf misfiled 13 176.7 KB 0131df464199

Database key: benaloh-s-dense-probabilistic-encryption-revisited · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set benaloh-s-dense-probabilistic-encryption-revisited COLUMN VALUE