Paper 2022/537

Rubato: Noisy Ciphers for Approximate Homomorphic Encryption (Full Version)

Jincheol Ha
Seongkwang Kim
Byeonghak Lee
Jooyoung Lee
Mincheol Son
Abstract

A transciphering framework converts a symmetric ciphertext into a homomorphic ciphertext on the server-side, reducing computational and communication overload on the client-side. In Asiacrypt 2021, Cho et al. proposed the RtF framework that supports approximate computation. In this paper, we propose a family of noisy ciphers, dubbed Rubato, with a novel design strategy of introducing noise to a symmetric cipher of a low algebraic degree. With this strategy, the multiplicative complexity of the cipher is significantly reduced, compared to existing HE-friendly ciphers, without degrading the overall security. More precisely, given a moderate block size (16 to 64), Rubato enjoys a low multiplicative depth (2 to 5) and a small number of multiplications per encrypted word (2.1 to 6.25) at the cost of slightly larger ciphertext expansion (1.26 to 1.31). The security of Rubato is supported by comprehensive analysis including symmetric and LWE cryptanalysis. Compared to HERA within the RtF framework, client-side and server-side throughput is improved by 22.9% and 32.2%, respectively, at the cost of only 1.6% larger ciphertext expansion.

Note: We add some comments on a recent analysis on Rubato by Grassi et al.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2022
Keywords
homomorphic encryptiontransciphering frameworkstream cipherHE-friendly cipher
Contact author(s)
seongkwang kim23 @ gmail com
History
2023-07-19: revised
2022-05-10: received
See all versions
Short URL
https://ia.cr/2022/537
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/537,
      author = {Jincheol Ha and Seongkwang Kim and Byeonghak Lee and Jooyoung Lee and Mincheol Son},
      title = {Rubato: Noisy Ciphers for Approximate Homomorphic Encryption (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2022/537},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/537}},
      url = {https://eprint.iacr.org/2022/537}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.