Cryptology ePrint Archive: Report 2020/276

CryptoPIM: In-memory Acceleration for Lattice-based Cryptographic Hardware

Hamid Nejatollahi and Saransh Gupta and Mohsen Imani and Tajana Simunic Rosing and Rosario Cammarota and Nikil Dutt

Abstract: Quantum computers promise to solve hard mathematical problems such as integer factorization and discrete logarithms in polynomial time, making standardized public-key cryptography (such as digital signature and key agreement) insecure. Lattice-Based Cryptography (LBC) is a promising post-quantum public-key cryptographic protocol that could replace standardized public-key cryptography, thanks to the inherent post-quantum resistant properties, efficiency, and versatility. A key mathematical tool in LBC is the Number Theoretic Transform (NTT), a common method to compute polynomial multiplication that is the most compute-intensive routine, and which requires acceleration for practical deployment of LBC protocols. In this paper, we propose, a high-throughput Processing In-Memory (PIM) accelerator for NTT-based polynomial multiplier with the support of polynomials with degrees up to 32k. Compared to the fastest FPGA implementation of an NTT-based multiplier, achieves on average 31x throughput improvement with the same energy and only 28% performance reduction, thereby showing promise for practical deployment of LBC.

Category / Keywords: implementation / Lattice-based Cryptography, Acceleration, Number Theoretic Transform, Homomorphic Encryption, Processing in Memory

Original Publication (in the same form): Design Automation Conference (DAC)

Date: received 2 Mar 2020, last revised 14 Mar 2020

Contact author: hnejatol at uci edu

Available format(s): PDF | BibTeX Citation

Version: 20200315:015621 (All versions of this report)

Short URL: ia.cr/2020/276


[ Cryptology ePrint archive ]