Cryptanalysis of Symmetric Primitives over Rings and a Key Recovery Attack on Rubato

Lorenzo Grassi; Irati Manterola Ayala; Martha Norberg Hovd; Morten Øygarden; Håvard Raddum; Qingju Wang

Paper 2023/822

Cryptanalysis of Symmetric Primitives over Rings and a Key Recovery Attack on Rubato

Lorenzo Grassi, Ruhr University Bochum

Irati Manterola Ayala, Simula UiB

Martha Norberg Hovd, Simula UiB

Morten Øygarden, Simula UiB

Håvard Raddum, Simula UiB

Qingju Wang, Telecom Paris

Abstract

Symmetric primitives are a cornerstone of cryptography, and have traditionally been defined over fields, where cryptanalysis is now well understood. However, a few symmetric primitives defined over rings Z_q for a composite number q have recently been proposed, a setting where security is much less studied. In this paper we focus on studying established algebraic attacks typically defined over fields and the extent of their applicability to symmetric primitives defined over the ring of integers modulo a composite q. Based on our analysis, we present an attack on full Rubato, a family of symmetric ciphers proposed by Ha et al. at Eurocrypt 2022 designed to be used in a transciphering framework for approximate fully homomorphic encryption. We show that at least 25% of the possible choices for q satisfy certain conditions that lead to a successful key recovery attack with complexity significantly lower than the claimed security level for five of the six ciphers in the Rubato family.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: A minor revision of an IACR publication in CRYPTO 2023
Keywords: Algebraic cryptanalysis composite modulus Rubato Key recovery attack Arithmetization oriented primitives
Contact author(s): lorenzo grassi @ ruhr-uni-bochum de
irati @ simula no
martha @ simula no
morten oygarden @ simula no
haavardr @ simula no
qingju wang @ telecom-paris fr
History: 2023-06-06: approved; 2023-06-02: received; See all versions
Short URL: https://ia.cr/2023/822
License: CC BY

BibTeX

@misc{cryptoeprint:2023/822,
      author = {Lorenzo Grassi and Irati Manterola Ayala and Martha Norberg Hovd and Morten Øygarden and Håvard Raddum and Qingju Wang},
      title = {Cryptanalysis of Symmetric Primitives over Rings and a Key Recovery Attack on Rubato},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/822},
      year = {2023},
      url = {https://eprint.iacr.org/2023/822}
}