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
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint. MAJOR revision.
- Keywords
- OTSMerkle TreeNTTSWIFFTCover-Free FamilySIMD.
- Contact author(s)
- sabyasachi karati @ gmail com
- History
- 2019-05-03: received
- Short URL
- https://ia.cr/2019/442
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/442, author = {Sabyasachi Karati and Reihaneh Safavi-Naini}, title = {{K2SN}-{MSS}: An Efficient Post-Quantum Signature (Full Version)}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/442}, year = {2019}, url = {https://eprint.iacr.org/2019/442} }