Paper 2026/1547

Silent Distributed Cryptography for DNFs and Threshold Policies from Lattices

Abstract

We study two central problems in threshold cryptography from lattices: (1)~threshold encryption with silent setup for general thresholds $t \geq 2$, where no post-quantum constructions were previously known, and (2)~threshold fully homomorphic encryption (TFHE) with sublinear parameters, an open problem since the work of Boneh~et~al.\ (CRYPTO~2018). We introduce \emph{$(\alpha,\beta)$-Scaled Linear Secret Sharing Schemes} (LSSS), a relaxation of standard LSSS in which each authorized set~$S$ reconstructs a scaled version of the secret, $\gamma_S \cdot k$, where both the reconstruction coefficients and the set-dependent scaling factor~$\gamma_S$ are bounded over the integers. Unlike prior approaches based on bit decomposition, this preserves the uniform distribution of unauthorized shares. Building on this, we obtain: \begin{itemize} \item \textbf{Distributed monotone-policy encryption with silent setup.} We provide the first post-quantum construction supporting: (i) DNF formulas with fully compact parameters, and (ii) threshold policies with ciphertexts growing as $\tau^6 \cdot \mathsf{poly}(\lambda, \log N)$, where $\tau = \min(t^2,N{-}t)$. Our constructions are proven secure under the decomposed LWE assumption in the random oracle model. If we additionally rely on a common reference string, then the ciphertext size for our threshold policy scheme can be reduced to $\tau^2 \cdot \mathsf{poly}(\lambda, \log N)$ under the Succinct LWE assumption. \item \textbf{Decentralized TFHE with silent setup.} We provide the first \emph{decentralized} TFHE, for DNFs and threshold policies, from the decomposed LWE assumption. Our construction supports homomorphic evaluation of arbitrary circuits, one-round distributed decryption, and silent setup. This was left as an open problem by Boneh~et~al.\ (CRYPTO~2018) and, prior to this work, we did not have any non-trivial construction for decentralized TFHE from any assumption. \item \textbf{Sublinear centralized TFHE from LWE.} We also extend our techniques to \emph{centralized} TFHE. We provide a TFHE scheme under the standard LWE assumption, where all parameters are simultaneously sublinear in $N$ for any threshold $t$ as long as $\min(t^2, N{-}t) = o(N)$. This breaks the $\omega(N)$ barrier that has persisted in the TFHE literature since 2018. \end{itemize}