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.

Callegari, C
Vansinderen, M
Sarigiannidis, P
Samarati, P
Cabello, E
Lorenz, P
Obaidat, Ms
Published in:
Secrypt: Proceedings Of The 13Th International Joint Conference On E-Business And Telecommunications - Vol. 4, 49-60
Presented at:
13th International Joint Conference on e-Business and Telecommunications, Lisbon, PORTUGAL, JUL 26-28, 2016
Setubal, Scitepress

 Record created 2017-02-17, last modified 2018-09-13

Rate this document:

Rate this document:
(Not yet reviewed)