Paper 2012/001

Digital Signatures from Challenge-Divided Sigma-Protocols

Andrew C. Yao and Yunlei Zhao

Abstract

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.