Cryptology ePrint Archive: Report 2020/769

Lattice-Based Blind Signatures, Revisited

Eduard Hauck and Eike Kiltz and Julian Loss and Ngoc Khanh Nguyen

Abstract: We observe that all previously known lattice-based blind signature schemes contain subtle flaws in their security proofs (e.g., Rückert, ASIACRYPT '08) or can be attacked (e.g., BLAZE by Alkadri et al., FC '20). Motivated by this, we revisit the problem of constructing blind signatures from standard lattice assumptions.

We propose a new three-round lattice-based blind signature scheme whose security can be proved, in the random oracle model, from the standard SIS assumption. Our starting point is a modified version of the (insecure) BLAZE scheme, which itself is based Lyubashevsky's three-round identification scheme combined with a new aborting technique to reduce the correctness error. Our proof builds upon and extends the recent modular framework for blind signatures of Hauck, Kiltz, and Loss (EUROCRYPT '19). It also introduces several new techniques to overcome the additional challenges posed by the correctness error which is inherent to all lattice-based constructions.

While our construction is mostly of theoretical interest, we believe it to be an important stepping stone for future works in this area.

Category / Keywords: public-key cryptography / Blind Signatures

Original Publication (with minor differences): IACR-CRYPTO-2020

Date: received 22 Jun 2020, last revised 2 Jan 2021

Contact author: lossjulian at gmail com, eike kiltz at rub de, eduard hauck at rub de, NKN at zurich ibm com

Available format(s): PDF | BibTeX Citation

Version: 20210102:131134 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]