Semi-Compressed CRYSTALS-Kyber

• URL: http://arxiv.org/abs/2407.17684v1
• Date: Thu, 25 Jul 2024 00:54:22 GMT
• Title: Semi-Compressed CRYSTALS-Kyber
• Authors: Shuiyin Liu, Amin Sakzad,
• Abstract summary: 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.
• Score: 4.317605401561789
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we investigate the communication overhead of the Kyber, which has recently been standardized by the National Institute of Standards and Technology (NIST). Given the same decryption failure rate (DFR) and security argument, 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. First, we prove that the Lloyd-Max quantization is optimal to minimize the decryption decoding noise. The original Kyber compression function is not optimal. Second, we propose an encoding scheme, which combines Pulse-Amplitude Modulation (PAM), Gray mapping, and a binary error correcting code. An explicit expression for the DFR is derived. The minimum possible communication overhead is also derived. Finally, we demonstrate 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 (e.g., 2.5 AES keys) in a single ciphertext.

Related papers

• Reducing Ciphertext and Key Sizes for MLWE-Based Cryptosystems [21.252957852477092]
  We show that it is possible to reduce the sizes of ciphertexts and secret keys by 25% for the parameter set Kyber1024. For a single Kyber encryption block used to share a 256-bit AES key, we furthermore show that reductions in ciphertext size 39% and 33% are possible for Kyber1024 and Kyber512.
  arXiv  Detail & Related papers  (2025-02-03T13:33:27Z)
• Efficient Layered New Bit-Flipping QC-MDPC Decoder for BIKE Post-Quantum Cryptography [6.583725235299022]
  Bit Flipping Key Encapsulation mechanism is a candidate of post-quantum cryptography standardization. New bit-flipping (BF) decoding algorithm decides the BF threshold by an affine function with high-precision coefficients. This paper proposes a column-layered decoder for the new BIKE BF decoding algorithm to substantially reduce the memory requirement.
  arXiv  Detail & Related papers  (2024-12-16T17:23:41Z)
• The Road to Near-Capacity CV-QKD Reconciliation: An FEC-Agnostic Design [53.67135680812675]
  A new codeword-based QKD reconciliation scheme is proposed. Both the authenticated classical channel (ClC) and the quantum channel (QuC) are protected by separate forward error correction (FEC) coding schemes. The proposed system makes QKD reconciliation compatible with a wide range of FEC schemes.
  arXiv  Detail & Related papers  (2024-03-24T14:47:08Z)
• Progressive-Proximity Bit-Flipping for Decoding Surface Codes [8.971989179518214]
  Topological quantum codes, such as toric and surface codes, are excellent candidates for hardware implementation. Existing decoders often fall short of meeting requirements such as having low computational complexity. We propose a novel bit-flipping (BF) decoder tailored for toric and surface codes.
  arXiv  Detail & Related papers  (2024-02-24T22:38:05Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [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)
• Graph Neural Networks for Channel Decoding [71.15576353630667]
  We showcase competitive decoding performance for various coding schemes, such as low-density parity-check (LDPC) and BCH codes. The idea is to let a neural network (NN) learn a generalized message passing algorithm over a given graph. We benchmark our proposed decoder against state-of-the-art in conventional channel decoding as well as against recent deep learning-based results.
  arXiv  Detail & Related papers  (2022-07-29T15:29:18Z)
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes [61.411482146110984]
  We introduce decoders that are both fast and accurate, and can be used with a wide class of quantum error correction codes. Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC. We find that the decoders led to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code.
  arXiv  Detail & Related papers  (2022-03-09T18:48:54Z)
• Dense Coding with Locality Restriction for Decoder: Quantum Encoders vs. Super-Quantum Encoders [67.12391801199688]
  We investigate dense coding by imposing various locality restrictions to our decoder. In this task, the sender Alice and the receiver Bob share an entangled state.
  arXiv  Detail & Related papers  (2021-09-26T07:29:54Z)
• 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)
• FFConv: Fast Factorized Neural Network Inference on Encrypted Data [9.868787266501036]
  We propose a low-rank factorization method called FFConv to unify convolution and ciphertext packing. Compared to prior art LoLa and Falcon, our method reduces the inference latency by up to 87% and 12%, respectively.
  arXiv  Detail & Related papers  (2021-02-06T03:10:13Z)

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.