ENSL/CWI/KCL/IRISA Joint Online Cryptography Seminars
  • iCal
  • Free Slots
  • ENS Lyon
  • CWI Amsterdam
  • King's College London
  • IRISA

Mon, 14 Nov 2022

  • Mon, 14 Nov 2022 13:00 Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs by Thibauld Feneuil (CryptoExperts)

    In this talk, I will present a new zero-knowledge proof of knowledge for the syndrome decoding (SD) problem on random linear codes. Instead of using permutations like most of the existing protocols, we rely on the MPC-in-the-head paradigm in which we reduce the task of proving the low Hamming weight of the SD solution to proving some relations between specific polynomials. Specifically, we propose a 5-round zero-knowledge protocol that proves the knowledge of a vector x such that $y=Hx$ and $wt(x)\leq w$ and which achieves a soundness error close to $1/N$ for an arbitrary $N$.

    While turning this protocol into a signature scheme, we achieve a signature size of 11-12 KB for 128-bit security when relying on the hardness of the SD problem on binary fields. Using larger fields (like $\mathbb{F}_{256}$), we can produce fast signatures of around 8 KB. This allows us to outperform Picnic3 and be competitive with $\text{SPHINCS}^{+}$. Since the security relies on the hardness of the syndrome decoding problem for random linear codes which is known to be NP-hard and for which the cryptanalysis state of the art has been stable for many years, it results in a conservative signature scheme. Moreover, our scheme outperforms all the former code-based signature schemes for the common “signature size + public key size” metric.

    Joint work with Antoine Joux and Matthieu Rivain.

    Speaker Bio: ⯆

    Thibauld Feneuil is a PhD student at CryptoExperts & Sorbonne University (France). He is working on zero-knowledge proofs in post-quantum cryptography.

    Venue: Online