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 $$ and their tags $$, anyone can evaluate a circuit $$ on the data and tags to produce a succinct tag authenticating the output $$. Importantly, tags remain succinc -- of size polynomial in the security parameter $$ -- regardless of the size of $$. This work introduces an enhanced variant of HMACs called algebraic HMAC (aHMAC), in which all tags (input and output) take the form $$, 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 $$ represented by circuit, we obtain a Conditional Disclosure of Secrets protocol with poly$$ communication. - Succinct PSM for simple programs. For any $$ represented by a truth-table or shallow branching program, we obtain a Private Simultaneous Messages protocol or a garbling scheme with poly$$ 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;