Paper 2020/688

Lin2-Xor Lemma: an OR-proof that leads to the membership proof and signature

Anton A. Sokolov
Abstract

In this paper we introduce an novel two-round public coin OR-proof protocol that extends in a natural way to the log-size membership proof and signature in a prime-order group. In the lemma called Lin2-Xor we prove that our OR-proof is perfectly complete and has witness-extended emulation under the discrete logarithm assumption. We derive from it a log-size one-out-of-many proof, which retains the perfect completeness and witness-extended emulation. Both of our OR- and membership- proofs easily acquire the special honest verifier zero-knowledge property under the decisional Diffie-Hellman assumption. We sketch out a setup-free pairings-free log-size linkable ring signature with strong security model on top of our membership proof. Many recently proposed discrete-log setup-free pairings-free log-size ring signatures are based on the ideas of commitment-to-zero proving system by Groth and Kohlweiss or on the Bulletproofs inner-product compression method by Bünz et al. Our Lin2-Xor lemma provides an alternative technique which, using the general reduction similar to Bulletproofs, leads directly to the log-size linkable ring signature under the same prerequisites.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
or-proofmembership prooflinkable ring signaturelog-sizeanonymityzero-knowledgewitness-extended emulation
Contact author(s)
acmxddk @ gmail com
History
2024-03-14: last of 11 revisions
2020-06-09: received
See all versions
Short URL
https://ia.cr/2020/688
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/688,
      author = {Anton A.  Sokolov},
      title = {Lin2-Xor Lemma: an OR-proof that leads to the membership proof and signature},
      howpublished = {Cryptology ePrint Archive, Paper 2020/688},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/688}},
      url = {https://eprint.iacr.org/2020/688}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.