  Homomorphic encryption (HE) offers data confidentiality by executing queries
directly on encrypted fields in the database-as-a-service (DaaS) paradigm.
While fully HE exhibits great expressiveness but prohibitive performance
overhead, a better balance between flexibility and efficiency can be achieved
by partially HE schemes. Performance-wise, however, the encryption rate of
state-of-the-art HE schemes is still orders of magnitude lower than the I/O
throughput, rendering the HE scheme the performance bottleneck.
  This paper proposes INCHE, an incrementally homomorphic encryption scheme,
which aims to boost the performance of HE schemes by incrementally encrypting
fields in relational databases. The key idea of INCHE is to explore the
intrinsic correlation between plaintexts and cache them for future reuse such
that expensive HE primitives from plaintexts to ciphertexts are avoided. We
prove the semantic security of INCHE under the chosen-plaintext attack (CPA)
model and show that its time complexity is linear in the plaintext length. We
implement an INCHE prototype by extending the Symmetria cryptosystem and verify
its effectiveness on both randomly-generated data and the TPC-H benchmark.
