Cryptology ePrint Archive: Report 2016/1085

Digital Signatures from Symmetric-Key Primitives

David Derler and Claudio Orlandi and Sebastian Ramacher and 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.

Category / Keywords: public-key cryptography / post-quantum cryptography, signatures, block cipher, Fiat-Shamir, Bellare-Goldwasser, implementation

Date: received 18 Nov 2016, last revised 30 Mar 2017

Contact author: sebastian ramacher at iaik tugraz at

Available format(s): PDF | BibTeX Citation

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

Version: 20170330:124800 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]