Paper 2025/2307

Computationally Succinct Authentication from DCR: Attribute-Based Laconic Function Evaluation and More

Abstract

We present the first construction of attribute-based laconic function evaluation (AB-LFE) from the decisional composite residuosity (DCR) assumption. This yields the first example of computationally succinct secure computation from a group-based assumption, avoiding reliance on noisy lattice assumptions such as LWE. Our construction builds on recent work in fully homomorphic MACs and homomorphic secret sharing by Ishai, Li and Lin (FOCS 2025) and Meyer, Orlandi, Roy, and Scholl (Crypto 2025), which we extend by constructing a fully homomorphic MAC for packed vector operations, where the evaluation time of one party is independent of the vector length. As applications, we obtain full-fledged laconic function evaluation (LFE) from the combination of DCR and standard LWE, avoiding the need for sub-exponential modulus-to-noise ratio LWE used in previous work. We also obtain the first constrained pseudorandom function whose master evaluation key is succinct in the constraint. These results highlight the unexplored power of group-based cryptography for succinct secure computation.