IACR News item: 14 March 2016
Markku-Juhani O. Saarinen
ePrint Report
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.
Additional news items may be found on the IACR news page.