International Association for Cryptologic Research

International Association
for Cryptologic Research


Combinatorially Homomorphic Encryption

Yuval Ishai , Technion
Eyal Kushnir , Technion
Ron Rothblum , Technion
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2023
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 \emph{combinatorially homomorphic encryption}, which attempts to give a broad base that captures the intuitive meaning of homomorphic encryption. 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 \emph{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.
  title={Combinatorially Homomorphic Encryption},
  author={Yuval Ishai and Eyal Kushnir and Ron Rothblum},