You are looking at a specific version 20210526:004025 of this paper. See the latest version.

Paper 2021/474

Algebraic Attacks on Rasta and Dasta Using Low-Degree Equations

Fukang Liu and Santanu Sarkar and Willi Meier and Takanori Isobe

Abstract

Rasta and Dasta are two fully homomorphic encryption friendly symmetric-key primitives proposed at CRYPTO 2018 and ToSC 2020, respectively. We point out that the designers of Rasta and Dasta neglected an important property of the $\chi$ operation. Combined with the special structure of Rasta and Dasta, this property directly leads to significantly improved algebraic cryptanalysis. Especially, it enables us to theoretically break 2 out of 3 instances of full Agrasta, which is the aggressive version of Rasta with the block size only slightly larger than the security level in bits. We further reveal that Dasta is more vulnerable to our attacks than Rasta for its usage of a linear layer composed of an ever-changing bit permutation and a deterministic linear transform. Based on our cryptanalysis, the security margins of Dasta and Rasta parameterized with $(n,\kappa,r)\in\{(327,80,4),(1877,128,4),(3545,256,5)\}$ are reduced to only 1 round, where $n$, $\kappa$ and $r$ denote the block size, the claimed security level and the number of rounds, respectively. These parameters are of particular interest as the corresponding ANDdepth is the lowest among those that can be implemented in reasonable time and target the same claimed security level.

Note: This is a major revision: (1). New authors. (2). A new general approach to search for more exploitable low-degree equations. (3). Experimental results are added.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
RastaDastaAgrastachi operationlinearizationalgebraic attack
Contact author(s)
liufukangs @ 163 com,takanori isobe @ ai u-hyogo ac jp,willimeier48 @ gmail com,santanu @ iitm ac in
History
2021-09-06: last of 7 revisions
2021-04-15: received
See all versions
Short URL
https://ia.cr/2021/474
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.