Paper 2018/181

Rasta: A cipher with low ANDdepth and few ANDs per bit

Christoph Dobraunig
Maria Eichlseder
Lorenzo Grassi
Virginie Lallemand
Gregor Leander
Eik List
Florian Mendel
Christian Rechberger

Recent developments in multi party computation (MPC) and fully homomorphic encryption (FHE) promoted the design and analysis of symmetric cryptographic schemes that minimize multiplications in one way or another. In this paper, we propose with Rasta a design strategy for symmetric encryption that has ANDdepth d and at the same time only needs d ANDs per encrypted bit. Even for very low values of d between 2 and 6 we can give strong evidence that attacks may not exist. This contributes to a better understanding of the limits of what concrete symmetric-key constructions can theoretically achieve with respect to AND-related metrics, and is to the best of our knowledge the first attempt that minimizes both metrics simultaneously. Furthermore, we can give evidence that for choices of d between 4 and 6 the resulting implementation properties may well be competitive by testing our construction in the use-case of removing the large ciphertext-expansion when using the BGV scheme.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2018
Symmetric encryptionASASAhomomorphic encryptionmultiplicative complexitymultiplicative depth
Contact author(s)
christoph dobraunig @ iaik tugraz at
2024-06-07: last of 2 revisions
2018-02-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christoph Dobraunig and Maria Eichlseder and Lorenzo Grassi and Virginie Lallemand and Gregor Leander and Eik List and Florian Mendel and Christian Rechberger},
      title = {Rasta: A cipher with low {ANDdepth} and few {ANDs} per bit},
      howpublished = {Cryptology ePrint Archive, Paper 2018/181},
      year = {2018},
      doi = {10.1007/978-3-319-96884-1_22},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.