Ouroboros An efficient and provably secure KEM family - ENAC - École nationale de l'aviation civile Accéder directement au contenu
Article Dans Une Revue IEEE Transactions on Information Theory Année : 2022

Ouroboros An efficient and provably secure KEM family


In this paper we introduce Ouroboros, a new family of Key Exchange protocols based on coding theory. The protocols propose a middle ground between the cryptosystems based on QC-MDPC codes, which feature small parameter sizes, but have a security reduction to two problems: the syndrome decoding problem and the indistinguishability of the code, and the HQC protocol, which features bigger parameters but has a security reduction to the syndrome decoding problem only. Ouroboros features a reduction to the syndrome decoding problem with only a small overhead compared to the QC-MDPC based cryptosystems. The approach is based on an ideal structure and also works for the rank metric. This yields a simple, secure and efficient approach for key exchange, the Ouroboros family of protocols. For the Hamming metric we obtain the same type of parameters (and almost the same simple decoding) as for MDPC based cryptosystems, but with a security reduction to decoding random quasi-cyclic codes in the Random Oracle Model. This represents a reduction of up to 38% on the public key size compared to HQC, for the most secure parameters. For the rank metric, we obtain better parameters than for RQC, saving up to 31% on the public key for the most secure set of parameters, using non homogeneous errors in Ouroboros. In this full version, the protocol and decoding algorithm have been slightly improved, additional details are given in the security proof, and the protocol is fully described for the rank metric
Fichier non déposé

Dates et versions

hal-03679752 , version 1 (27-05-2022)



Nicolas Aragon, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Gilles Zemor. Ouroboros An efficient and provably secure KEM family. IEEE Transactions on Information Theory, 2022, pp.1-1. ⟨10.1109/TIT.2022.3168439⟩. ⟨hal-03679752⟩
48 Consultations
0 Téléchargements



Gmail Facebook Twitter LinkedIn More