In this work, we present a modified Fiat-Shamir paradigm, named challenge-divided Fiat-Shamir paradigm, which is applicable to a variant of Σ-protocol with divided random challenges. This new paradigm yields a new family of (online/offline efficient) digital signatures from challenge-divided Σ-protocols, including in particular a variant of Schnorr’s signature scheme called challenge-divided Schnorr signature. We then present a formal analysis of the challenge-divided Schnorr signature in the random oracle model. Finally, we give comparisons between the challenge-divided Schnorr signature and DSS and Schnorr’s signature, showing that the newly developed challenge-divided Schnorr signature can enjoy better (online/offline) efficiency (besides provable security in the random oracle model).
Of independent interest is a new forking lemma, referred to as divided forking lemma, for dealing with multiple ordered rewinding points in the RO model, which is of independent interest and can be applied to analyzing other cryptographic schemes in the RO model.Category / Keywords: public-key cryptography / digital signatures, forking lemma Date: received 2 Jan 2012 Contact author: yunleizhao at gmail com Available formats: PDF | BibTeX Citation Version: 20120102:203345 (All versions of this report) Discussion forum: Show discussion | Start new discussion