Abstract. 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

2X. 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 7X to

15X. In what could be of independent interest, we also provide noticeably improved proofs for integer relations which, together with one-outof-many proofs are key components of confidential payment systems.