Paper 2019/442

K2SN-MSS: An Efficient Post-Quantum Signature (Full Version)

Sabyasachi Karati and Reihaneh Safavi-Naini

Abstract

With the rapid development of quantum technologies, quantum-safe cryptography has found significant attention. Hash-based signature schemes have been in particular of interest because of (i) the importance of digital signature as the main source of trust on the Internet, (ii) the fact that the security of these signatures relies on existence of one-way functions, which is the minimal assumption for signature schemes, and (iii) they can be efficiently implemented. Basic hash-based signatures are for a single message, but have been extended for signing multiple messages. In this paper we design a Multi-message Signature Scheme (MSS) based on an existing One-Time Signature (OTS) that we refer to as KSN-OTS. KSN uses SWIFFT, an additive homomorphic lattice-based hash function family with provable one-wayness property, as the one-way-function and achieves a short signature. We prove security of our proposed signature scheme in a new strengthened security model (multi-target multi-function) of MSS, determine the system parameters for 512 bit classical (256 bit quantum) security, and compare parameter sizes of our scheme against XMSS, a widely studied hash based MSS that has been a candidate for NIST standardization of post-quantum signature scheme. We give an efficient implementation of our scheme using Intel SIMD (Single Instruction Multiple Data) instruction set. For this, we first implement SWIFFT computation using a SIMD parallelization of Number Theoretic Transform (NTT) of elements of the ring $\mathbb{Z}_p[X]/(X^\n+1)$, that can support different levels of parallelization. We compare efficiency of this implementation with a comparable (security level) implementation of XMSS and show its superior performance on a number of efficiency parameters.