Addressing Side-Channel Vulnerabilities in the Discrete Ziggurat Sampler

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

    Published

    View graph of relations

    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.

    Documents

    • Addressing Side-Channel Vulnerabilities in the Discrete Ziggurat Sampler Camera Ready

      Rights statement: © Springer Nature Switzerland AG 2018. This work is made available online in accordance with the publisher’s policies. Please refer to any applicable terms of use of the publisher.

      Accepted author manuscript, 465 KB, PDF-document

      Embargo ends: 07/12/2019

    DOI

    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

    ID: 157964139