## CryptoDB

### Paper: BLOOM: Bimodal Lattice One-Out-of-Many Proofs and Applications

Authors: Vadim Lyubashevsky , IBM Research Europe Ngoc Khanh Nguyen , École Polytechnique Fédérale de Lausanne Search ePrint Search Google Slides ASIACRYPT 2022 We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Lyubashevsky et al. (Crypto 2022) together with an improved, over prior lattice-based one-out-of-many proofs, recursive procedure, and a novel rejection sampling proof that allows to use the efficient bimodal rejection sampling throughout the protocol. Using these new primitives and techniques, we give instantiations of the most compact lattice-based ring and group signatures schemes. The improvement in signature sizes over prior works ranges between $25\%$ and $2$X. Perhaps of even more significance, the size of the user public keys, which need to be stored somewhere publicly accessible in order for ring signatures to be meaningful, is reduced by factors ranging from $7$X to $15$X. In what could be of independent interest, we also provide noticeably improved proofs for integer relations which, together with one-out-of-many proofs are key components of confidential payment systems.
##### BibTeX
@inproceedings{asiacrypt-2022-32511,
title={BLOOM: Bimodal Lattice One-Out-of-Many Proofs and Applications},
publisher={Springer-Verlag},
author={Vadim Lyubashevsky and Ngoc Khanh Nguyen},
year=2022
}