Cryptology ePrint Archive: Report 2021/1205

FASTA - a stream cipher for fast FHE evaluation

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

Abstract: 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.

Category / Keywords: secret-key cryptography / Stream Ciphers, Homomorphic Encryption, Hybrid Encryption

Original Publication (in the same form): CT-RSA 2022

Date: received 16 Sep 2021, last revised 11 Jan 2022

Contact author: carlos cid at rhul ac uk, johnpetter at simula no, haavardr at simula no

Available format(s): PDF | BibTeX Citation

Version: 20220111:083955 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]