Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Symposium on Computing and Networking Workshops (CANDARW)

Single-round Lattice-based Multisignatures

Kittiphon Phalakarn, Vorapong Suppakitpaisarn, M.A. Hasan

Published Nov 1, 2021• 1 citation
Publisher

Abstract

This work presents a provably-secure lattice-based multisignature scheme which requires only a single round of communication, whereas the existing works need two or three rounds. The reduction in the number of rounds for the proposed scheme is achieved by utilizing lattice trapdoors. In order to generate multisignatures securely, our scheme however requires an honest centralized server that maintains the trapdoor of a shared matrix used in the scheme.

DOI
10.1109/candarw53999.2021.00068

Related papers

A Lattice-based Provably Secure Multisignature Scheme in Quantum Random Oracle Model.

Masayuki Fukumitsu, Shingo Hasegawa

The multisignature schemes are attracted to utilize in some cryptographic applications such as the blockchain. Though the lattice-based constructions of multisignature schemes exist as quantum-secure multisignature, a multisignature scheme whose security is proven in the quantum random oracle model (QROM), rather than the classical random oracle model (CROM), is not known.

•Jan 1, 2021•0 citations

A Tightly-Secure Lattice-Based Multisignature

Masayuki Fukumitsu, Shingo Hasegawa

Multisignatures enable multiple users to sign a message in an interactive manner. Many instantiations are proposed for multisignatures, however, most of them are quantum-insecure, because these are based on the integer factoring assumption or the discrete logarithm assumption. Although there exist some constructions based on the lattice problems, which are believed to be quantum-secure, their security reductions are loose. In this paper, we construct a first lattice-based multisignature which has a tight security reduction. Our basic strategy is combining the multisignature scheme proposed by El Bansarkhani and Sturm with the lattice-based standard signature scheme by Abdalla, Fouque, Lyubashevsky and Tibouchi which has a tight security reduction from the Ring-LWE (Ring Learning with Error) assumption.

•Jul 2, 2019•25 citations

Tighter Reduction for Lattice-Based Multisignature

Masayuki Fukumitsu, Shingo Hasegawa

Multisignatures enable multiple users to sign a message interactively. Many instantiations are proposed for multisignatures, however, most of them are quantum-insecure, because these are based on the integer factoring assumption or the discrete logarithm assumption. Although there exist some constructions based on the lattice problems, which are believed to be quantum-secure, their security reductions are loose. In this paper, we aim to improve the security reduction of lattice-based multisignature schemes concerning tightness. Our basic strategy is combining the multisignature scheme proposed by El Bansarkhani and Sturm with the lattice-based signature scheme by Abdalla, Fouque, Lyubashevsky, and Tibouchi which has a tight security reduction from the Ring-LWE (Ring Learning with Errors) assumption. Our result shows that proof techniques for standard signature schemes can be applied to multisignature schemes, then we can improve the polynomial loss factor concerning the Ring-LWE assumption. Our second result is to address the problem of security proofs of existing lattice-based multisignature schemes pointed out by Damgård, Orlandi, Takahashi, and Tibouchi. We employ a new cryptographic assumption called the Rejected-Ring-LWE assumption, to complete the security proof.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•May 24, 2021•0 citations

A Lattice-Based Provably Secure Multisignature Scheme in Quantum Random Oracle Model

Masayuki Fukumitsu, Shingo Hasegawa

Lecture notes in computer science•Jan 1, 2020•34 citations

Identity-Based Blind Multisignature From Lattices

Raylin Tso, Ziyuan Liu, Yi‐Fan Tseng

Blind multisignature (BMS), first introduced by Horster et al, constitutes a crucial primitive that allows a user to generate a signature of a message from multiple signers, while the signers cannot obtain any information about the message. With these useful properties, blind multisignature is suitable for electronic payments and electronic voting. However, most of the current BMS schemes may be attacked by quantum computers in the future because they are based on traditional number theories, such as discrete logarithm assumption and large integer factor assumption. In this work, we first formalize the notion and the sound security models of the identity-based blind multisignature scheme (IDBMS). Then we present an instantiation based on lattices, along with rigorous proofs of the blindness and unforgeability under the lattice hard assumption (short integer solution, SIS), which is considered to remain secure under quantum computer attacks. To the best of our knowledge, it is the first identity-based quantum-resistant scheme that has the advantages of blind signature and multisignature.

IEEE Access•Jan 1, 2019•9 citations

Lattice-based identity-based ring signature without trapdoors

Lili Zhang, Zhongwen Li, Yongxuan Sang

