Tightly-secure signatures from Chameleon Hash Functions

Olivier Blazy*, Saqib A. Kakvi, Eike Kiltz, Jiaxin Pan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

48 Citations (Scopus)

Abstract

We give a new framework for obtaining signatures with a tight security reduction from standard hardness assumptions. Concretely, we show that any Chameleon Hash function can be transformed into a (binary) tree-based signature scheme with tight security. The transformation is in the standard model, i.e., it does not make use of any random oracle. For specific assumptions (such as RSA, Diffie-Hellman and Short Integer Solution (SIS)) we further manage to obtain a more efficient flat-tree construction. Our framework explains and generalizes most of the existing schemes as well as providing a generic means for constructing tight signature schemes based on arbitrary assumptions, which improves the standard Merkle tree transformation. Moreover, we obtain the first tightly secure signature scheme from the SIS assumption and several schemes based on Diffie-Hellman in the standard model. Some of our signature schemes can (using known techniques) be combined with Groth-Sahai proof methodology to yield tightly secure and efficient simulation-sound NIZK proofs of knowledge and CCA-secure encryption in the multi-user/-challenge setting under classical assumptions.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
Pages256-279
Number of pages24
Volume9020
ISBN (Print)9783662464465
DOIs
Publication statusPublished - 2015
Event18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015 - Gaithersburg, United States
Duration: 30 Mar 20151 Apr 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9020
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015
Country/TerritoryUnited States
CityGaithersburg
Period30/03/151/04/15

Keywords

  • Chameleon hash
  • Signature
  • Standard model
  • Tight reduction

Fingerprint

Dive into the research topics of 'Tightly-secure signatures from Chameleon Hash Functions'. Together they form a unique fingerprint.

Cite this