Laboratoire IMATH

Title :
Threshold Niederreiter : Chosen-Ciphertext Security and Improved Distributed Decoding

Abstract :
Threshold public key encryption is a variant of public key encryption in which multiple participants are required in order to decrypt a ciphertext. Many threshold PKEs already exist in the literature based on multiple assumptions. However, the topic is not well-studied in the realm of code-based cryptography. In 2023, Takahashi, Hashimoto and Ogata were the first authors to present threshold PKEs in this field. Each of their scheme rely on generic conversion to transform the OW-CPA non-threshold Niederreiter cryptosystem into a IND-CCA threshold scheme. However, each of their design either becomes inefficient when the number of participants becomes large, or contains a security flaw. In this talk, we present our own IND-CCA threshold scheme based on the Niederreiter cryptosystem. Its efficiency does not depend on the number of participants. To achieve this, we first formalize our own generic conversion from OW-CPA to IND-CCA, which is a variant of the Naor-Yung conversion. This conversion uses a NIZK proof system that is both simulation sound and straight line extractable. To instantiate the conversion, we build a variant of an existing NIZK proof system for syndrome decoding based on the MPC-in-the-Head paradigm. We also propose improvements for MPC operations that enables the threshold decryption to be more efficient.