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 $\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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. CCS 2018
DOI
10.1145/3243734.3243819
Keywords
Digital signaturespost-quantum securityauthentication
Contact author(s)
Rouzbeh behnia @ gmail com
History
2018-12-12: revised
2018-09-23: received
See all versions
Short URL
https://ia.cr/2018/873
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/873,
      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{https://eprint.iacr.org/2018/873}},
      url = {https://eprint.iacr.org/2018/873}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.