Paper 2023/1973
Combinatorially Homomorphic Encryption
Abstract
Homomorphic encryption enables public computation over encrypted data. In the past few decades, homomorphic encryption has become a staple of both the theory and practice of cryptography. Nevertheless, while there is a general loose understanding of what it means for a scheme to be homomorphic, to date there is no single unifying minimal definition that captures all schemes.
In this work, we propose a new definition, which we refer to as combinatorially homomorphic encryption, which attempts to give a broad base that captures the intuitive meaning of homomorphic encryption and draws a clear line between trivial and nontrivial homomorphism.
Our notion relates the ability to accomplish some task when given a ciphertext, to accomplishing the same task without the ciphertext, in the context of communication complexity. Thus, we say that a scheme is combinatorially homomorphic if there exists a communication complexity problem
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Major revision. Rothblum, G., Wee, H. (eds) Theory of Cryptography. TCC 2023. Lecture Notes in Computer Science, vol 14370. Springer, Cham
- DOI
- https://doi.org/10.1007/978-3-031-48618-0_9
- Keywords
- Homomorphic EncryptionCommunication Complexity
- Contact author(s)
-
yuvali @ cs technion ac il
eyal kushnir @ cs technion ac il
rothblum @ cs technion ac il - History
- 2024-01-05: approved
- 2023-12-31: received
- See all versions
- Short URL
- https://ia.cr/2023/1973
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1973, author = {Yuval Ishai and Eyal Kushnir and Ron D. Rothblum}, title = {Combinatorially Homomorphic Encryption}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1973}, year = {2023}, doi = {https://doi.org/10.1007/978-3-031-48618-0_9}, url = {https://eprint.iacr.org/2023/1973} }