International Association
for Cryptologic Research

In this paper, we introduce Oblivious Homomorphic Encryption (OHE) which provably separates the computation spaces of multiple clients of a fully homomorphic encryption (FHE) service while keeping the evaluator blind about whom a result belongs. We justify the importance of this strict isolation property of OHE by showing an attack on a recently proposed key-private cryptocurrency scheme. Our two OHE constructions are based on a puncturing function where the evaluator can effectively mask ciphertexts from rogue and potentially colluding clients. We show that this can be implemented via a FHE scheme plus an anonymous commitment scheme. OHE can be used to provide provable anonymity to cloud applications, to single server implementations of anonymous messaging as well as to account-based cryptocurrencies.