Paper 2021/1565

Practical, Round-Optimal Lattice-Based Blind Signatures

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 provide the first round-optimal, practical lattice based blind signature. Our scheme relies on the Gentry, Peikert and Vainkuntanathan 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: one-more-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.

Note: This version does not contain one of the constructions from the earlier version. That construction has been substantially improved and will appear as a separate report.