Constant-Round Secure Distributed Decoding and HQC Threshold Decryption

Pascal Giorgi; Fabien Laguillaumie; Lucas Ottow; Damien Vergnaud

Paper 2026/946

Constant-Round Secure Distributed Decoding and HQC Threshold Decryption

Pascal Giorgi

, University of Montpellier, Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

Fabien Laguillaumie

, University of Montpellier, Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

Lucas Ottow

, University of Montpellier, Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

Damien Vergnaud

, Laboratoire de Recherche en Informatique de Paris 6, Sorbonne University

Abstract

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 novel techniques for specific multiparty computations in fields of characteristic 2. For distributed Reed-Muller decoding, we develop a majority computing protocol. 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: HQC Threshold cryptography Multi-party computation Reed-Solomon decoding Reed-Muller decoding
Contact author(s): pascal giorgi @ lirmm fr
fabien laguillaumie @ lirmm fr
lucas ottow @ lirmm fr
damien vergnaud @ lip6 fr
History: 2026-05-16: approved; 2026-05-13: received; See all versions
Short URL: https://ia.cr/2026/946
License: CC BY

BibTeX

@misc{cryptoeprint:2026/946,
      author = {Pascal Giorgi and Fabien Laguillaumie and Lucas Ottow and Damien Vergnaud},
      title = {Constant-Round Secure Distributed Decoding and {HQC} Threshold Decryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/946},
      year = {2026},
      url = {https://eprint.iacr.org/2026/946}
}