So far, most ring signature schemes rely on hard number theory problems, such as discrete logarithm, bilinear pairings and so on. Unfortunately, the above underlying number theory problems will be solvable in the post quantum era. Lattice-based cryptography is a hotspot of research recently, due to its implementation simplicity and provable security reductions. When the hash-and-sign signature scheme was constructed based on the hardness of worst-case lattice problems, provably secure lattice-based ring signature schemes were finally constructed. However, the hash-and-sign ring signatures were rather inefficient (with megabytes long signatures). In this paper, we propose an alternative method for constructing lattice-based and identity-based ring signature scheme which does not use the hash-and-sign methodology. In the random oracle model, the proposed signature scheme based on the problem in general lattices is unforgeable and holds anonymity. Compared with the previous instantiations of the hash-and-sign ring signature schemes, the lengths of secret key, public key and signatures in the proposed scheme are much shorter. The signing algorithm is quite simple, with matrix-vector multiplications and rejection samplings.

International Journal of High Performance Computing and Networking•Jan 1, 2018•0 citations
This work presents a provably-secure lattice-based multisignature scheme which requires only a single round of communication, whereas the existing works need two or three rounds. The reduction in the number of rounds for the proposed scheme is achieved by utilizing lattice trapdoors. In order to generate multisignatures securely, our scheme however requires an honest centralized server that maintains the trapdoor of a shared matrix used in the scheme.
Multisignatures enable multiple users to sign a message in an interactive manner. Many instantiations are proposed for multisignatures, however, most of them are quantum-insecure, because these are based on the integer factoring assumption or the discrete logarithm assumption. Although there exist some constructions based on the lattice problems, which are believed to be quantum-secure, their security reductions are loose. In this paper, we construct a first lattice-based multisignature which has a tight security reduction. Our basic strategy is combining the multisignature scheme proposed by El Bansarkhani and Sturm with the lattice-based standard signature scheme by Abdalla, Fouque, Lyubashevsky and Tibouchi which has a tight security reduction from the Ring-LWE (Ring Learning with Error) assumption.
Multisignatures enable multiple users to sign a message interactively. Many instantiations are proposed for multisignatures, however, most of them are quantum-insecure, because these are based on the integer factoring assumption or the discrete logarithm assumption. Although there exist some constructions based on the lattice problems, which are believed to be quantum-secure, their security reductions are loose. In this paper, we aim to improve the security reduction of lattice-based multisignature schemes concerning tightness. Our basic strategy is combining the multisignature scheme proposed by El Bansarkhani and Sturm with the lattice-based signature scheme by Abdalla, Fouque, Lyubashevsky, and Tibouchi which has a tight security reduction from the Ring-LWE (Ring Learning with Errors) assumption. Our result shows that proof techniques for standard signature schemes can be applied to multisignature schemes, then we can improve the polynomial loss factor concerning the Ring-LWE assumption. Our second result is to address the problem of security proofs of existing lattice-based multisignature schemes pointed out by Damgård, Orlandi, Takahashi, and Tibouchi. We employ a new cryptographic assumption called the Rejected-Ring-LWE assumption, to complete the security proof.
Blind multisignature (BMS), first introduced by Horster et al, constitutes a crucial primitive that allows a user to generate a signature of a message from multiple signers, while the signers cannot obtain any information about the message. With these useful properties, blind multisignature is suitable for electronic payments and electronic voting. However, most of the current BMS schemes may be attacked by quantum computers in the future because they are based on traditional number theories, such as discrete logarithm assumption and large integer factor assumption. In this work, we first formalize the notion and the sound security models of the identity-based blind multisignature scheme (IDBMS). Then we present an instantiation based on lattices, along with rigorous proofs of the blindness and unforgeability under the lattice hard assumption (short integer solution, SIS), which is considered to remain secure under quantum computer attacks. To the best of our knowledge, it is the first identity-based quantum-resistant scheme that has the advantages of blind signature and multisignature.
So far, most ring signature schemes rely on hard number theory problems, such as discrete logarithm, bilinear pairings and so on. Unfortunately, the above underlying number theory problems will be solvable in the post quantum era. Lattice-based cryptography is a hotspot of research recently, due to its implementation simplicity and provable security reductions. When the hash-and-sign signature scheme was constructed based on the hardness of worst-case lattice problems, provably secure lattice-based ring signature schemes were finally constructed. However, the hash-and-sign ring signatures were rather inefficient (with megabytes long signatures). In this paper, we propose an alternative method for constructing lattice-based and identity-based ring signature scheme which does not use the hash-and-sign methodology. In the random oracle model, the proposed signature scheme based on the problem in general lattices is unforgeable and holds anonymity. Compared with the previous instantiations of the hash-and-sign ring signature schemes, the lengths of secret key, public key and signatures in the proposed scheme are much shorter. The signing algorithm is quite simple, with matrix-vector multiplications and rejection samplings.