Paper 2020/688

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

Abstract

This paper introduces a logarithmic-size membership proof, Lin2Selector, obtained by iterating a new OR-reduction step, formalized as a standalone argument Lin2Xor. Our main technical contribution is the Lin2-Xor lemma, which establishes the required special soundness for this reduction and thereby enables a clean proof that Lin2Selector is a zero-knowledge argument of knowledge. As an application, we instantiate two setup-free linkable ring signatures via the Fiat–Shamir transform in the ROM: minimalistic L2S-LRS, of length 2(log n)+4 group/scalar elements, and multisignature-friendly L2S-LRS-MS, of length 2(log n)+5, supporting an LSAG-style key image. Both schemes rely only on the standard DLR/DDH assumptions in a black-box prime-order group and allow efficient verification dominated by a single multi-exponentiation, enabling standard batching optimizations. The OR-reduction step Lin2Xor suggests a natural generalization to higher arity. This may enable even more compact one-out-of-many proofs/signatures with lengths approaching (log n)+O(log log n), as well as compact k-out-of-many variants; we leave these as open directions.