Paper 2024/795

New Limits of Provable Security and Applications to ElGamal Encryption

Sven Schäge, Eindhoven University of Technology
Abstract

We provide new results showing that ElGamal encryption cannot be proven CCA1-secure – a long-standing open problem in cryptography. Our result follows from a very broad, meta-reduction-based impossibility result on random self-reducible relations with efficiently re-randomizable witnesses. The techniques that we develop allow, for the first time, to provide impossibility results for very weak security notions where the challenger outputs fresh challenge statements at the end of the security game. This can be used to finally tackle encryption-type definitions that have remained elusive in the past. We show that our results have broad applicability by casting several known cryptographic setups as instances of random self-reducible and re-randomizable relations. These setups include general semi-homomorphic PKE and the large class of certified homomorphic one-way bijections. As a result, we also obtain new impossibility results for the IND-CCA1 security of the PKEs of Paillier and Damg ̊ard–Jurik, and many one-more inversion assumptions like the one-more DLOG or the one-more RSA assumption.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2024
DOI
10.1007/978-3-031-58737-5_10
Keywords
ElGamalIND-CCA1semi-homomorphic encryptionre-randomizablerandom self-reducibleRRR
Contact author(s)
s schage @ tue nl
History
2024-05-24: approved
2024-05-22: received
See all versions
Short URL
https://ia.cr/2024/795
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/795,
      author = {Sven Schäge},
      title = {New Limits of Provable Security and Applications to {ElGamal} Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2024/795},
      year = {2024},
      doi = {10.1007/978-3-031-58737-5_10},
      note = {\url{https://eprint.iacr.org/2024/795}},
      url = {https://eprint.iacr.org/2024/795}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.