Efficient Encryption from Random Quasi-Cyclic Codes

Carlos Aguilar, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, and Gilles Zémor

Abstract

We propose a framework for constructing efficient code-based encryption schemes from codes that do not hide any structure in their public matrix. The framework is in the spirit of the schemes first proposed by Alekhnovich in 2003 and based on the difficulty of decoding random linear codes from random errors of low weight. We depart somewhat from Aleknovich's approach and propose an encryption scheme based on the difficulty of decoding random quasi-cyclic codes. We propose two new cryptosystems instantiated within our framework: the Hamming Quasi-Cyclic cryptosystem (HQC), based on the Hamming metric, and the Rank Quasi-Cyclic cryptosystem (RQC), based on the rank metric. We give a security proof, which reduces the IND-CPA security of our systems to a decisional version of the well known problem of decoding random families of quasi-cyclic codes for the Hamming and rank metrics (the respective QCSD and RQCSD problems). We also provide an analysis of the decryption failure probability of our scheme in the Hamming metric case: for the rank metric there is no decryption failure. Our schemes benefit from a very fast decryption algorithm together with small key sizes of only a few thousand bits. The cryptosystems are very efficient for low encryption rates and are very well suited to key exchange and authentication. Asymptotically, for $\lambda$ the security parameter, the public key sizes are respectively in $\mathcal{O}({\lambda}^2)$ for HQC and in $\mathcal{O}(\lambda^{\frac{4}{3}})$ for RQC. Practical parameter compares well to systems based on ring-LPN or the recent MDPC system.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Code-based CryptographyPublic-Key EncryptionPost-Quantum CryptographyProvable Security
Contact author(s)
jean-christophe deneuville @ unilim fr
History
Short URL
https://ia.cr/2016/1194

CC BY

BibTeX

@misc{cryptoeprint:2016/1194,
author = {Carlos Aguilar and Olivier Blazy and Jean-Christophe Deneuville and Philippe Gaborit and Gilles Zémor},
title = {Efficient Encryption from Random Quasi-Cyclic Codes},
howpublished = {Cryptology ePrint Archive, Paper 2016/1194},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/1194}},
url = {https://eprint.iacr.org/2016/1194}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.