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: ia.cr/2016/1085