Computationally Succinct Authentication from DCR
摘要
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. On the way, we also provide novel constructions of depth-preserving bundled universal circuits. 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 as in previous work. In addition, we 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.