Chosen-IV Algebraic Attack on Randomized Ciphers FASTA and HERA

Fully homomorphic encryption (FHE) enables computation on encrypted data without decryption, providing strong guarantees for privacy-preserving applications. However, its practicality heavily depends on the efficiency of the underlying cryptographic primitives. To this end, FHE-friendly symmetric ciphers have been designed to achieve a balance between security and homomorphic efficiency. Among them, FASTA (a variant of Rasta) and HERA are two FHE-friendly symmetric-key primitives proposed at CT-RSA 2022 and ASIACRYPT 2021, respectively. Previous cryptanalytic results of FASTA and HERA were achieved by peeling off the last nonlinear layer. In this paper, we present an improved algebraic cryptanalysis of FASTA by exploiting structural properties of its affine layers through chosen-IV algebraic attacks. We demonstrate that both the first and last nonlinear layers of FASTA can be removed, which significantly reduces the algebraic degree of the resulting system. As a result, we achieve the first key-recovery attack on 4-round FASTA, with time complexity about 2118.8, memory complexity 294.2, and data complexity 234.1, improving the best attack by 1 round. Overall, our findings reveal exploitable algebraic weaknesses in the affine layer of FASTA. For HERA, our refined chosen-IV algebraic attack based on the eXtended Linearization (XL) algorithm significantly enlarges the feasible parameter range, enabling attacks on prime moduli that were previously considered out of reach. This is mainly because the integration of the XL algorithm further decreases the number of keystream words required during the online phase of the chosen-IV algebraic attack, thus reducing the cost of its offline phase, i.e., a better tradeoff between the offline and online complexity can be achieved in our improved attack. This highlights the central role of the XL algorithm in enabling efficient algebraic attacks on FHE-friendly symmetric ciphers.