MinRank Gabidulin encryption scheme on matrix codes

• URL: http://arxiv.org/abs/2405.16539v2
• Date: Thu, 17 Oct 2024 08:03:24 GMT
• Title: MinRank Gabidulin encryption scheme on matrix codes
• Authors: Nicolas Aragon, Alain Couvreur, Victor Dyseryn, Philippe Gaborit, Adrien Vinçotte,
• Abstract summary: We propose a generalization of the McEliece scheme and the Niederreiter frame to matrix codes and the MinRank problem. Our new approach permits to achieve better trade-off between ciphertexts and public key than the classical McEliece scheme.
• Score: 6.471199354529622
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The McEliece scheme is a generic frame which allows to use any error correcting code of which there exists an efficient decoding algorithm to design an encryption scheme by hiding the generator matrix code. Similarly, the Niederreiter frame is the dual version of the McEliece scheme, and achieves smaller ciphertexts. We propose a generalization of the McEliece frame and the Niederreiter frame to matrix codes and the MinRank problem, that we apply to Gabidulin matrix codes (Gabidulin rank codes considered as matrix codes). The masking we consider consists in starting from a rank code C, to consider a matrix version of C and to concatenate a certain number of rows and columns to the matrix codes version of the rank code C and then apply to an isometry for matric codes. The security of the schemes relies on the MinRank problem to decrypt a ciphertext, and the structural security of the scheme relies on a new problem EGMC-Indistinguishability problem that we introduce and that we study in detail. The main structural attack that we propose consists in trying to recover the masked linearity over the extension field which is lost during the masking process. Overall, starting from Gabidulin codes we obtain a very appealing tradeoff between the size of ciphertext and the size of the public key. For 128b of security we propose parameters ranging from ciphertext of size 65 B (and public keys of size 98 kB) to ciphertext of size 138B (and public key of size 41 kB). Our new approach permits to achieve better trade-off between ciphertexts and public key than the classical McEliece scheme. Our new approach permits to obtain an alternative scheme to the classic McEliece scheme, to obtain very small ciphertexts, with moreover smaller public keys than in the classic McEliece scheme. For 256 bits of security, we can obtain ciphertext as low as 119B, or public key as low as 87kB.

Related papers

• High Memory Masked Convolutional Codes for PQC [0.0]
  This paper presents a novel post-quantum cryptosystem based on high-memory masked convolutional codes.<n>It supports arbitrary plaintext lengths with linear-time decryption and uniform per-bit computational cost.<n>The scheme achieves cryptanalytic margins exceeding those of the classic McEliece system by factors greater than 2100.
  arXiv  Detail & Related papers  (2025-10-17T10:39:20Z)
• The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head [2.123778388986574]
  We introduce two new problems: the Matrix Subcode Equivalence Problem and the Matrix Code Permuted Kernel Problem.<n>We apply the MPCitH paradigm to build a signature scheme.<n>We obtain a signature size of $approx$ 4 800 Bytes, with a public key of $approx$ 275 Bytes.
  arXiv  Detail & Related papers  (2025-07-21T08:33:24Z)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• Post-Quantum Homomorphic Encryption: A Case for Code-Based Alternatives [0.6749750044497732]
  Homomorphic Encryption (HE) allows secure and privacy-protected computation on encrypted data without the need to decrypt it. Most of the current PQHE algorithms are secured by lattice-based problems. Code-based encryption is a novel way to diversify post-quantum algorithms.
  arXiv  Detail & Related papers  (2025-03-28T06:49:22Z)
• Cryptanalysis via Machine Learning Based Information Theoretic Metrics [58.96805474751668]
  We propose two novel applications of machine learning (ML) algorithms to perform cryptanalysis on any cryptosystem. These algorithms can be readily applied in an audit setting to evaluate the robustness of a cryptosystem. We show that our classification model correctly identifies the encryption schemes that are not IND-CPA secure, such as DES, RSA, and AES ECB, with high accuracy.
  arXiv  Detail & Related papers  (2025-01-25T04:53:36Z)
