Cryptology ePrint Archive: Report 2016/471

NTRU Modular Lattice Signature Scheme on CUDA GPUs

Wei Dai and John Schanck and Berk Sunar and William Whyte and Zhenfei Zhang

Abstract: In this work we show how to use Graphics Processing Units (GPUs) with Compute Unified Device Architecture (CUDA) to accelerate a lattice based signature scheme, namely, the NTRU modular lattice signature (NTRU-MLS) scheme. Lattice based schemes require operations on large vectors that are perfect candidates for GPU implementations. In addition, similar to most lattice based signature schemes, NTRU-MLS provides transcript security with a rejection sampling technique. With a GPU implementation, we are able to generate many candidates simultaneously, and hence mitigate the performance slowdown from rejection sampling. Our implementation results show that for the original NTRU-MLS parameter sets, we obtain a 2x improvement in the signing speed; for the revised parameter sets, where acceptance rate of rejection sampling is down to around 1%, our implementation can be as much as 47x faster than a CPU implementation.

Category / Keywords: public-key cryptography / NTRU, digital signatures, lattice techniques, CUDA, GPU

Original Publication (with minor differences): 11th International Workshop on Security and High Performance Computing Systems (SHPCS 2016)

Date: received 16 May 2016, last revised 16 May 2016

Contact author: wdai at wpi edu

Available format(s): PDF | BibTeX Citation

Version: 20160517:151641 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]