Lattice-Based Signatures with Tight Adaptive Corruptions and More

Abstract. We construct the first tightly secure signature schemes in the

multi-user setting with adaptive corruptions from lattices. In stark contrast to the previous tight constructions whose security is solely based on

number-theoretic assumptions, our schemes are based on the Learning

with Errors (LWE) assumption which is supposed to be post-quantum

secure. The security of our scheme is independent of the numbers of users

and signing queries, and it is in the non-programmable random oracle

model. Our LWE-based scheme is compact, namely, its signatures contain only a constant number of lattice vectors.

At the core of our construction are a new abstraction of the existing

lossy identification (ID) schemes using dual-mode commitment schemes

and a refinement of the framework by Diemert et al. (PKC 2021) which

transforms a lossy ID scheme to a signature using sequential OR proofs.

In combination, we obtain a tight generic construction of signatures from

dual-mode commitments in the multi-user setting. Improving the work

of Diemert et al., our new approach can be instantiated using not only

the LWE assumption, but also an isogeny-based assumption. We stress

that our LWE-based lossy ID scheme in the intermediate step uses a

conceptually different idea than the previous lattice-based ones.

Of independent interest, we formally rule out the possibility that the

aforementioned “ID-to-Signature” methodology can work tightly using

parallel OR proofs. In addition to the results of Fischlin et al. (EUROCRYPT 2020), our impossibility result shows a qualitative difference

between both forms of OR proofs in terms of tightness.