Paper 2023/1973

Combinatorially Homomorphic Encryption

Yuval Ishai, Technion – Israel Institute of Technology
Eyal Kushnir, Technion – Israel Institute of Technology
Ron D. Rothblum, Technion – Israel Institute of Technology

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.

Available format(s)
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
Homomorphic EncryptionCommunication Complexity
Contact author(s)
yuvali @ cs technion ac il
eyal kushnir @ cs technion ac il
rothblum @ cs technion ac il
2024-01-05: approved
2023-12-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yuval Ishai and Eyal Kushnir and Ron D. Rothblum},
      title = {Combinatorially Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1973},
      year = {2023},
      doi = {},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.