Paper 2021/457

Non-Interactive Composition of Sigma-Protocols via Share-then-Hash

Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Ohkubo, and Alon Rosen


Proofs of partial knowledge demonstrate the possession of certain subsets of witnesses for a given collection of statements $x_1,\dots,x_n$. Cramer, Damgård, and Schoenmakers (CDS), built proofs of partial knowledge, given ``atomic'' protocols for individual statements $x_i$, by having the prover randomly secret share the verifier's challenge and using the shares as challenges for the atomic protocols. This simple and highly-influential transformation has been used in numerous applications, ranging from anonymous credentials to ring signatures. We consider what happens if, instead of using the shares directly as challenges, the prover first hashes them. We show that this elementary enhancement can result in significant benefits: \begin{itemize} \item the proof contains a {\em single} atomic transcript per statement $x_i$, \item it suffices that the atomic protocols are $\kappa$-special sound for $\kappa \geq 2$, \item when compiled to a signature scheme using the Fiat-Shamir heuristic, its unforgeability can be proved in the {\em non-programmable} random oracle model. \end{itemize} None of the above features is satisfied by the CDS transformation.

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2020
sigma-protocolsrandom oraclesproof of partial knowledge
Contact author(s)
masayuki abe cp @ hco ntt co jp
miguel ambrona fu @ hco ntt co jp
andrejb @ cse cuhk edu hk
m ohkubo @ nict go jp
alon rosen @ idc ac il
2021-04-08: received
Short URL
Creative Commons Attribution


      author = {Masayuki Abe and Miguel Ambrona and Andrej Bogdanov and Miyako Ohkubo and Alon Rosen},
      title = {Non-Interactive Composition of Sigma-Protocols via Share-then-Hash},
      howpublished = {Cryptology ePrint Archive, Paper 2021/457},
      year = {2021},
      doi = {10.1007/978-3-030-64840-4_25},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.