Paper 2024/791

Minimize the Randomness in Rasta-Like Designs: How Far Can We Go?

Lorenzo Grassi, Ruhr University Bochum
Fukang Liu, Tokyo Institute of Technology
Christian Rechberger, Graz University of Technology
Fabian Schmid, Graz University of Technology
Roman Walch, Graz University of Technology
Qingju Wang, Télécom ParisTech
Abstract

The Rasta design strategy allows building low-round ciphers due to its efficient prevention of statistical attacks and algebraic attacks by randomizing the cipher, which makes it especially suitable for hybrid homomorphic encryption (HHE), also known as transciphering. Such randomization is obtained by pseudorandomly sampling new invertible matrices for each round of each new cipher evaluation. However, naively sampling a random invertible matrix for each round significantly impacts the plain evaluation runtime, though it does not impact the homomorphic evaluation cost. To address this issue, Dasta was proposed at ToSC 2020 to reduce the cost of generating the random matrices. In this work, we address this problem from a different perspective: How far can the randomness in Rasta-like designs be reduced in order to minimize the plain evaluation runtime without sacrificing the security? To answer this question, we carefully studied the main threats to Rasta-like ciphers and the role of random matrices in ensuring security. We apply our results to the recently proposed cipher $\text{PASTA}$, proposing a modified version called $\text{PASTA}_\text{v2}$ instantiated with one initial random matrix and fixed linear layers - obtained by combining two MDS matrices with the Kronecker product - for the other rounds. Compared with $\text{PASTA}$, the state-of-the-art cipher for BGV- and BFV-style HHE, our evaluation shows that $\text{PASTA}_\text{v2}$ is up to 100% faster in plain while having the same homomorphic runtime in the SEAL homomorphic encryption library and up to 30% faster evaluation time in HElib, respectively.

Note: This symmetric cipher has been implemented and tested in the open-source HHE framework found here: https://github.com/IAIK/hybrid-HE-framework.git

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Selected Areas in Cryptography (SAC) 2024
Keywords
RastaPASTAPASTAv2HHEInterweaving matrix
Contact author(s)
Lorenzo Grassi @ ruhr-uni-bochum de
liu f ad @ m titech ac jp
christian rechberger @ tugraz at
fabian schmid @ iaik tugraz at
walch @ taceo io
qingju wang @ telecom-paris fr
History
2024-06-28: last of 2 revisions
2024-05-22: received
See all versions
Short URL
https://ia.cr/2024/791
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/791,
      author = {Lorenzo Grassi and Fukang Liu and Christian Rechberger and Fabian Schmid and Roman Walch and Qingju Wang},
      title = {Minimize the Randomness in Rasta-Like Designs: How Far Can We Go?},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/791},
      year = {2024},
      url = {https://eprint.iacr.org/2024/791}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.