Addressing Side-Channel Vulnerabilities in the Discrete Ziggurat Sampler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

90 Downloads (Pure)

Abstract

Post-quantum cryptography with lattices typically requires
high precision sampling of vectors with discrete Gaussian distributions. Lattice signatures require large values of the standard deviation parameter, which poses difficult problems in finding a suitable trade-off between throughput performance and memory resources on constrained devices. In this paper, we propose modifications to the Ziggurat method, known to be advantageous with respect to these issues, but problematic due to its inherent rejection-based timing profile. We improve upon information leakage through timing channels significantly and require: only 64-bit unsigned integers, no floating-point arithmetic, no division and no external libraries. Also proposed is a constant-time Gaussian function, possessing all aforementioned advantageous properties. The measures taken to
secure the sampler completely close side-channel vulnerabilities through direct timing of operations and these have no negative implications on its applicability to lattice-based signatures. We demonstrate the improved method with a 128-bit reference implementation, showing that we retain
the sampler's efficiency and decrease memory consumption by a factor of 100. We show that this amounts to memory savings by a factor of almost 5,000, in comparison to an optimised, state-of-the-art implementation of another popular sampling method, based on cumulative distribution tables.
Original languageEnglish
Title of host publication8th International Conference on Security, Privacy, and Applied Cryptography Engineering: Proceedings
PublisherSpringer-Verlag
Pages65-84
ISBN (Electronic)978-3-030-05072-6
ISBN (Print) 978-3-030-05071-9
DOIs
Publication statusPublished - 11 Jan 2019
Event8th International Conference on Security, Privacy, and Applied Cryptography Engineering - Indian Institute of Technology, Kanpur, India
Duration: 15 Dec 201819 Dec 2018
https://space2018.cse.iitk.ac.in/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
ISSN (Electronic)0302-9743

Conference

Conference8th International Conference on Security, Privacy, and Applied Cryptography Engineering
Abbreviated titleSPACE 2018
CountryIndia
CityKanpur
Period15/12/201819/12/2018
Internet address

Fingerprint Dive into the research topics of 'Addressing Side-Channel Vulnerabilities in the Discrete Ziggurat Sampler'. Together they form a unique fingerprint.

Cite this