• Lattice-Based Vulnerabilities in Lee Metric Post-Quantum Cryptosystems [3.277820036565198]
  Post-quantum cryptography has gained attention due to the need for secure cryptographic systems in the face of quantum computing. We consider a generic Lee metric based McEliece type cryptosystem and evaluate its security against lattice-based attacks.
  arXiv  Detail & Related papers  (2024-09-24T12:21:33Z)
• Semi-Compressed CRYSTALS-Kyber [4.317605401561789]
  We show it is feasible to reduce the communication overhead of the Kyber by 54%. The improvement is based on two technologies: ciphertext quantization and plaintext encoding. We show that with the Lloyd-Max quantization, 8-PAM, Gray mapping, and a shortened binary BCH(768,638,13) code, the proposed scheme encapsulates 638 bits in a single ciphertext.
  arXiv  Detail & Related papers  (2024-07-25T00:54:22Z)
• The syzygy distinguisher [0.0]
  We present a new distinguisher for alternant and hence Goppa codes, whose complexity is subexponential in the error-correcting capability. In particular, it applies to the codes used in the Classic McEliece candidate for postquantum cryptography standardization.
  arXiv  Detail & Related papers  (2024-07-22T15:42:06Z)
• A Machine Learning-Based Framework for Assessing Cryptographic Indistinguishability of Lightweight Block Ciphers [1.5953412143328967]
  Indistinguishability is a fundamental principle of cryptographic security, crucial for securing data transmitted between Internet of Things (IoT) devices. This research investigates the ability of machine learning (ML) in assessing indistinguishability property in encryption systems. We introduce MIND-Crypt, a novel ML-based framework designed to assess the cryptographic indistinguishability of lightweight block ciphers.
  arXiv  Detail & Related papers  (2024-05-30T04:40:13Z)
• CodeChameleon: Personalized Encryption Framework for Jailbreaking Large Language Models [49.60006012946767]
  We propose CodeChameleon, a novel jailbreak framework based on personalized encryption tactics. We conduct extensive experiments on 7 Large Language Models, achieving state-of-the-art average Attack Success Rate (ASR) Remarkably, our method achieves an 86.6% ASR on GPT-4-1106.
  arXiv  Detail & Related papers  (2024-02-26T16:35:59Z)
• Bit-flipping Decoder Failure Rate Estimation for (v,w)-regular Codes [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder. We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Lightweight Public Key Encryption in Post-Quantum Computing Era [0.0]
  Confidentiality in our digital world is based on the security of cryptographic algorithms. In the course of technological progress with quantum computers, the protective function of common encryption algorithms is threatened. Our concept describes the transformation of a classical asymmetric encryption method to a modern complexity class.
  arXiv  Detail & Related papers  (2023-11-24T21:06:42Z)
• A tiny public key scheme based on Niederreiter Cryptosystem [1.1633929083694385]
  This article proposes a code-based public key cryptography scheme that is both simple and implementable. The key length for the primary parameters of the McEliece cryptosystem ranges from 18 to 500 bits. The security of this system is at least as strong as the security of the Niederreiter cryptosystem.
  arXiv  Detail & Related papers  (2023-10-10T15:50:18Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels. RM codes only admit limited sets of rates. Efficient decoders are available for RM codes at finite lengths.
  arXiv  Detail & Related papers  (2023-01-16T04:11:14Z)
• Recovering AES Keys with a Deep Cold Boot Attack [91.22679787578438]
  Cold boot attacks inspect the corrupted random access memory soon after the power has been shut down. In this work, we combine a novel cryptographic variant of a deep error correcting code technique with a modified SAT solver scheme to apply the attack on AES keys. Our results show that our methods outperform the state of the art attack methods by a very large margin.
  arXiv  Detail & Related papers  (2021-06-09T07:57:01Z)
• Sparsifying Parity-Check Matrices [60.28601275219819]
  We consider the problem of minimizing the number of one-entries in parity-check matrices. In the maximum-likelihood (ML) decoding method, the number of ones in PCMs is directly related to the time required to decode messages. We propose a simple matrix row manipulation which alters the PCM, but not the code itself.
  arXiv  Detail & Related papers  (2020-05-08T05:51:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.