Motivated by the need to have secure blind signatures even in the presence of quantum computers, we present two efficient blind signature schemes based on hard worst-case lattice problems. Both schemes are provably secure in the random oracle model and unconditionally blind. The first scheme is based on preimage samplable functions that were introduced at STOC 2008 by Gentry, Peikert, and Vaikuntanathan. The scheme is stateful and runs in 3 moves. The second scheme builds upon the PKC 2008 identification scheme of Lyubashevsky. It is stateless, has 4 moves, and its security is based on the hardness of worst-case problems in ideal lattices.
Motivated by the need to have secure blind signatures even in the presence of quantum computers, we present two efficient blind signature schemes based on hard worst-case lattice problems. Both schemes are provably secure in the random oracle model and unconditionally blind. The first scheme is based on preimage samplable functions that were introduced at STOC 2008 by Gentry, Peikert, and Vaikuntanathan. The scheme is stateful and runs in 3 moves. The second scheme builds upon the PKC 2008 identification scheme of Lyubashevsky. It is stateless, has 4 moves, and its security is based on the hardness of worst-case problems in ideal lattices.
Motivated by the need to have secure blind signatures even in the presence of quantum computers, we present two ecient blind signa- ture schemes based on hard worst-case lattice problems. Both schemes are provably secure in the random oracle model and unconditionally blind. The rst scheme is based on preimage samplable functions that were introduced at STOC 2008 by Gentry, Peikert, and Vaikuntanathan. The scheme is stateful and runs in 3 moves. The second scheme builds upon the PKC 2008 identication scheme of Lyubashevsky. It is state- less, has 4 moves, and its security is based on the hardness of worst-case problems in ideal lattices.
Building cryptographic schemes upon as many fundamentally different hard problems as possible, seems to be the best way to hedge against future threats such as quantum computers. Being mainly based on the hardness of factoring and computing discrete logarithms, the present security landscape is at risk. In contrast, problems in lattices, such as finding short non-zero vectors, seem to withstand quantum computer attacks and the best known algorithms run in exponential time. In sharp contrast to other fields of cryptography, lattices admit a worst-case to average-case reduction (Ajtai 1996). Instead of assuming that a problem is hard for randomly chosen instances, lattice-based cryptosystems merely require the existence of a single hard instance, i.e., hardness in the worst case. With such an additional "trust anchor", the resulting security guarantees are much more plausible. Quite recently, we have seen an increased interest in lattice-based cryptography with many striking results. In this thesis, we are particularly interested in signature schemes, which provide a supporting pillar for today's economy. While we have seen basic signature schemes from lattices, e.g., (Gentry, Peikert, Vaikuntanathan 2008), (Lyubashevsky, Micciancio 2008), (Lyubashevsky 2009), or (Cash, Hofheinz, Kiltz, Peikert 2009), there are hardly any results dealing with the specific needs of applications, where ordinary signatures often fall too short. In this thesis, we build upon the above results and equip them with additional features, motivated by an exemplary selection of application scenarios. Hence, we demonstrate the great versatility of lattices in cryptography. In particular, we facilitate privacy-friendly electronic elections, fair online contract signing, signature compression, secure signatures in the strongest sense, as well as identity-based primitives. As far as possible, we avoid simplifying assumptions, such as the random oracle model. We believe that our techniques can be transferred to other application scenarios as well. Independently of the these results, we discuss the practical hardness of lattice problems and provide a framework for estimating the security of essentially all modern lattice-based cryptography.
Abstract. We provide an alternative method for constructing lattice-based digital signatures which does not use the “hash-and-sign ” methodology of Gentry, Peikert, and Vaikuntanathan (STOC 2008). Our resulting signature scheme is secure, in the random oracle model, based on the worst-case hardness of the Õ(n1.5)-SIVP problem in general lattices. The secret key, public key, and the signature size of our scheme are smaller than in all previous instantiations of the hash-and-sign signature, and our signing algorithm is also quite simple, requiring just a few matrix-vector multiplications and rejection samplings. We then also show that by slightly changing the parameters, one can get even more efficient signatures that are based on the hardness of the Learning With Errors problem. Our construction naturally transfers to the ring setting, where the size of the public and secret keys can be significantly shrunk, which results in the most practical to-date provably secure signature scheme based on lattices. 1
Blind signature allows a user to get a signature of a signer on an arbitrary message, and the verifier can convince that the signature is indeed signed by the signer without leaking any information about the message. This property is necessary when the user’s privacy needs protection, such as a bank bill, a trade secret, etc. As an alternative of public key infrastructure, the identity-based system can simplify the key management procedures in certificate-based public key systems. Inspired by the requirement of identity-based blind signature in the post quantum world, we research on identity-based blind signature based on hard lattice problems under the random Oracle model. We propose a construction built upon the blind signature by Rückert, and it is proved to be one-more unforgeable against selective identity and chosen message attacks (sID-CMA) and unconditionally blind. The proposed scheme has 2 moves, and its security can be reduced to the small integer solution (SIS) problem.
Blind signature schemes (BSS) play a pivotal role in privacy-oriented cryptography. However, with BSS, the signed message remains unintelligible to the signer, giving them no guarantee that the blinded message he signed actually contained valid information. Partially BSS (PBSS) were introduced to address precisely this problem. In this study, the authors present the first leakage-resilient, lattice-based PBSS in the literature. The proposed construction is provably secure in the random oracle model and offers quasi-linear complexity w.r.t. key/signature sizes and signing speed. In addition, it offers statistical partial blindness and its unforgeability is based on the computational hardness of worst-case ideal lattice problems for approximation factors in O ~ ( n 4 ) in dimension n. The proposed scheme benefits from the subexponential hardness of ideal lattice problems and remains secure even if a ( 1 − o ( 1 ) ) fraction of the signer's secret key leaks to an adversary via arbitrary side-channels. Several extensions of the security model, such as honest-user unforgeability and selective failure blindness, are also considered and concrete parameters for instantiation are proposed.
Blind signature offer the protection for sender's privacy and become an important primitive for electronic commerce. In this paper, we present a technique of matrix-vector-blinding for lattice-based blind signature. Building on this result, we propose two hierarchical ID-based blind signature schemes from lattice with and without random oracle, which are secure against quantum attacks. We apply the latest technique of "lattice basis delegation in fixed dimension" from ABB10's[1] scheme to our constructions which contribute to shorter public key and signature. Both of our blind signature schemes are proven to hold the properties of perfect blindness and one-more unforgeableability. Our hierarchical ID-based blind signature schemes are communicationally efficient and needs only one round data exchanges between the signer and the user, and with a shorter public key and signature in comparison with similar schemes[2, 3]. We prove that our scheme is secure assuming that the short integer solution (SIS) problem is hard.