Paper 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.

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