Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on the Falcon signature scheme

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

Standard

Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on the Falcon signature scheme. / Karmakar, Angshuman; Roy, Sujoy Sinha; Vercauteren, Frederik; Verbauwhede, Ingrid.

Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019. Association for Computing Machinery (ACM), 2019. p. 88:1-88:6 88 (Proceedings - Design Automation Conference).

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

Harvard

Karmakar, A, Roy, SS, Vercauteren, F & Verbauwhede, I 2019, Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on the Falcon signature scheme. in Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019., 88, Proceedings - Design Automation Conference, Association for Computing Machinery (ACM), pp. 88:1-88:6, the 56th Annual Design Automation Conference 2019, Las Vegas, NV, United States, 2/06/19. https://doi.org/10.1145/3316781.3317887

APA

Karmakar, A., Roy, S. S., Vercauteren, F., & Verbauwhede, I. (2019). Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on the Falcon signature scheme. In Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019 (pp. 88:1-88:6). [88] (Proceedings - Design Automation Conference). Association for Computing Machinery (ACM). https://doi.org/10.1145/3316781.3317887

Vancouver

Karmakar A, Roy SS, Vercauteren F, Verbauwhede I. Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on the Falcon signature scheme. In Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019. Association for Computing Machinery (ACM). 2019. p. 88:1-88:6. 88. (Proceedings - Design Automation Conference). https://doi.org/10.1145/3316781.3317887

Author

Karmakar, Angshuman ; Roy, Sujoy Sinha ; Vercauteren, Frederik ; Verbauwhede, Ingrid. / Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on the Falcon signature scheme. Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019. Association for Computing Machinery (ACM), 2019. pp. 88:1-88:6 (Proceedings - Design Automation Conference).

Bibtex

@inproceedings{43615c1c7066431380616c88973566f3,
title = "Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on the Falcon signature scheme",
abstract = "Sampling from a discrete Gaussian distribution has applications in lattice-based post-quantum cryptography. Several efficient solutions have been proposed in recent years. However, making a Gaussian sampler secure against timing attacks turned out to be a challenging research problem. In this work, we present a toolchain to instantiate an efficient constant-time discrete Gaussian sampler of arbitrary standard deviation and precision. We observe an interesting property of the mapping from input random bit strings to samples during a Knuth-Yao sampling algorithm and propose an efficient way of minimizing the Boolean expressions for the mapping. Our minimization approach results in up to 37% faster discrete Gaussian sampling compared to the previous work. Finally, we apply our optimized and secure Gaussian sampler in the lattice-based digital signature algorithm Falcon, which is a NIST submission, and provide experimental evidence that the overall performance of the signing algorithm degrades by at most 33% only due to the additional overhead of 'constant-time' sampling, including the 60% overhead of random number generation. Breaking a general belief, our results indirectly show that the use of discrete Gaussian samples in digital signature algorithms would be beneficial.",
keywords = "Discrete Gaussian, Constant-time, Boolean minimization, Learning with errors",
author = "Angshuman Karmakar and Roy, {Sujoy Sinha} and Frederik Vercauteren and Ingrid Verbauwhede",
year = "2019",
month = jun,
day = "2",
doi = "10.1145/3316781.3317887",
language = "English",
series = "Proceedings - Design Automation Conference",
publisher = "Association for Computing Machinery (ACM)",
pages = "88:1--88:6",
booktitle = "Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019",
address = "United States",
note = "the 56th Annual Design Automation Conference 2019 ; Conference date: 02-06-2019 Through 06-06-2019",

}

RIS

TY - GEN

T1 - Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on the Falcon signature scheme

AU - Karmakar, Angshuman

AU - Roy, Sujoy Sinha

AU - Vercauteren, Frederik

AU - Verbauwhede, Ingrid

PY - 2019/6/2

Y1 - 2019/6/2

N2 - Sampling from a discrete Gaussian distribution has applications in lattice-based post-quantum cryptography. Several efficient solutions have been proposed in recent years. However, making a Gaussian sampler secure against timing attacks turned out to be a challenging research problem. In this work, we present a toolchain to instantiate an efficient constant-time discrete Gaussian sampler of arbitrary standard deviation and precision. We observe an interesting property of the mapping from input random bit strings to samples during a Knuth-Yao sampling algorithm and propose an efficient way of minimizing the Boolean expressions for the mapping. Our minimization approach results in up to 37% faster discrete Gaussian sampling compared to the previous work. Finally, we apply our optimized and secure Gaussian sampler in the lattice-based digital signature algorithm Falcon, which is a NIST submission, and provide experimental evidence that the overall performance of the signing algorithm degrades by at most 33% only due to the additional overhead of 'constant-time' sampling, including the 60% overhead of random number generation. Breaking a general belief, our results indirectly show that the use of discrete Gaussian samples in digital signature algorithms would be beneficial.

AB - Sampling from a discrete Gaussian distribution has applications in lattice-based post-quantum cryptography. Several efficient solutions have been proposed in recent years. However, making a Gaussian sampler secure against timing attacks turned out to be a challenging research problem. In this work, we present a toolchain to instantiate an efficient constant-time discrete Gaussian sampler of arbitrary standard deviation and precision. We observe an interesting property of the mapping from input random bit strings to samples during a Knuth-Yao sampling algorithm and propose an efficient way of minimizing the Boolean expressions for the mapping. Our minimization approach results in up to 37% faster discrete Gaussian sampling compared to the previous work. Finally, we apply our optimized and secure Gaussian sampler in the lattice-based digital signature algorithm Falcon, which is a NIST submission, and provide experimental evidence that the overall performance of the signing algorithm degrades by at most 33% only due to the additional overhead of 'constant-time' sampling, including the 60% overhead of random number generation. Breaking a general belief, our results indirectly show that the use of discrete Gaussian samples in digital signature algorithms would be beneficial.

KW - Discrete Gaussian

KW - Constant-time

KW - Boolean minimization

KW - Learning with errors

UR - http://www.scopus.com/inward/record.url?scp=85067794007&partnerID=8YFLogxK

U2 - 10.1145/3316781.3317887

DO - 10.1145/3316781.3317887

M3 - Conference contribution

T3 - Proceedings - Design Automation Conference

SP - 88:1-88:6

BT - Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019

PB - Association for Computing Machinery (ACM)

T2 - the 56th Annual Design Automation Conference 2019

Y2 - 2 June 2019 through 6 June 2019

ER -