Constant-Round Secure Distributed Decoding and HQC Threshold Decryption

Threshold public-key encryption schemes enable decryption only with the participation of enough partial secret key holders. In this article, we propose the first dedicated protocol for distributed decryption of HQC ciphertexts. This protocol is perfectly correct and does not leak any information about the shared secret key. This leads to the first threshold cryptosystem based on HQC. To this end, we present protocols for securely decoding shared erroneous words of both Reed-Muller and Reed-Solomon codes. Such decodings require to develop innovative techniques for specific multiparty computations in fields of characteristic 2. For distributed Reed-Muller decoding, we investigate two approaches : one relying on a majority computing protocol and a second one relying on an exaustive search for closest codeword. For distributed Reed-Solomon decoding, we propose a novel protocol for securely solving Padé approximants over shared polynomials. Beyond their immediate application to HQC, our results enable new techniques in secure distributed computation over structured algebraic objects, and may find independent applications in advanced cryptographic protocols.