Subdomain and Access Pattern Privacy Trading off Confidentiality and Performance

Homomorphic encryption and secure multi-party computation enable computations on encrypted data. However, both techniques suffer from a large performance overhead. While advances in algorithms might reduce the overhead, we show that achieving perfect (or even computational) confidentiality is not possible without increasing the running time compared to computations on plaintext more than exponentially in some cases. In practice, however, perfect confidentiality is not always required. The paper discusses mechanisms to trade off confidentiality and performance for computing on ciphertexts. It introduces a fine-grained approach to define security levels for variables called (statistical) subdomain privacy. This concept differs substantially from prior work because it treats a variable as confidential or non-confidential depending on the actual value. We further propose privacy-preserving methods for memory access patterns. We apply our techniques to improve performance of control flow logic (loops, if-then-else logic) and arithmetic operations such as multiplications. The evaluation shows that the resulting speedup can be in the order of several magnitudes depending on the privacy needs.