Practical Signatures from Standard Assumptions

Florian Böhl, Dennis Hofheinz, Tibor Jager, Jessica Koch, Jae Hong Seo, Christoph Striecks

Research output: Chapter in Book or Conference ProceedingsConference Proceedings with Oral Presentationpeer-review


We put forward new techniques for designing signature schemes. As a result, we present practical signature schemes based on the CDH, the RSA, and the SIS assumptions. Our schemes compare favorably with existing schemes based on these assumptions.
Our core idea is the use of tag-based signatures. Concretely, each signatures contains a tag which is uniformly chosen from a suitable tag set. Intuitively, the tag provides a way to embed instances of computational problems. Indeed, carefully choosing these tag spaces provides new ways to partition the set of possible message-tag pairs into “signable” and “unsignable” pairs. In our security proof, we will thus be able to sign all adversarially requested messages, and at the same time use an adversarially generated forgery with suitably large probability.
Original languageEnglish
Title of host publication32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques - EUROCRYPT 2013
Publication statusPublished - 2013
EventEUROCRYPT 2013: Advances in Cryptology – EUROCRYPT 2013 - Athens, Athens, Greece
Duration: 26 May 201330 May 2013


ConferenceEUROCRYPT 2013: Advances in Cryptology – EUROCRYPT 2013

Research Field

  • Cyber Security


Dive into the research topics of 'Practical Signatures from Standard Assumptions'. Together they form a unique fingerprint.

Cite this