Paper 2023/1800

Algebraic Attack on FHE-Friendly Cipher HERA Using Multiple Collisions

Fukang Liu, Tokyo Institute of Technology
Abul Kalam, Indian Institute of Technology Madras
Santanu Sarkar, Indian Institute of Technology Madras
Willi Meier, FHNW
Abstract

Fully homomorphic encryption (FHE) is an advanced cryptography technique to allow computations (i.e., addition and multiplication) over encrypted data. After years of effort, the performance of FHE has been significantly improved and it has moved from theory to practice. The transciphering framework is another important technique in FHE to address the issue of ciphertext expansion and reduce the client-side computational overhead. To apply the transciphering framework to the CKKS FHE scheme, a new transciphering framework called the Real-to-Finite-Field (RtF) framework and a corresponding FHE-friendly symmetric-key primitive called HERA were proposed at ASIACRYPT 2021. Although HERA has a very similar structure to \aes, it is considerably different in the following aspects: 1) the power map $x\mapsto x^3$ is used as the S-box; 2) a randomized key schedule is used; 3) it is over a prime field $\mathbb F_p$ with $p>2^{16}$. In this work, we perform the first third-party cryptanalysis of HERA, by showing how to mount new algebraic attacks with multiple collisions in the round keys. Specifically, according to the special way to randomize the round keys in HERA, we find it possible to peel off the last nonlinear layer by using collisions in the last-round key and a simple property of the power map. In this way, we could construct an overdefined system of equations of a much lower degree in the key, and efficiently solve the system via the linearization technique. As a result, for HERA with 192 and 256 bits of security, respectively, we could break some parameters under the same assumption made by designers that the algebra constant $\omega$ for Gaussian elimination is $\omega=2$, i.e., Gaussian elimination on an $n\times n$ matrix takes $\mathcal{O}(n^{\omega})$ field operations. If using more conservative choices like $\omega\in\{2.8,3\}$, our attacks can also successfully reduce the security margins of some variants of HERA to only 1 round. However, the security of HERA with 80 and 128 bits of security is not affected by our attacks due to the high cost to find multiple collisions. In any case, our attacks reveal a weakness of HERA caused by the randomized key schedule and its small state size.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published by the IACR in TOSC 2024
Keywords
HERAalgebraic attackmultiple collisionsrandomized key schedule
Contact author(s)
fukang liu @ hotmail com
abulkalam sunny @ gmail com
santanu @ iitm ac in
willimeier48 @ gmail com
History
2024-02-16: revised
2023-11-22: received
See all versions
Short URL
https://ia.cr/2023/1800
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1800,
      author = {Fukang Liu and Abul Kalam and Santanu Sarkar and Willi Meier},
      title = {Algebraic Attack on {FHE}-Friendly Cipher {HERA} Using Multiple Collisions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1800},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1800}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.