CryptoDB
Leveraging Small Message Spaces for CCA1 Security in Additively Homomorphic and BGN-type Encryption
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| Abstract: | We show that the smallness of message spaces can be used as a checksum allowing to hedge against CCA1 attacks in additively homomorphic encryption schemes. We first show that the additively homomorphic variant of Damg{\aa}rd's Elgamal provides IND-CCA1 security under the standard DDH assumption. Earlier proofs either required non-standard assumptions or only applied to hybrid versions of Damg{\aa}rd's Elgamal, which are not additively homomorphic. Our security proof builds on hash proof systems and exploits the fact that encrypted messages must be contained in a polynomial-size interval in order to enable decryption. With $3$ group elements per ciphertext, this positions Damg{\aa}rd's Elgamal as the most efficient/compact DDH-based additively homomorphic CCA1 cryptosystem. Under the same assumption, the best candidate so far was the lite Cramer-Shoup cryptosystem, where ciphertexts consist of $4$ group elements. We extend this observation to build an IND-CCA1 variant of the Boneh-Goh-Nissim encryption scheme, which allows evaluating $2$-DNF formulas on encrypted data. By computing tensor products of Damg{\aa}rd's Elgamal ciphertexts, we obtain product ciphertexts consisting of $9$ elements (instead of $16$ elements if we were tensoring lite Cramer-Shoup ciphertexts) in the target group of a bilinear map. Using similar ideas, we also obtain a CCA1 variant of the Elgamal-Paillier cryptosystem by forcing $\lambda$ plaintext bits to be zeroes, which yields CCA1 security almost for free. In particular, the message space remains exponentially large and ciphertexts are as short as in the IND-CPA scheme. We finally adapt the technique to the Castagnos-Laguillaumie system. |
BibTeX
@inproceedings{eurocrypt-2025-34949,
title={Leveraging Small Message Spaces for CCA1 Security in Additively Homomorphic and BGN-type Encryption},
publisher={Springer-Verlag},
author={Benoit Libert},
year=2025
}