Paper 2023/525

Error Correction and Ciphertext Quantization in Lattice Cryptography

Daniele Micciancio, UC San Diego
Mark Schultz, UC San Diego
Abstract

Recent work in the design of rate $1 - o(1)$ lattice-based cryptosystems have used two distinct design paradigms, namely replacing the noise-tolerant encoding $m \mapsto (q/2)m$ present in many lattice-based cryptosystems with a more efficient encoding, and post-processing traditional lattice-based ciphertexts with a lossy compression algorithm, using a technique very similar to the technique of ``vector quantization'' within coding theory. We introduce a framework for the design of lattice-based encryption that captures both of these paradigms, and prove information-theoretic rate bounds within this framework. These bounds separate the settings of trivial and non-trivial quantization, and show the impossibility of rate $1 - o(1)$ encryption using both trivial quantization and polynomial modulus. They furthermore put strong limits on the rate of constructions that utilize lattices built by tensoring a lattice of small dimension with $\mathbb{Z}^k$, which is ubiquitous in the literature. We additionally introduce a new cryptosystem, that matches the rate of the highest-rate currently known scheme, while encoding messages with a ``gadget'', which may be useful for constructions of Fully Homomorphic Encryption.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
lattice-based cryptographylweencryption
Contact author(s)
daniele @ eng ucsd edu
mdschultz @ eng ucsd edu
History
2023-04-12: approved
2023-04-11: received
See all versions
Short URL
https://ia.cr/2023/525
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/525,
      author = {Daniele Micciancio and Mark Schultz},
      title = {Error Correction and Ciphertext Quantization in Lattice Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/525},
      year = {2023},
      url = {https://eprint.iacr.org/2023/525}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.