Paper 2024/1271

AES-based Multi-instance TCCR Hash with High Security, and Applications

Abstract

Correlation robust hash function (CRHF) is an important class of building blocks that have found applications in many cryptographic applications, including various protocols for zero-knowledge (ZK) proof, circuit garbling, vector oblivious linear evaluation (VOLE), etc. It offers more efficient instantiations from block ciphers as compared to cryptographic hash functions like SHA-3. State-of-the-art instantiations work provide near-optimal security in the ideal cipher model that can in turn be efficiently instantiated using AES, which is standardized and provides instruction-level acceleration. However, since AES is only available for 128-bit block size, they cannot be generalized beyond 128-bit security while enjoying the same level of efficiency. In this paper, we fill this gap by constructing a new multi-instance tweakable circular CRHF (miTCCR) from AES, supporting up to 256-bit security. Since miTCCR is the most general notion of CRHF, it directly leads to numerous applications. 1. The state-of-the-art optimization of GGM tree (Eurocrypt'23), which builds on circular CRHF as a black box, can be instantiated with our construction, boosting its security strength, as well as the security of the VOLE-ZK protocols building on top, from 128 bits to 256 bits. 2. With a new extractability notion, we use the miTCCR hash to instantiate the leaf commitment in an all-but-one vector commitment scheme, which is a core primitive of post-quantum digital signature schemes and ZK in the VOLE-in-the-Head framework. Experiments show that our technique could reduce the end-to-end signing/verification time of FAEST (resp. FAEST-EM) by 13.1%~40.4% / 15.2%~46.4% (resp. 1.5%~25.0% / 2.9%~24.2%). 3. The multi-instance-secure half-gates garbling scheme (Crypto'20) uses miTCCR as a black box. Our construction can strengthen its security as well as the security of constant-round multiparty computation building on half-gates to 246-bit.