Arithmetic Coding and Blinding for Lattice Cryptography

[coderman]

https://eprint.iacr.org/2016/276

Abstract: In this work we apply information theoretically optimal
arithmetic coding and a number of novel side-channel blinding
countermeasure techniques to create BLZZRD, a practical, compact, and
more quantum-resistant variant of the BLISS Ring-LWE Signature Scheme.
We show how the hash-based random oracle can be modified to be more
secure against quantum preimage attacks while decreasing signature
size at any given security level. Most lattice-based cryptographic
algorithms require non-uniformly distributed ciphertext, signature,
and public/private key data to be stored and transmitted; hence there
is a requirement for compression. Arithmetic Coding offers an
information theoretically optimal compression for stationary and
memoryless sources, such as the discrete Gaussian distributions often
used in Lattice-based cryptography. We show that this technique gives
better signature sizes than the previously proposed advanced
Huffman-based compressors. We further demonstrate that arithmetic
decoding from an uniform source to target distribution is also an
optimal Gaussian sampling method in the sense that a minimal amount of
true random bits is required. Performance of the new Binary Arithmetic
Coding (BAC) sampler is comparable to other mainstream samplers. The
same code, tables, or circuitry can be utilised for both tasks,
eliminating the need for separate sampling and compression components.
We also describe a simple blinding technique that can be applied to
anti-cyclic polynomial multiplication to mask timing- and power
consumption side-channels in ring arithmetic. We further show that
Gaussian sampling can also be blinded by a split-and-permute technique
while reducing the size of required CDF tables.