We propose a 2-round blind signature protocol based on the random oracle heuristic and the hardness of standard lattice problems (Ring/Module-SIS/LWE and NTRU) with a signature size of 20 KB. The protocol is round-optimal and has a transcript size that can be as small as 60 KB. This blind signature is around 4 times shorter than the most compact lattice-based scheme based on standard assumptions of del Pino and Katsumata (Crypto 2022) and around 2 times shorter than the scheme of Agrawal et al. (CCS 2022) based on their newly-proposed one-more-ISIS assumption. We also propose a "keyed-verification'' blind signature scheme in which the verifier and the signer need to share a secret key. This scheme has a smaller signature size of only 48 bytes, but further work is needed to explore the efficiency of its signature generation protocol.
We propose a 2-round blind signature protocol based on the random oracle heuristic and the hardness of standard lattice problems (Ring/Module-SIS/LWE and NTRU) with a signature size of 20 KB. The protocol is round-optimal and has a transcript size that can be as small as 60 KB. This blind signature is around 4 times shorter than the most compact lattice-based scheme based on standard assumptions of del Pino and Katsumata (Crypto 2022) and around 2 times shorter than the scheme of Agrawal et al. (CCS 2022) based on their newly-proposed one-more-ISIS assumption. We also propose a "keyed-verification'' blind signature scheme in which the verifier and the signer need to share a secret key. This scheme has a smaller signature size of only 48 bytes, but further work is needed to explore the efficiency of its signature generation protocol.
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.
Blind signatures are a central tool for privacy-preserving protocols. They allow users to obtain signatures from a signer without the signer seeing the signed message. For instance, it enables electronic cash: signatures correspond to coins which can be issued by the bank in a privacy-preserving manner via blind signing. To mitigate the risk of key compromise, threshold blind signatures allow the distribution of the signing key amongst N parties. While recent works have focused on improving the security of this primitive in the classical setting, no construction is known to date in the post-quantum setting. We present the first construction of a threshold blind signature secure in the post-quantum setting, based on lattices. We prove its security under an interactive variant of the SIS assumption introduced in [Agrawal et al., CCS’22]. Our construction has a reasonable overhead of a factor of roughly 1.4 X to 2.5 X in signature size over comparable non-threshold blind signatures over lattices under heuristic but natural assumptions.
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 signatures are a fundamental cryptographic primitive with numerous practical applications. 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 overall practical, lattice-based blind signature, supporting an unbounded number of signature queries and additionally enjoying optimal round complexity. We provide a detailed estimate of parameters achieved -- we obtain a signature of size slightly above 45KB, for a core-SVP hardness of 109 bits. The run-times of the signer, user and verifier are also very small.
We propose a short signature scheme under the ring-SIS assumption in the standard model. Specifically, by revisiting an existing construction [Ducas and Micciancio, CRYPTO 2014], we demonstrate lattice-based signatures with improved reduction loss. As far as we know, there are no ways to use multiple tags in the signature simulation of security proof in the lattice tag-based signatures. We address the tag-collision possibility in the lattice setting, which improves reduction loss. Our scheme generates tags from messages by constructing a scheme under a mild security condition that is existentially unforgeable against random message attack with auxiliary information. Thus our scheme can reduce the signature size since it does not need to send tags with the signatures. Our scheme has short signature sizes of O(1) and achieves tighter reduction loss than that of Ducas et al.'s scheme. Our proposed scheme has two variants. Our scheme with one property has tighter reduction and the same verification key size of O(log n) as that of Ducas et al.'s scheme, where n is the security parameter. Our scheme with the other property achieves much tighter reduction loss of O(Q/n) and verification key size of O(n), where Q is the number of signing queries.
In recent years, there has been much focus on developing core cryptographic primitives based on lattice assumptions, driven by the NIST call for post-quantum key encapsulation and digital signature algorithms. However, more work must be conducted on efficient privacy-preserving protocols based on quantum-safe assumptions. Electronic voting is one such privacy-preserving protocol whose adoption is increasing across the democratic world. E-voting offers both a fast and convenient alternative to postal voting whilst further ensuring cryptographic privacy of votes and offering full verifiability of the process. Owing to the sensitivity of voting and its infrastructure challenges, it is crucial to ensure security against quantum computers is baked into e-voting solutions. We present an e-voting scheme from quantum-safe assumptions based on the hardness of the RLWE and NTRU lattice problems, providing concrete parameters and an efficient implementation. Our design achieves a factor 5.3 × reduction in ciphertext size, 2.5 × reduction in total communication cost, and 2 × reduction in total computation time compared to the state-of-the-art lattice-based voting scheme by Aranha et al. (ACM CCS 2023). We argue that the efficiency of this scheme makes it suitable for real-world elections. Our scheme makes use of non-ternary NTRU secrets to achieve optimal parameters. In order to compute the security of our design, we extend the ternary-NTRU work of Ducas and van Woerden (ASIACRYPT 2021) by determining the concrete fatigue point (for general secrets) of NTRU to be q = 0.0058 · σ 2 · d 2.484 (above which parameters become overstretched) for modulus q , ring dimension d , and secrets drawn from a Gaussian of parameter σ . We consider this relation to be of independent interest and demonstrate its significance by improving the efficiency of the (partially) blind signature scheme by del Pino and Katsumata (CRYPTO 2022).