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 $f(x,y)$ (where $x$ is Alice's input and $y$ is Bob's input) which requires communication $c$, but can be solved with communication less than $c$ when Alice is given in addition also an encryption $E_k(y)$ of Bob's input (using Bob's key $k$). We show that this definition indeed captures pre-existing notions of homomorphic encryption and (suitable variants are) sufficiently strong to derive prior known implications of homomorphic encryption in a conceptually appealing way. These include constructions of (lossy) public-key encryption from homomorphic private-key encryption, as well as collision-resistant hash functions and private information retrieval schemes.
Metadata
- Available format(s)
- 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} }