eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2016/1058

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

Markku-Juhani O. Saarinen


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.

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


      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.