Paper 2015/311

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

Masayuki Abe, Bernardo David, Markulf Kohlweiss, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2013
DOI
10.1007/978-3-642-36362-7_20
Keywords
Tagged One-Time SignaturesStructure-Preserving SignaturesTight Security ReductionDecision Linear Assumption
Contact author(s)
m ohkubo @ nict go jp
History
2015-09-10: revised
2015-04-06: received
See all versions
Short URL
https://ia.cr/2015/311
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/311,
      author = {Masayuki Abe and Bernardo David and Markulf Kohlweiss and Ryo Nishimaki and Miyako Ohkubo},
      title = {Tagged One-Time Signatures: Tight Security and Optimal Tag Size},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/311},
      year = {2015},
      doi = {10.1007/978-3-642-36362-7_20},
      url = {https://eprint.iacr.org/2015/311}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.