A Provably Secure Nyberg-Rueppel Signature Variant with Applications

Giuseppe Ateniese; Breno de Medeiros

Paper 2004/093

A Provably Secure Nyberg-Rueppel Signature Variant with Applications

Giuseppe Ateniese and Breno de Medeiros

Abstract

This paper analyzes the modified Nyberg-Rueppel signature scheme (mNR), proving it secure in the Generic Group Model (GM). We also show that the security of the mNR signature is equivalent (in the standard model) to that of a twin signature, while achieving computational and bandwidth improvements. As a provably secure signature scheme, mNR is very efficient. We demonstrate its practical relevance by providing an application to the construction of a provably secure, self-certified, identity-based scheme (SCID). SCID schemes combine some of the best features of both PKI-based schemes (functionally trusted authorities, public keys revocable without the need to change identifier strings) and ID-based ones (lower bandwidth requirements). The new SCID scheme matches the performance achieved by the most efficient ones based on the discrete logarithm, while requiring only standard security assumptions in the Generic Group Model.

Note: This revision adds applications to self-certified public key schemes.

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. manuscript
Keywords: Generic Group Model signature schemes Nyberg-Rueppel variants self-certified identity-based cryptography
Contact author(s): breno @ cs jhu edu
History: 2004-05-07: last of 2 revisions; 2004-04-17: received; See all versions
Short URL: https://ia.cr/2004/093
License: CC BY

BibTeX

@misc{cryptoeprint:2004/093,
      author = {Giuseppe Ateniese and Breno de Medeiros},
      title = {A Provably Secure Nyberg-Rueppel Signature Variant with Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/093},
      year = {2004},
      url = {https://eprint.iacr.org/2004/093}
}