Paper 2012/001

Digital Signatures from Challenge-Divided Sigma-Protocols

Andrew C. Yao and Yunlei Zhao


Digital signature is one of the basic primitives in cryptography. A common paradigm of obtaining signatures, known as the Fiat-Shamir (FS) paradigm, is to collapse any Σ-protocol (which is 3-round public-coin honest-verifier zero-knowledge) into a non-interactive scheme with hash functions that are modeled to be random oracles (RO). The Digital Signature Standard (DSS) and Schnorr’s signature schemes are two salient examples following the FS-paradigm. 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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
digital signaturesforking lemma
Contact author(s)
yunleizhao @ gmail com
2012-01-02: received
Short URL
Creative Commons Attribution


      author = {Andrew C.  Yao and Yunlei Zhao},
      title = {Digital Signatures from Challenge-Divided Sigma-Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2012/001},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.