The transition to post-quantum cryptography has been an enormous challenge and effort for cryptographers over the last decade, with impressive results such as the future NIST standards. However, the latter has so far only considered central cryptographic mechanisms (signatures or KEM) and not more advanced ones, e.g., targeting privacy-preserving applications. Of particular interest is the family of solutions called blind signatures, group signatures and anonymous credentials, for which standards already exist, and which are deployed in billions of devices. Such a family does not have, at this stage, an efficient post-quantum counterpart although very recent works improved this state of affairs by offering two different alternatives: either one gets a system with rather large elements but a security proved under standard assumptions or one gets a more efficient system at the cost of ad-hoc interactive assumptions or weaker security models. Moreover, all these works have only considered size complexity without implementing the quite complex building blocks their systems are composed of. In other words, the practicality of such systems is still very hard to assess, which is a problem if one envisions a post-quantum transition for the corresponding systems/standards.

The Module Learning With Errors ( $$\text {M-LWE}$$ ) problem is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of $$\text {M-LWE}$$ , i.e., uniform secret modulo q and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress toward narrowing this gap. More precisely, we prove that $$\text {M-LWE}$$ with uniform $$\eta $$ -bounded secret for any $$1 \le \eta \ll q$$ and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of $$\text {M-LWE}$$ , provided that the module rank d is at least logarithmic in the ring degree n. We also prove that the search version of $$\text {M-LWE}$$ with large uniform secret and uniform $$\eta $$ -bounded error is at least as hard as the standard $$\text {M-LWE}$$ problem, if the number of samples m is close to the module rank d and with further restrictions on $$\eta $$ . The latter result can be extended to provide the hardness of search $$\text {M-LWE}$$ with uniform $$\eta $$ -bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.