Paper 2026/2159

Batch IT-MAC: Program the Randomness in Succinct VOLE

Abstract

Many cryptographic protocols rely on affine message authentication tags of the form \({\boldsymbol\sigma}=\Delta{\boldsymbol x}+{\boldsymbol k}\), the batch version of information-theoretic MAC. Generating the tags for a long message vector typically requires communication linear in its length. Recent chosen-input VOLE protocols achieve succinct communication, but do not allow the authenticator’s key $k$ to be fixed in advance. We introduce $\mathit{batch\text{-}MAC}$, a primitive that authenticates a chosen message vector in two messages while allowing the authenticator’s key vector to be generated beforehand from a short seed. For a vector of length \(m\), we construct batch-MACs with \(O(m^{2/3}\lambda)\) communication under the decisional composite residuosity (DCR) assumption and \(\operatorname{poly}(\log m,\lambda)\) communication under the learning with errors assumption. Both constructions require a common reference string (CRS). We find applications in constrained pseudorandom functions, 2-message 2PC, and succinct zero-knowledge arguments.