Paper 2021/1405

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

Tianyu Zheng
Shang Gao
Yubo Song
Bin Xiao

Ring Confidential Transaction (RingCT) protocol is an effective cryptographic component for preserving the privacy of cryptocurrencies. However, existing RingCT protocols are instantiated from one-out-of-many proofs with only one secret, leading to low efficiency and weak anonymity when handling transactions with multiple inputs. Additionally, current partial knowledge proofs with multiple secrets are neither secure nor efficient to be applied in a RingCT protocol. In this paper, we propose a novel \emph{any-out-of-many proof}, a logarithmic-sized zero-knowledge proof scheme for showing the knowledge of arbitrarily many secrets out of a public list. Unlike other partial knowledge proofs that have to reveal the number of secrets [ACF21], our approach proves the knowledge of multiple secrets without leaking the exact number of them. Furthermore, we improve the efficiency of our method with a generic inner-product transformation to adopt the Bulletproofs compression [BBB+18], which reduces the proof size to $2 \lceil \log_2(N) \rceil \! + \! 9$. Based on our proposed proof scheme, we further construct a compact RingCT protocol for privacy cryptocurrencies, which can provide a logarithmic-sized communication complexity for transactions with multiple inputs. More importantly, as the only known RingCT protocol instantiated from the partial knowledge proofs, our protocol can achieve the highest anonymity level compared with other approaches like Omniring [LRR+19]. For other applications, such as multiple ring signatures, our protocol can also be applied with some modifications. We believe our techniques are also applicable in other privacy-preserving scenarios, such as multiple ring signatures and coin-mixing in the blockchain.

Available format(s)
Cryptographic protocols
Publication info
zero-knowledge$k$-out-of-$N$ proofring signatureconfidential transaction
Contact author(s)
tian-yu zheng @ connect polyu hk
shanggao @ polyu edu hk
songyubo @ seu edu cn
csbxiao @ comp polyu edu hk
2023-07-02: last of 2 revisions
2021-10-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tianyu Zheng and Shang Gao and Yubo Song and Bin Xiao},
      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.