Paper 2021/1565
Can Round-Optimal Lattice-Based Blind Signatures be Practical?
Shweta Agrawal and Elena Kirshanova and Damien Stehle and Anshu Yadav
Abstract
Blind signatures have numerous applications in privacy-preserving technologies. While there exist many practical blind signatures from number-theoretic assumptions, the situation is far less satisfactory from post-quantum assumptions. In this work, we make advances towards making lattice-based blind signatures practical. We introduce two round-optimal constructions in the random oracle model, and provide guidance towards their concrete realization as well as efficiency estimates. The first scheme relies on the homomorphic evaluation of a lattice-based signature scheme. This requires an ${\sf HE}$-compatible lattice-based signature. For this purpose, we show that the rejection step in Lyubashevsky's signature is unnecessary if the working modulus grows linearly in $\sqrt{Q}$, where $Q$ is an a priori bound on the number of signature queries. Compared to the state of art scheme from Hauck et al [CRYPTO'20], this blind signature compares very favorably in all aspects except for signer cost. Compared to a lattice-based instantiation of Fischlin's generic construction, it is much less demanding on the user and verifier sides. The second scheme relies on the Gentry, Peikert and Vaikuntanathan signature [STOC'08] and non-interactive zero-knowledge proofs for linear relations with small unknowns, which are significantly more efficient than their general purpose counterparts. Its security stems from a new and arguably natural assumption which we introduce: ${\sf one}$-${\sf more}$-${\sf ISIS}$. This assumption can be seen as a lattice analogue of the one-more-RSA assumption by Bellare et al [JoC'03]. To gain confidence, we provide a detailed overview of diverse attack strategies. The resulting blind signature beats all the aforementioned from most angles and obtains practical overall performance.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Blind signaturespracticalround-optimallattices
- Contact author(s)
- shweta a @ cse iitm ac in,elenakirshanova @ gmail com,damien stehle @ ens-lyon fr,anshu yadav06 @ gmail com
- History
- 2022-09-02: last of 3 revisions
- 2021-12-02: received
- See all versions
- Short URL
- https://ia.cr/2021/1565
- License
-
CC BY