Paper 2018/873

TACHYON: Fast Signatures from Compact Knapsack

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


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. CCS 2018
Digital signaturespost-quantum securityauthentication
Contact author(s)
Rouzbeh behnia @ gmail com
2018-12-12: revised
2018-09-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rouzbeh Behnia and Muslum Ozgur Ozmen and Attila A.  Yavuz and Mike Rosulek},
      title = {{TACHYON}: Fast Signatures from Compact Knapsack},
      howpublished = {Cryptology ePrint Archive, Paper 2018/873},
      year = {2018},
      doi = {10.1145/3243734.3243819},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.