Paper 2016/1058

Ring-LWE Ciphertext Compression and Error Correction: Tools for Lightweight Post-Quantum Cryptography

Markku-Juhani O. Saarinen

Abstract

Some lattice-based public key cryptosystems allow one to transform ciphertext from one lattice or ring representation to another efficiently and without knowledge of public and private keys. In this work we explore this lattice transformation property from cryptographic engineering viewpoint. We apply ciphertext transformation to compress Ring-LWE ciphertexts and to enable efficient decryption on an ultra-lightweight implementation targets such as Internet of Things, Smart Cards, and RFID applications. Significantly, this can be done without modifying the original encryption procedure or its security parameters. Such flexibility is unique to lattice-based cryptography and may find additional, unique real-life applications. Ciphertext compression can significantly increase the probability of decryption errors. We show that the frequency of such errors can be analyzed, measured and used to derive precise failure bounds for $n$-bit error correction. We introduce XECC, a fast multi-error correcting code that allows constant time implementation in software. We use these tools to construct and explore TRUNC8, a concrete Ring-LWE encryption and authentication system. We analyze its implementation, security, and performance. We show that our lattice compression technique reduces ciphertext size by more than 40% at equivalent security level, while also enabling public key cryptography on previously unreachable ultra-lightweight platforms. The experimental public key encryption and authentication system has been implemented on an 8-bit AVR target, where it easily outperforms elliptic curve and RSA-based proposals at similar security level. Similar results have been obtained with a Cortex M0 implementation. The new decryption code requires only a fraction of the software footprint of previous Ring-LWE implementations with the same encryption parameters, and is well suited for hardware implementation.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Proc. IoTPTS '17, ACM International Workshop on IoT Privacy, Trust, and Security, April 2, 2017, Abu Dhabi, UAE.
DOI
10.1145/3055245.3055254
Keywords
Post-Quantum CryptographyLattice CryptographyRing-LWE EncryptionLightweight Cryptography
Contact author(s)
mjos @ iki fi
History
2017-02-23: last of 7 revisions
2016-11-15: received
See all versions
Short URL
https://ia.cr/2016/1058
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1058,
      author = {Markku-Juhani O.  Saarinen},
      title = {Ring-LWE Ciphertext Compression and Error Correction: Tools for Lightweight Post-Quantum Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1058},
      year = {2016},
      doi = {10.1145/3055245.3055254},
      note = {\url{https://eprint.iacr.org/2016/1058}},
      url = {https://eprint.iacr.org/2016/1058}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.