Skip to content

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

Year: 2018

type: technique collection: schemes status: auto

Links: ePrint 2018/181

Summary

Auto-extracted summary (unreviewed)

Rasta is a family of stream ciphers designed for MPC and FHE use cases that simultaneously achieves ANDdepth d and only d AND gates per encrypted bit, using a fixed chi non-linear layer and nonce/counter-derived random affine layers generated by an XOF. The authors argue that no attacks exist even for d between 2 and 6, and benchmark transciphering in HElib (BGV) to remove ciphertext expansion, finding balanced instances competitive with specialised designs and the aggressive 'Agrasta' variants about one order of magnitude better.

Abstract

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.
Source: pdf

Extracted details

Field Value Source Confidence
contribution Rasta design strategy: symmetric cipher with ANDdepth d and d ANDs per bit simultaneously llm 0.80
contribution security analysis against algebraic, linear and statistical attacks with conservative parameter choices llm 0.80
contribution Agrasta aggressively parameterised variants llm 0.80
contribution HElib/BGV implementation and comparison for removing FHE ciphertext expansion (transciphering) llm 0.80
schemes Rasta (symmetric stream cipher) llm 0.80
schemes BGV llm 0.80
libraries HElib llm 0.80
tasks transciphering / FHE ciphertext-expansion removal llm 0.80
tasks MPC-friendly symmetric encryption llm 0.80
security level 80-bit (benchmarked instances); parameters given for various conjectured security levels llm 0.80
code url https://github.com/iaikkrypto/rasta (URL found in the full text) regex 0.50
code url https://github.com/shaih/HElib/ (URL found in the full text) regex 0.50
limitations very low d is not implementable: required key/block size and number of additions grow very fast for a fixed security level llm 0.80
limitations security relies on conservative parameter choices; further external cryptanalysis is encouraged llm 0.80
llm relevance low llm 0.80
key result homomorphic evaluation cost improvement: about one order of magnitude (Agrasta variants in HElib experiments vs other specialised designs) llm 0.80
key result AND metrics: ANDdepth d with d ANDs per bit, d in 2..6 (design target; d in 4..6 deemed practical) llm 0.80

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: BGV 12 [p.1], MPC 10 [p.1], Zero-knowledge proofs 2 [p.30]
  • library: HElib 5 [p.25]
  • hardware: Intel Xeon 1 [p.23]
  • technique: Bootstrapping 4 [p.2]
  • assumption: Post-quantum 4 [p.29], 128-bit security 3 [p.5]
  • topic: Homomorphic encryption 22 [p.1], Benchmark 5 [p.25], Open source 2 [p.3]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s42-1_eprint-2018-181.pdf schemes 36 2.0 MB 878060922ed8

Database key: rasta-a-cipher-with-low-anddepth-and-few-ands-per-bit · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set rasta-a-cipher-with-low-anddepth-and-few-ands-per-bit COLUMN VALUE