Paper 2016/1085

Digital Signatures from Symmetric-Key Primitives

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


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)
Public-key cryptography
Publication info
Preprint. MINOR revision.
post-quantum cryptographysignaturesblock cipherFiat-ShamirBellare-Goldwasserimplementation
Contact author(s)
sebastian ramacher @ iaik tugraz at
2017-03-30: last of 2 revisions
2016-11-21: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.