Paper 2021/1405

Leaking Arbitrarily Many Secrets: Any-out-of-Many Proofs and Applications to RingCT Protocols

Tianyu Zheng, Shang Gao, Bin Xiao, and Yubo Song


In this paper, we propose any-out-of-many proofs, a logarithmic zero-knowledge scheme for proving knowledge of arbitrarily many secrets out of a public list. Unlike existing $k$-out-of-$N$ proofs [S\&P'21, CRYPTO'21], our approach also hides the exact amount of secrets $k$, which can be used to achieve a higher anonymity level. Furthermore, we enhance the efficiency of our scheme through a transformation that can adopt the improved inner product argument in Bulletproofs [S\&P'18], only $2 \cdot \lceil log_2(N) \rceil + 13$ elements need to be sent in a non-interactive proof. We further use our proof scheme to implement both multiple ring signature schemes and RingCT protocols. For multiple ring signatures, we need to add a boundary constraint for the number $k$ to avoid the proof of an empty secret set. Thus, an improved version called bounded any-out-of-many proof is presented, which preserves all nice features of the original protocol such as high anonymity and logarithmic size. As for the RingCT, both the original and bounded proofs can be used safely. The result of the performance evaluation indicates that our RingCT protocol is more efficient and secure than others. We also believe our techniques are applicable in other privacy-preserving occasions.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
zero-knowledge$k$-out-of-$N$ proofring signatureconfidential transaction
Contact author(s)
tianzheng @ polyu edu hk
shang-jason gao @ polyu edu hk
2021-11-24: revised
2021-10-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tianyu Zheng and Shang Gao and Bin Xiao and Yubo Song},
      title = {Leaking Arbitrarily Many Secrets: Any-out-of-Many Proofs and Applications to RingCT Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1405},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.