Paper 2021/1205

FASTA - a stream cipher for fast FHE evaluation

Carlos Cid, John Petter Indrøy, and Håvard Raddum


In this paper we propose FASTA, a stream cipher design optimised for implementation over popular fully homomorphic encryption schemes. A number of symmetric encryption ciphers have been recently proposed for FHE applications, e.g. the block cipher LowMC, and the stream ciphers Rasta (and variants), FLIP and Kreyvium. The main design criterion employed in these ciphers has typically been to minimise the multiplicative complexity of the algorithm. However, other aspects affecting their efficient evaluation over common FHE libraries are often overlooked, compromising their real-world performance. Whilst FASTA may also be considered as a variant of Rasta, it has its parameters and linear layer especially chosen to allow efficient implementation over the BGV scheme, particularly as implemented in the HElib library. This results in a speedup by a factor of 25 compared to the most efficient publicly available implementation of Rasta. FASTA’s target is BGV, as implemented in HElib. However the design ideas introduced in the cipher could also be potentially employed to achieve improvements in the homomorphic evaluation in other popular FHE schemes/libraries. We do consider such alternatives in this paper (e.g. BFV and BGVrns, as implemented in SEAL and PALISADE), but argue that, unlike BGV in HElib, it is more challenging to make use of their parallelism in a Rasta-like stream cipher design.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. CT-RSA 2022
Stream CiphersHomomorphic EncryptionHybrid Encryption
Contact author(s)
carlos cid @ rhul ac uk
johnpetter @ simula no
haavardr @ simula no
2022-03-10: last of 2 revisions
2021-09-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carlos Cid and John Petter Indrøy and Håvard Raddum},
      title = {FASTA - a stream cipher for fast FHE evaluation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1205},
      year = {2021},
      doi = {10.1007/978-3-030-95312-6_19},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.