Cryptology ePrint Archive: Report 2015/311

Tagged One-Time Signatures: Tight Security and Optimal Tag Size

Masayuki Abe and Bernardo David and Markulf Kohlweiss and Ryo Nishimaki and Miyako Ohkubo

Abstract: We present an efficient structure-preserving tagged one-time signature scheme with tight security reductions to the decision-linear assumption. Our scheme features short tags consisting of a single group element and gives rise to the currently most efficient structure-preserving signature scheme based on the decision-liner assumption with constant-size signatures of only 14 group elements, where the record-so-far was 17 elements.

To demonstrate the advantages of our scheme, we revisit the work by Hofheinz and Jager (CRYPTO 2012) and present the currently most efficient tightly secure public-key encryption scheme. We also obtain the first structure-preserving public-key encryption scheme featuring both tight security and public verifiability.

Category / Keywords: public-key cryptography / Tagged One-Time Signatures, Structure-Preserving Signatures, Tight Security Reduction, Decision Linear Assumption

Original Publication (with minor differences): IACR-PKC-2013
DOI: 10.1007/978-3-642-36362-7_20

Date: received 5 Apr 2015, last revised 10 Sep 2015

Contact author: m ohkubo at nict go jp

Available format(s): PDF | BibTeX Citation

Version: 20150910:102054 (All versions of this report)

Short URL: ia.cr/2015/311

Discussion forum: Show discussion | Start new discussion