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]
Related papers¶
- this paper follow up of Pasta: A Case for Hybrid Homomorphic Encryption — follow-up listed for scheme "Pasta / Rasta / Kreyvium / Elisabeth (HHE ciphers)"
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