Paper 2024/2073

Succinct Homomorphic MACs from Groups and Applications

Abstract

Homomorphic message authentication codes (HMACs) allow users to authenticate data using a shared secret key, while supporting computation over authenticated data. Given data $(m_1, \ldots, m_n)$ and their tags $(\sigma_1, \ldots, \sigma_n)$, anyone can evaluate a circuit $C$ on the data and tags to produce a succinct tag authenticating the output $C(m_1, \ldots, m_n)$. Importantly, tags remain succinc -- of size polynomial in the security parameter $\lambda$ -- regardless of the size of $C$. This work introduces an enhanced variant of HMACs called algebraic HMAC (aHMAC), in which all tags (input and output) take the form $\Delta \cdot m + K$, as in standard information-theoretic MACs. We construct an aHMAC from group-based assumptions, including variants of the DDH and DCR assumptions, and use it to obtain group-based constructions of several cryptographic primitives: - Succinct CDS for circuits. For any $P: [N]^k \to [N]$ represented by circuit, we obtain a Conditional Disclosure of Secrets protocol with poly$(\lambda, k, \log N )$ communication. - Succinct PSM for simple programs. For any $P:[N]^k \to [N]$ represented by a truth-table or shallow branching program, we obtain a Private Simultaneous Messages protocol or a garbling scheme with poly$(\lambda, k, \log N )$ communication. - Constrained PRFs for circuits. We obtain the first group-based constrained pseudorandom functions for general circuits, improving over a previous construction for NC1 circuits. Prior to our work, these applications could only be obtained from lattice assumptions or indistinguishability obfuscation.

Note: April, 21, 2025: - changed titile (from "Succinct Partial Garbling from Groups and Applications"); - revised leveled constructions based on DDH instead of P-DDH in Sec. 3.4; - added connections between aHMAC and standard HMAC in Sec. 3.5; - added lattice constructions for aHMAC in Sec. A;