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]
Related papers¶
- this paper misfiled as Probabilistic Encryption — the PDF was originally filed under this paper
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