Subdomain and Access Pattern Privacy - Trading off Confidentiality and Performance

Johannes Schneider, Bin Lu, Thomas Locher, Yvonne-Anne Pignolet, Matus Harvan, Sebastian Obermeier

2016

Abstract

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.

Paper Citation

in Harvard Style

Schneider J., Lu B., Locher T., Pignolet Y., Harvan M. and Obermeier S. (2016). Subdomain and Access Pattern Privacy - Trading off Confidentiality and Performance . In Proceedings of the 13th International Joint Conference on e-Business and Telecommunications - Volume 4: SECRYPT, (ICETE 2016) ISBN 978-989-758-196-0, pages 49-60. DOI: 10.5220/0005954100490060

in Bibtex Style

@conference{secrypt16,
author={Johannes Schneider and Bin Lu and Thomas Locher and Yvonne-Anne Pignolet and Matus Harvan and Sebastian Obermeier},
title={Subdomain and Access Pattern Privacy - Trading off Confidentiality and Performance},
booktitle={Proceedings of the 13th International Joint Conference on e-Business and Telecommunications - Volume 4: SECRYPT, (ICETE 2016)},
year={2016},
pages={49-60},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005954100490060},
isbn={978-989-758-196-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 13th International Joint Conference on e-Business and Telecommunications - Volume 4: SECRYPT, (ICETE 2016)
TI - Subdomain and Access Pattern Privacy - Trading off Confidentiality and Performance
SN - 978-989-758-196-0
AU - Schneider J.
AU - Lu B.
AU - Locher T.
AU - Pignolet Y.
AU - Harvan M.
AU - Obermeier S.
PY - 2016
SP - 49
EP - 60
DO - 10.5220/0005954100490060