Paper 2026/1854

Distributed Key Generation for NTRU

Abstract

NTRU-based encryption enjoys compact keys and ciphertexts and admits non-interactive distributed decryption, making it an attractive basis for threshold encryption with applications to threshold FHE, threshold signatures, and electronic voting. All known protocols, however, assume a secret key shared by a trusted dealer. The public NTRU key $h = f^{-1}g$ is a nonlinear function of the secret, so distributed key generation (DKG) techniques for LWE-based schemes do not apply, and generic MPC is prohibitively expensive. We present the first dedicated DKG protocol for NTRU. Each party publishes an NTRU sample, defining a joint public key whose secret key is shared multiplicatively, and a multiplicative-to-additive (MtA) conversion yields the additive sharing required for non-interactive decryption. The protocol runs in few rounds and is actively secure with abort. At the heart of our DKG lies the MtA conversion, for which we give two efficient lattice-based certified constructions; one from additively homomorphic NTRU encryption and one from homomorphic secret sharing, both of which may be of independent interest. We demonstrate the protocol by building a threshold variant of NTRU-Encrypt, which we prove secure and instantiate with concrete parameters.