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.

Fully Homomorphic Encryption has known impressive improvements in the last 15 years, going from a technology long thought to be impossible to an existing family of encryption schemes able to solve a plethora of practical use cases related to the privacy of sensitive information. Recent results mainly focus on improving techniques within the traditionally defined framework of GLWE-based schemes, but the recent CPU implementation improvements are mainly incremental. To keep improving this technology, one solution is to modify the aforementioned framework, by using slightly different hardness assumptions.

Abstract The Fiat-Shamir with Aborts paradigm of Lyubashevsky has given rise to efficient lattice-based signature schemes. One popular implementation is Dilithium, which has been selected for standardization by the US National Institute of Standards and Technology (NIST). Informally, it can be seen as a lattice analog of the well-known discrete-logarithm-based Schnorr signature. An interesting research question is whether it is possible to combine several unrelated signatures, issued from different signing parties on different messages, into one single aggregated signature. Of course, its size should be significantly smaller than the trivial concatenation of all signatures. Ideally, the aggregation can be done offline by a third party, called public aggregation. Previous works have shown that it is possible to half-aggregate Schnorr signatures, but it was left open if the underlying techniques can be adapted to the lattice setting. In this work, we show that, indeed, we can use similar strategies to obtain a signature scheme allowing for public aggregation whose hardness is proven assuming the intractability of well-studied problems on module lattices. Unfortunately, our scheme produces aggregated signatures that are larger than the trivial solution of concatenating. This is due to peculiarities that seem inherent to lattice-based cryptography. Its motivation is thus mainly pedagogical.

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.

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems. Previously this was only known under quantum reductions.