Cryptology ePrint Archive: Report 2018/873

TACHYON: Fast Signatures from Compact Knapsack

Rouzbeh Behnia and Muslum Ozgur Ozmen and Attila A. Yavuz and Mike Rosulek

Abstract: We introduce a simple, yet efficient digital signature scheme which offers post-quantum security promise. Our scheme, named $\texttt{TACHYON}$, is based on a novel approach for extending one-time hash-based signatures to (polynomially bounded) many-time signatures, using the additively homomorphic properties of generalized compact knapsack functions. Our design permits $\texttt{TACHYON}$ to achieve several key properties. First, its signing and verification algorithms are the fastest among its current counterparts with a higher level of security. This allows $\texttt{TACHYON}$ to achieve the lowest end-to-end delay among its counterparts, while also making it suitable for resource-limited signers. Second, its private keys can be as small as $\kappa$ bits, where $\kappa$ is the desired security level. Third, unlike most of its lattice-based counterparts, $\texttt{TACHYON}$ does not require any Gaussian sampling during signing, and therefore, is free from side-channel attacks targeting this process. We also explore various speed and storage trade-offs for $\texttt{TACHYON}$, thanks to its highly tunable parameters. Some of these trade-offs can speed up $\texttt{TACHYON}$ signing in exchange for larger keys, thereby permitting $\texttt{TACHYON}$ to further improve its end-to-end delay.

Category / Keywords: public-key cryptography / Digital signatures; post-quantum security; authentication

Original Publication (in the same form): CCS 2018
DOI:
10.1145/3243734.3243819

Date: received 18 Sep 2018, last revised 11 Dec 2018

Contact author: Rouzbeh behnia at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20181212:031847 (All versions of this report)

Short URL: ia.cr/2018/873


[ Cryptology ePrint archive ]