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 ( \(\textsf{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 Pasta, proposing a modified version called \(\textsc {Pasta}_\texttt {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 Pasta, the state-of-the-art cipher for BGV- and BFV-style \(\textsf{HHE}\) , our evaluation shows that \(\textsc {Pasta}_\texttt {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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Lorenzo Grassi,
  • Fukang Liu,
  • Christian Rechberger,
  • Fabian Schmid,
  • Roman Walch,
  • Qingju Wang

摘要

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 ( \(\textsf{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 Pasta, proposing a modified version called \(\textsc {Pasta}_\texttt {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 Pasta, the state-of-the-art cipher for BGV- and BFV-style \(\textsf{HHE}\) , our evaluation shows that \(\textsc {Pasta}_\texttt {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.