CISPA
Browse
cispa_all_3598.pdf (804.54 kB)

Lattice-based Signatures with Tight Adaptive Corruptions and More

Download (804.54 kB)
conference contribution
posted on 2023-11-29, 18:19 authored by Jiaxin Pan, Benedikt Wagner
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.

History

Preferred Citation

Jiaxin Pan and Benedikt Wagner. Lattice-based Signatures with Tight Adaptive Corruptions and More. In: International Conference on Practice and Theory in Public Key Cryptography (PKC). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on Practice and Theory in Public Key Cryptography (PKC)

Legacy Posted Date

2022-04-05

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3598, title = "Lattice-based Signatures with Tight Adaptive Corruptions and More", author = "Pan, Jiaxin and Wagner, Benedikt", booktitle="{International Conference on Practice and Theory in Public Key Cryptography (PKC)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC