International Association
for Cryptologic Research

Lattice trapdoor algorithms allow us to sample hard random lattices together with their trapdoors, given which short preimage vectors of any given target images can be sampled efficiently. This enables a wide range of advanced cryptographic primitives, such as attribute-based encryption and homomorphic signatures. To obtain thresholdised variants of these primitives, one approach is to design a non-interactive mechanism to distribute the preimage sampling process. While generic tools such as the universal thresholdiser exist for this task, they require homomorphically sampling from Gaussian distributions which is non-trivial. We ask: can we distribute lattice trapdoors non-interactively and algebraically? We present a natural approach to this problem: splitting full trapdoors into partial trapdoors for different lower-rank sublattices that allow the local sampling of short sublattice vectors, using essentially only linear algebra but not generic tools such as fully homomorphic encryption or multiparty computation. Our partial trapdoor algorithms generate (partial) preimages of dimension linear in the recovery threshold $t$ but otherwise polylogarithmic in the number of shareholders k. Given sufficiently many short sublattice vectors, these can then be combined to yield short vectors in the original lattice. This process can be repeated an unbounded polynomial number of times without needing the (full) trapdoor owner to intervene. A wide range of lattice-trapdoor-based primitives can be thresholdised non-interactively by simply substituting the trapdoor preimage sampling procedure with our partial analogue. We prove the one-wayness and indistinguishability properties of our construction, against adversaries who are given at most t-1 partial trapdoors, from the κ-SIS and κ-LWE assumptions, which were previously shown to be implied by the plain SIS and LWE assumptions, respectively. The security proofs extend naturally to the ring or module settings under the respective analogues of these assumptions.

We present a simple IND-CCA lattice-based threshold KEM. At a high level, our design is based on the BCHK transform (Canetti et al., EUROCRYPT 2004), which we adapt to the lattice setting by combining it with the FO transform (Fujisaki and Okamoto, PKC 1999) in order to achieve decryption consistency. As for the BCHK transform, our construction requires a threshold identity-based encryption (TIBE) scheme with suitable properties. We build such an IBE by combining the ABB IBE (Agrawal, Boneh, Boyen, EUROCRYPT 2010) with recent advances in lattice threshold cryptography, such as the threshold-friendly signature Plover (Esgin et al., EUROCRYPT 2024) and a variant of the Threshold Raccoon scheme (Katsumata et al., CRYPTO 2024). The security proof of our scheme relies on a new assumption which we call the Coset-Hint-MLWE assumption, and which is a natural generalisation of the Hint-MLWE assumption (Kim et al., CRYPTO 2023). We prove the hardness of Coset-Hint-MLWE under standard assumptions. We believe this new assumption may be of independent interest. Unlike prior works on IND-CCA lattice-based threshold KEMs, our construction only relies on simple algorithmic tools and does not use heavy machinery such as multi-party computation or threshold fully homomorphic encryption.

Recent works on lattice-based extractable polynomial commitments can be grouped into two classes: (i) non-interactive constructions that stem from the functional commitment by Albrecht, Cini, Lai, Malavolta and Thyagarajan (CRYPTO 2022), and (ii) lattice adaptations of the Bulletproofs protocol (S&P 2018). The former class enjoys security in the standard model, albeit a knowledge assumption is desired. In contrast, Bulletproof-like protocols can be made secure under falsifiable assumptions, but due to technical limitations regarding subtractive sets, they only offer inverse-polynomial soundness error. This issue becomes particularly problematic when transforming these protocols to the non-interactive setting using the Fiat-Shamir paradigm. In this work, we propose the first lattice-based non-interactive extractable polynomial commitment scheme which achieves polylogarithmic proof size and verifier runtime (in the length of the committed message) under standard assumptions. At the core of our work lies a new tree-based commitment scheme, along with an efficient proof of polynomial evaluation inspired by FRI (ICALP 2018). Natively, the construction is secure under a “multi-instance version” of the Power-Ring BASIS assumption (Eprint 2023/846). We then base security on the Module-SIS assumption by introducing several re-randomisation techniques which can be of independent interest.