Paper 2025/1593

Leveraging Smaller Finite Fields for More Efficient ZK-Friendly Hash Functions

Abstract

Maximum distance separable (MDS) matrices are the main building blocks that provide the maximum possible diffusion in several block ciphers and cryptographic hash functions. In addition to using MDS matrices directly, there are also some indirect but simple and efficient methods that provide the maximum possible diffusion property. In particular, the subfield construction introduced by Barreto et al. in [DCC 56 (2-3) 141-162 (2010)] and its generalization examined by Otal in [IJISS 11 (2) 1-11 (2022)] make use of MDS matrices over smaller finite fields to provide the maximum possible diffusion property over larger finite fields. ZK-friendly hash functions, in contrast to the classical cryptographic hash functions, use higher-dimensional MDS matrices over larger finite fields. In this paper, we examine the applicability of the generalized subfield construction and the possibility of improvements on ZK-friendly hash functions. As a case study, we focus on a recent ZK-friendly hash function Vision Mark-32 presented by Ashur et al. in [IACR Preprint 2024/633]. In particular, instead of using a $24\times 24$ MDS matrix over $\mathbb{F}_{2^{32}}$ for a $24\times 1$ column input over $\{0,1\}^{{32}}$, we suggest separating the $24\times 1$ column input over $\{0,1\}^{{32}}$ into four $24\times 1$ subcolumns over $\{0,1\}^{{8}}$ and then using a $24\times 24$ MDS matrix over $\mathbb{F}_{2^8}$ for each subcolumn. This method still keeps the maximum diffusion property without any compromise and provides simplicity and efficiency. For example, it is possible to significantly decrease the required LUT values to 265 from about 9200 and FF values to 102 from about 4600 for the hardware implementation. We also highlight that we do not need any additional tricks such as NTT for field multiplications. We also push the theoretical boundaries of the generalized subfield construction to see how much small finite fields we can use, examine the arithmetization complexity, and discuss its applicability to other ZK-friendly hash functions.