International Association for Cryptologic Research

International Association
for Cryptologic Research


Eyal Kushnir


Combinatorially Homomorphic Encryption
Yuval Ishai Eyal Kushnir Ron Rothblum
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.


Yuval Ishai (1)
Ron D. Rothblum (1)