Paper 2026/1547 Original: eprint.iacr.org/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'18]. We introduce $\textit{$(\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: 1. $\textbf{Silent Threshold and Distributed monotone-policy encryption.}$ We provide the first post-quantum construction supporting: (i) threshold policies with ciphertexts growing as $\tau^{16} \cdot \mathsf{poly}(\lambda, \log N)$, where $\tau = \min(t^2,N{-}t)$, and (ii) DNF formulas with fully compact parameters. 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^4 \cdot \mathsf{poly}(\lambda, \log N)$ under the Succinct LWE assumption. 2. $\textbf{Decentralized TFHE with silent setup.}$ We provide the first $\textit{decentralized}$ TFHE, for threshold policies and DNFs, 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'18] and, prior to this work, we did not have any non-trivial construction for decentralized TFHE from any assumption. 3. $\textbf{Sublinear centralized TFHE from LWE.}$ We also extend our techniques to $\textit{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^{1/6})$. This breaks the $\omega(N)$ barrier that has persisted in the TFHE literature since 2018.