### Digital Signatures from Symmetric-Key Primitives

David Derler, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, and Daniel Slamanig

##### Abstract

We propose practically efficient signature schemes which feature several attractive properties: (a) they only rely on the security of symmetric-key primitives (block ciphers, hash functions), and are therefore a viable candidate for post-quantum security, (b) they have extremely small signing keys, essentially the smallest possible, and, (c) they are highly parametrizable. For this result we take advantage of advances in two very distinct areas of cryptography. The first is the area of primitives in symmetric cryptography, where recent developments led to designs which exhibit an especially low number of multiplications. The second is the area of zero-knowledge proof systems, where significant progress for efficiently proving statements over general circuits was recently made. We follow two different directions, one of them yielding the first practical instantiation of a design paradigm due to Bellare and Goldwasser without relying on structured hardness assumptions. For both our schemes we explore the whole design spectrum to obtain optimal parameter choices for different settings. Within limits, in all cases our schemes allow to trade-off computational effort with signature sizes. We also demonstrate that our schemes are parallelizable to the extent that they can practically take advantage of several cores on a CPU.

Note: This paper has been merged into ePrint:2017/279.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
post-quantum cryptographysignaturesblock cipherFiat-ShamirBellare-Goldwasserimplementation
Contact author(s)
sebastian ramacher @ iaik tugraz at
History
2017-03-30: last of 2 revisions
See all versions
Short URL
https://ia.cr/2016/1085

CC BY

BibTeX

@misc{cryptoeprint:2016/1085,
author = {David Derler and Claudio Orlandi and Sebastian Ramacher and Christian Rechberger and Daniel Slamanig},
title = {Digital Signatures from Symmetric-Key Primitives},
howpublished = {Cryptology ePrint Archive, Paper 2016/1085},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/1085}},
url = {https://eprint.iacr.org/2016/1085}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.