Compact Lattice-Coded (Multi-Recipient) Kyber without CLT Independence Assumption

• URL: http://arxiv.org/abs/2504.17185v2
• Date: Thu, 15 May 2025 03:11:10 GMT
• Title: Compact Lattice-Coded (Multi-Recipient) Kyber without CLT Independence Assumption
• Authors: Shuiyin Liu, Amin Sakzad,
• Abstract summary: This work presents a joint design of encoding and encryption procedures for public key encryptions (PKEs) and key encapsulation mechanism (KEMs) such as Kyber.<n>Our design features two techniques: ciphertext packing and lattice packing.<n>Both DFR and CER are greatly decreased thanks to ciphertext packing and lattice packing.
• Score: 4.317605401561789
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work presents a joint design of encoding and encryption procedures for public key encryptions (PKEs) and key encapsulation mechanism (KEMs) such as Kyber, without relying on the assumption of independent decoding noise components, achieving reductions in both communication overhead (CER) and decryption failure rate (DFR). Our design features two techniques: ciphertext packing and lattice packing. First, we extend the Peikert-Vaikuntanathan-Waters (PVW) method to Kyber: $\ell$ plaintexts are packed into a single ciphertext. This scheme is referred to as P$_\ell$-Kyber. We prove that the P$_\ell$-Kyber is IND-CCA secure under the M-LWE hardness assumption. We show that the decryption decoding noise entries across the $\ell$ plaintexts (also known as layers) are mutually independent. Second, we propose a cross-layer lattice encoding scheme for the P$_\ell$-Kyber, where every $\ell$ cross-layer information symbols are encoded to a lattice point. This way we obtain a \emph{coded} P$_\ell$-Kyber, where the decoding noise entries for each lattice point are mutually independent. Therefore, the DFR analysis does not require the assumption of independence among the decryption decoding noise entries. Both DFR and CER are greatly decreased thanks to ciphertext packing and lattice packing. We demonstrate that with $\ell=24$ and Leech lattice encoder, the proposed coded P$_\ell$-KYBER1024 achieves DFR $<2^{-281}$ and CER $ = 4.6$, i.e., a decrease of CER by $90\%$ compared to KYBER1024.

Related papers

• Secure Multi-Key Homomorphic Encryption with Application to Privacy-Preserving Federated Learning [10.862166653863571]
  We identify a critical security vulnerability in the CDKS scheme when applied to multiparty secure computation tasks.<n>We propose a new scheme, SMHE, which incorporates a novel masking mechanism into the multi-key BFV and CKKS frameworks.<n>We implement a PPFL application using SMHE and demonstrate it provides significantly improved security with only a modest overhead in runtime evaluation.
  arXiv  Detail & Related papers  (2025-06-25T03:28:25Z)
• Fair Data Exchange at Near-Plaintext Efficiency [1.187519459637148]
  We introduce an FDE implementation that achieves near-plaintext speeds and sizes, making fair exchange practical even for gigabyte-scale files.<n>This can reduce transaction fees from roughly $10 to under $0.01 and shorten transaction latency from tens of seconds on down to about a second or less.
  arXiv  Detail & Related papers  (2025-06-17T19:50:25Z)
• Cryptanalysis on Lightweight Verifiable Homomorphic Encryption [7.059472280274008]
  Verifiable Homomorphic Encryption (VHE) is a cryptographic technique that integrates Homocrypt Encryption (HE) with Verifiable Computation (VC)<n>This paper presents efficient attacks that exploit the homomorphic properties of encryption schemes.
  arXiv  Detail & Related papers  (2025-02-18T08:13:10Z)
• Optimal Computational Secret Sharing [51.599517747577266]
  In $(t, n)$-threshold secret sharing, a secret $S$ is distributed among $n$ participants.<n>We present a construction achieving a share size of $tfrac|S|t + |K|t$.
  arXiv  Detail & Related papers  (2025-02-04T23:37:16Z)
• 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)
• Conditional Encryption with Applications to Secure Personalized Password Typo Correction [7.443139252028032]
  We introduce the notion of a conditional encryption scheme as an extension of public key encryption. A conditional encryption scheme for a binary predicate $P$ adds a new conditional encryption algorithm $mathsfCEnc$. We demonstrate how to use conditional encryption to improve the security of personalized password typo correction systems.
  arXiv  Detail & Related papers  (2024-09-10T00:49:40Z)
• 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)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass [72.07642648108849]
  Superposed Decoding is a new decoding algorithm that generates $k$ drafts at the cost of one autoregressive inference pass. Superposed Decoding can be combined with other decoding strategies, resulting in universal coverage gains when scaling inference time compute.
  arXiv  Detail & Related papers  (2024-05-28T17:40:48Z)
• Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information [53.85237314348328]
  We introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) We show that NU-HUNCC is information-theoretic individually secured against an eavesdropper with access to any subset of the links.
  arXiv  Detail & Related papers  (2024-02-13T12:12:39Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04:01Z)
• 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.<n>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)
• Quantum forgery attacks against OTR structures based on Simon's algorithm [3.845166861382186]
  A quantum forgery attack on OTR structure using Simon's algorithm is proposed. A variant of OTR structure (Pr/ost-OTR-Even-Mansour structure) is proposed. It is easy to generate the correct tag of any given message if attacker is allowed to change a single block in it.
  arXiv  Detail & Related papers  (2023-10-01T15:16:43Z)
• Functional Encryption in the Bounded Storage Models [0.0]
  We investigate possibilities in the bounded quantum storage model (BQSM) and the bounded classical storage model (BCSM) In the BQSM, we construct non-interactive functional encryption satisfying information-theoretic simulation based security with $q=O(sqrts/r)$. In the BCSM, we construct non-interactive functional encryption satisfying information-theoretic subexponential simulation based security.
  arXiv  Detail & Related papers  (2023-09-13T03:55:36Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  We study a distributed multi-armed bandit where a client supplies the learner with communication-constrained feedback. We propose a multi-phase bandit algorithm, $mathttUEtext-UCB++$, which matches this lower bound to a minor additive factor.
  arXiv  Detail & Related papers  (2023-04-25T09:31:20Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)

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.