Paper 2024/1271

AES-based CCR Hash with High Security and Its Application to Zero-Knowledge Proofs

Abstract

The recent VOLE-based interactive zero-knowledge (VOLE-ZK) protocols along with non-interactive zero-knowledge (NIZK) proofs based on MPC-in-the-Head (MPCitH) and VOLE-in-the-Head (VOLEitH) extensively utilize the commitment schemes, which adopt a circular correlation robust (CCR) hash function as the core primitive. Nevertheless, the state-of-the-art CCR hash construction by Guo et al. (S&P'20), building from random permutations, can only provide 128-bit security, when it is instantiated from AES. This brings about a gap between AES-based CCR hash function and high security (beyond 128-bit security). In this paper, we fill this gap by constructing a new CCR hash function from AES, supporting three security levels (i.e., 128, 192 and 256). Using the AES-based CCR hash function, we present an all-but-one vector commitment (AVC) scheme, which constitutes a computationally intensive part of the NIZK proofs from MPCitH and VOLEitH, where these NIZK proofs can in turn be transformed into the promising post-quantum signature candidates. Furthermore, we obtain an efficient VOLE-ZK protocol with security levels higher than 128 from the CCR hash function. Our benchmark results show that the AES-based CCR hash function has a comparable performance with CCR hash functions based on Rijndael with larger block sizes, which is not standardized and has a limited application range. In the AVC context, the expensive commitment component instantiated with our AES-based CCR hash function improves the running time by a factor of $7 \sim 30 \times$, compared to the SHA3-based instantiation used in the recent post-quantum signature algorithm FAEST.