SPECK: Signatures from Permutation Equivalence of Codes and Kernels

Marco Baldi; Michele Battagliola; Rahmi El Mechri; Paolo Santini; Riccardo Schiavoni; Davide De Zuane

Paper 2025/923

SPECK: Signatures from Permutation Equivalence of Codes and Kernels

Marco Baldi

, Marche Polytechnic University

Michele Battagliola

, Marche Polytechnic University

Rahmi El Mechri

, Marche Polytechnic University

Paolo Santini

, Marche Polytechnic University

Riccardo Schiavoni

, Marche Polytechnic University

Davide De Zuane

, Marche Polytechnic University, IMT School for Advanced Studies

Abstract

The ongoing search for secure post-quantum cryptographic primitives has led to the development of numerous novel digital signature schemes. In this paper we introduce $\mathsf{SPECK}$, a new signature protocol based on the similarities between the Permuted Kernel Problem ($\mathsf{PKP}$) and the Permutation Code Equivalence Problem ($\mathsf{PEP}$). At its core, $\mathsf{SPECK}$ is built on the permutation version of LESS, but introduces a key modification to the commitment step. Indeed, instead of committing to an entire permuted code, the prover commits to a random relaxed $\mathsf{PKP}$ (that we call $\mathsf{PECK}$, Permutation Equivalence of Codes and Kernel) instance by randomly choosing a codeword from a random permutation of the initial code. In this sense, the secret key is used as a trapdoor to solve the committed $\mathsf{PECK}$ instance. The new approach allows for a faster verification that does not involve gaussian elimination, while maintains roughly the same signature size as LESS. We present the $\mathsf{Speck}$ protocol in detail and provide a deep analysis of the security of the new introduced assumptions.

Note: With respect to previous version: benchmark referred ot optimized implementation and minor editorial changes.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Permutation Equivalence Problem Permuted Kernel Problem Post-Quantum Cryptography Fiat-Shamir
Contact author(s): m baldi @ univpm it
m battagliola @ univpm it
r elmechri @ staff univpm it
p santini @ univpm it
r schiavoni @ pm univpm it
davide dezuane @ imtlucca it
History: 2025-12-01: revised; 2025-05-22: received; See all versions
Short URL: https://ia.cr/2025/923
License: CC BY

BibTeX

@misc{cryptoeprint:2025/923,
      author = {Marco Baldi and Michele Battagliola and Rahmi El Mechri and Paolo Santini and Riccardo Schiavoni and Davide De Zuane},
      title = {{SPECK}: Signatures from Permutation Equivalence of Codes and Kernels},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/923},
      year = {2025},
      url = {https://eprint.iacr.org/2025/923}
}