Succinct Homomorphic MACs from Groups and Applications

Homomorphic message authentication codes (HMACs) allow users to authenticate data using a shared secret key, while supporting computation over authenticated data. Given data $\left(m_{1}, \ldots, m_{n}\right)$ and their tags $\left(\sigma_{1}, \ldots, \sigma_{n}\right)$, anyone can evaluate a circuit C on the data and tags to produce a succinct tag authenticating the output $C\left(m_{1}, \ldots, m_{n}\right)$. Importantly, tags remain succinct-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 $\vec{\Delta} \cdot m+\vec{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} \rightarrow[N]$ represented by circuit, we obtain a Conditional Disclosure of Secrets protocol with $\operatorname{poly}(\lambda, k, \log N)$ communication.•Succinct PSM for simple programs. For any $P:[N]^{k} \rightarrow[N]$ represented by a truth-table or shallow branching program, we obtain a Private Simultaneous Messages protocol or a garbling scheme with $\operatorname{poly}(\lambda, k, \log N)$ communication.•Constrained PRFs for circuits. We obtain the first groupbased constrained pseudorandom functions for general circuits, improving over a previous construction for $\mathrm{NC}^{1}$ circuits.Prior to our work, these applications could only be obtained from lattice assumptions or indistinguishability obfuscation.