Paper 2018/873

TACHYON: Fast Signatures from Compact Knapsack

Rouzbeh Behnia, Muslum Ozgur Ozmen, 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 $\mathtt{\text{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 $\mathtt{\text{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 $\mathtt{\text{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, $$ 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 $$, thanks to its highly tunable parameters. Some of these trade-offs can speed up $$ signing in exchange for larger keys, thereby permitting $$ to further improve its end-to-end delay.