Paper 2023/822
Cryptanalysis of Symmetric Primitives over Rings and a Key Recovery Attack on Rubato
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 cryptanalysiscomposite modulusRubatoKey recovery attackArithmetization 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},
note = {\url{https://eprint.iacr.org/2023/822}},
url = {https://eprint.iacr.org/2023/822}
}
