Efficient Encryption From Random Quasi-Cyclic Codes

DOI10.1109/TIT.2018.2804444MaRDI QIDQ5375555zbMATH OpenOpenAlexWikidataFDO

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

Publication date 14 September 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.05572

Mathematics Subject Classification ID

Cryptography (94A60) Cyclic codes (94B15)

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 $O(lambd{a}^2)$ for HQC and in $O(lambd{a}^{4/3})$ for RQC. Practical parameter compares well to systems based on ring-LPN or the recent MDPC system.

Recommendations

• Efficient implementation of hybrid encryption from coding theory
• Efficient Code Based Hybrid and Deterministic Encryptions in the Standard Model
• Cryptanalysis of a Hash Function Based on Quasi-cyclic Codes
• QC-LDPC code-based cryptography
• Randomized coding of plaintext encryption scheme
• Asymptotically quasi-optimal cryptography
• Niederreiter cryptosystems using quasi-cyclic codes that resist quantum Fourier sampling
• Rerandomizable RCCA Encryption
• Quasi-cyclic codes
• An efficient probabilistic encryption scheme

Cited in

(41)

• Encryption scheme based on expanded Reed-Solomon codes
• Efficient pseudorandom correlation generators from ring-LPN
• A gapless code-based hash proof system based on RQC and its applications
• A practicable timing attack against HQC and its countermeasure
• A rank metric code-based group signature scheme
• Properties of constacyclic codes under the Schur product
• Equivalence and characterizations of linear rank-metric codes based on invariants
• Cryptanalysis of a code-based one-time signature
• Cryptanalysis of a rank-based signature with short public keys
• New rank codes based encryption scheme using partial circulant matrices
• A new decryption failure attack against HQC
• Cryptographic group actions and applications
• Statistical zero-knowledge and analysis of rank-metric zero-knowledge proofs of knowledge
• Designing a Public Key Cryptosystem Based on Quasi-cyclic Subspace Subcodes of Reed-Solomon Codes
• Area-Time Efficient Computation of Niederreiter Encryption on QC-MDPC Codes for Embedded Hardware
• Rank-metric codes and their applications
• A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions
• Cryptanalysis and repair of a Gabidulin code based cryptosystem from ACISP 2018
• Constructions of optimal rank-metric codes from automorphisms of rational function fields
• Towards automating cryptographic hardware implementations: a case study of HQC
• Non-interactive secure computation of inner-product from LPN and LWE
• Analysis of the security of the PSSI problem and cryptanalysis of the Durandal signature scheme
• Correlated pseudorandomness from expand-accumulate codes
• Correlated pseudorandomness from the hardness of quasi-abelian decoding
• Expand-convolute codes for pseudorandom correlation generators from LPN
• SPANSE: combining sparsity with density for efficient one-time code-based digital signatures
• zk-SNARKs from codes with rank metrics
• The hardness of LPN over any integer ring and field for PCG applications
• Post-quantum cryptosystems: open problems and current solutions. Isogeny-based and code-based cryptosystems
• Efficient error-correcting codes for the HQC post-quantum cryptosystem
• Key recovery from side-channel power analysis attacks on non-SIMD HQC decryption
• On generating sets of 2D cyclic codes of length 2ᵏs and corrections to some previous results
• McEliece parameter sets optimized for processing in memory architectures
• On the security of two IKKR-type code-based cryptosystems
• Main approaches in post-quantum cryptography: description, a comparative study
• CPAKE: an identity-binding password authenticated key exchange from quasi-cyclic codes
• FOLEAGE: \(\mathbb{F}_4\)OLE-based multi-party computation for Boolean circuits
• Post-quantum secure ZRTP
• Practical secure delegated linear algebra with trapdoored matrices
• A minrank-based encryption scheme à la Alekhnovich-Regev
• HQC beyond the standard: ciphertext compression and refined DFR analysis

This page was built for publication: Efficient Encryption From Random Quasi-Cyclic Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5375555)