Paper 2017/392

Running compression algorithms in the encrypted domain: a case-study on the homomorphic execution of RLE

Sébastien Canard, Sergiu Carpov, Donald Nokam Kuate, and Renaud Sirdey

Abstract

This paper is devoted to the study of the problem of running compression algorithms in the encrypted domain, using a (somewhat) Fully Homomorphic Encryption (FHE) scheme. We do so with a particular focus on conservative compression algorithms. Despite of the encrypted domain Turing-completeness which comes with the magic of FHE operators, we show that a number of subtleties crop up when it comes to running compression algorithms and, in particular, that guaranteed conservative compression is not possible to achieve in the FHE setting. To illustrate these points, we analyze the most elementary conservative compression algorithm of all, namely Run-Length Encoding (RLE). We first study the way to regularize this algorithm in order to make it (meaningfully) fit within the constraints of a FHE execution. Secondly, we analyze it from the angle of optimizing the resulting structure towards (as much as possible) FHE execution efficiency. The paper is concluded by concrete experimental results obtained using the Fan-Vercauteren cryptosystem as well as the Armadillo FHE compiler.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Contact author(s)
renaud sirdey @ gmail com
History
2017-05-09: received
Short URL
https://ia.cr/2017/392
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/392,
      author = {Sébastien Canard and Sergiu Carpov and Donald Nokam Kuate and Renaud Sirdey},
      title = {Running compression algorithms in the encrypted domain: a case-study on the homomorphic execution of RLE},
      howpublished = {Cryptology ePrint Archive, Paper 2017/392},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/392}},
      url = {https://eprint.iacr.org/2017/392}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.