Cryptology ePrint Archive: Report 2008/322

Lattice-based Blind Signatures

Markus Rückert

Abstract: Blind signatures (BS), introduced by Chaum, have become a cornerstone in privacy-oriented cryptography.

Using hard lattice problems, such as the shortest vector problem, as the basis of security has advantages over using the factoring or discrete logarithm problems. For instance, lattice operations are more efficient than modular exponentiation and lattice problems remain hard for quantum and subexponential-time adversaries.

Generally speaking, BS allow a signer to sign a message without seeing it, while retaining a certain amount of control over the process. In particular, the signer can control the number of issued signatures. For the receiver of the signature, this process provides perfect anonymity, e.g., his spendings remain anonymous when using BS for electronic money.

We provide a positive answer to the question of whether it is possible to implement BS based on lattice problems. More precisely, we show how to turn Lyubashevsky's identification scheme into a BS scheme, which has almost the same efficiency and security in the random oracle model. In particular, it offers quasi-linear complexity, statistical blindness, and its unforgeability is based on the hardness of worst-case lattice problems with an approximation factor of $\cOtilde(n^{5})$ in dimension $n$. Moreover, it is the first blind signature scheme that supports leakage-resilience, tolerating leakage of a $(1-o(1))$ fraction of the secret key in a model that is inspired by Katz and Vaikuntanathan.

Category / Keywords: Blind signatures, post-quantum, lattices, provable security, leakage resilience

Publication Info: ASIACRYPT 2010

Date: received 25 Jul 2008, last revised 1 Dec 2010

Contact author: rueckert at cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Note: * Added missing reference to (Pointcheval, Stern 2000) in the proof of unforgeability. * Fixed wrong scaling in Fig 4 and Fig 5.

Version: 20101201:073331 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]