Paolo Santini

Marco Baldi, Massimo Battaglioni, Franco Chiaraluce et al.

In this paper we introduce a variant of the Syndrome Decoding Problem (SDP), that we call Restricted SDP (R-SDP), in which the entries of the searched vector are defined over a subset of the underlying finite field. We prove the NP-completeness of R-SDP, via a reduction from the classical SDP, and describe algorithms which solve such new problem. We study the properties of random codes under this new decoding perspective, in the fashion of traditional coding theory results, and assess the complexity of solving a random R-SDP instance. As a concrete application, we describe how Zero-Knowledge Identification (ZK-ID) schemes based on SDP can be tweaked to rely on R-SDP, and show that this leads to compact public keys as well as significantly reduced communication costs. Thus, these schemes offer an improved basis for the construction of code-based digital signature schemes derived from identification schemes through the well-know Fiat-Shamir transformation.

Violetta Weger, Massimo Battaglioni, Paolo Santini et al.

Information set decoding (ISD) algorithms are the best known procedures to solve the decoding problem for general linear codes. These algorithms are hence used for codes without a visible structure, or for which efficient decoders exploiting the code structure are not known. Classically, ISD algorithms have been studied for codes in the Hamming metric. In this paper we switch from the Hamming metric to the Lee metric, and study ISD algorithms and their complexity for codes measured with the Lee metric over finite rings.

Paolo Santini, Alessandro Barenghi, Gerardo Pelosi et al.

Characterizing the decoding failure rate of iteratively decoded Low- and Moderate-Density Parity Check (LDPC/MDPC) codes is paramount to build cryptosystems based on them, able to achieve indistinguishability under adaptive chosen ciphertext attacks. In this paper, we provide a statistical worst-case analysis of our proposed iterative decoder obtained through a simple modification of the classic in-place bit-flipping decoder. This worst case analysis allows both to derive the worst-case behaviour of an LDPC/MDPC code picked among the family with the same length, rate and number of parity checks, and a code-specific bound on the decoding failure rate. The former result allows us to build a code-based cryptosystem enjoying the $δ$-correctness property required by IND-CCA2 constructions, while the latter result allows us to discard code instances which may have a decoding failure rate significantly different from the average one (i.e., representing weak keys), should they be picked during the key generation procedure.

Paolo Santini, Marco Baldi, Franco Chiaraluce

We consider a one-time digital signature scheme recently proposed by Persichetti and show that a successful key recovery attack can be mounted with limited complexity. The attack we propose exploits a single signature intercepted by the attacker, and relies on a statistical analysis performed over such a signature, followed by information set decoding. We assess the attack complexity and show that a full recovery of the secret key can be performed with a work factor that is far below the claimed security level. The efficiency of the attack is motivated by the sparsity of the signature, which leads to a significant information leakage about the secret key.

Paolo Santini, Marco Baldi, Franco Chiaraluce

Code-based public-key cryptosystems based on QC-LDPC and QC-MDPC codes are promising post-quantum candidates to replace quantum vulnerable classical alternatives. However, a new type of attacks based on Bob's reactions have recently been introduced and appear to significantly reduce the length of the life of any keypair used in these systems. In this paper we estimate the complexity of all known reaction attacks against QC-LDPC and QC-MDPC code-based variants of the McEliece cryptosystem. We also show how the structure of the secret key and, in particular, the secret code rate affect the complexity of these attacks. It follows from our results that QC-LDPC code-based systems can indeed withstand reaction attacks, on condition that some specific decoding algorithms are used and the secret code has a sufficiently high rate.

Marco Baldi, Alessandro Barenghi, Franco Chiaraluce et al.

In this paper we consider a post-quantum digital signature scheme based on low-density generator matrix codes and propose efficient algorithmic solutions for its implementation. We also review all known attacks against this scheme and derive closed-form estimates of their complexity when running over both classical and quantum computers. Based on these estimates, we propose new parametrization for the considered system to achieve given pre-quantum and post-quantum security levels. Finally, we provide and discuss performance benchmarks obtained through a suitably developed and publicly available reference implementation of the considered system.

Marco Baldi, Paolo Santini, Franco Chiaraluce

We propose to use real-valued errors instead of classical bit flipping intentional errors in the McEliece cryptosystem based on moderate-density parity-check (MDPC) codes. This allows to exploit the error correcting capability of these codes to the utmost, by using soft-decision iterative decoding algorithms instead of hard-decision bit flipping decoders. However, soft reliability values resulting from the use of real-valued noise can also be exploited by attackers. We devise new attack procedures aimed at this, and compute the relevant work factors and security levels. We show that, for a fixed security level, these new systems achieve the shortest public key sizes ever reached, with a reduction up to 25% with respect to previous proposals.