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

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

Masayuki Fukumitsu, Shingo Hasegawa

Published Jan 1, 2021• 0 citations
OpenAlex

Abstract

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.

Related papers

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

Single-round Lattice-based Multisignatures

Kittiphon Phalakarn, Vorapong Suppakitpaisarn, M.A. Hasan

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.

International Symposium on Computing and Networking Workshops (CANDARW)•Nov 1, 2021•1 citation

Traceable signatures from lattices

Nam Tran, Khoa Nguyen, Dongxi Liu +2 more

Traceable signatures (Kiayas et al., 2004) is an anonymous digital signature system that extends the tracing power of opening authority in group signatures. There are many known constructions of traceable signatures but all are based on number-theoretical/pairing assumptions. For such reason, they may not be secure in the presence of quantum computers. This work revisits the notion of traceable signatures and presents a lattice-based construction provably secure in the quantum random oracle model (QROM).

arXiv:2510.24101•Computer Standards & Interfaces•Nov 17, 2025•1 citation

Quantum resilient security proofs

Hélder Vieira de Freitas Maia Martins

Recent developments in quantum computers pose an imminent threat to cryptography since many widely used cryptographic schemes will no longer be secure. This worrisome scenario motivated a growing interest in the field of post-quantum cryptography, which aims to design cryptosystems that are postquantum secure, i.e. secure against quantum-capable adversaries. While finding post-quantum computational hardness assumptions is pivotal to achieve this goal, an issue that is often overlooked is provable security. In fact, to prove that the post-quantum computational hardness necessarily implies post-quantum security of the derived cryptosystem, the reduction argument that establishes this implication also needs to be post-quantum. As such, many new methods have been devised in the last few years to handle this adaptation to the quantum setting. In particular, the quantum analogue of the Random Oracle Model has garnered special interest, as it is the foundation of many cryptographic schemes, from public-key encryption to digital signatures. It is also very problematic and usually the main culprit of the failure of security proofs when transitioning to the quantum setting. This work offers a comprehensive exposition on the most influential techniques developed in the last decade to enable or facilitate the construction of security proofs in the Quantum Random Oracle Model (QROM). Each presented technique offers an unique purpose and a solution to a problem provoked by the QROM, and, as such, as a whole, this works allows for an understanding of the most common strategies to construct these type of security proofs. This is accomplished by presenting and analyzing the security proof of three cryptographic schemes set in this model, which underlines the central role these techniques take in provable quantum security.

•Dec 21, 2024•0 citations

Lattice-based logarithmic-size forward-secure ring signatures in QROM

Priyanka Dutta, Willy Susilo, Fuchun Guo +1 more

Ring signatures, a novel cryptographic primitive, were introduced by Rivest, Shamir, and Tauman at ASIACRYPT 2001. It allows a member of a group to sign a message on behalf of an ad-hoc group of users, known as a ring, without revealing its identity. Ring signatures, initially introduced for applications such as whistle-blowing and confidential disclosures, have since gained significant relevance and widespread adoption across various domains, including blockchain technologies, ad-hoc networks, anonymous transactions, location-based services, cloud computing platforms, and outsourced computation. However, traditional ring signatures are vulnerable if the signers’ keys are compromised. To resolve this vulnerability, Liu and Wong introduced the notion of forward-secure ring signatures at IJNS 2008. Forward-security ensures that even if a signer’s secret key is compromised, signatures generated in prior time periods remain secure. It significantly reduces the damage caused by secret key exposure, making it crucial for long-term security in applications such as whistle-blowing or anonymous authentication. However, most existing forward-secure ring signature schemes are based on number-theoretic assumptions, making them vulnerable to quantum adversaries. Yu and Wang proposed a quantum-safe forward-secure ring signature scheme at ICICS 2023, and Yu et al. further extended this work in Computer Networks (2025), retaining the same ring signature scheme with forward security. But the scheme suffers from large signatures that grow linearly with the ring size. In this paper, we propose a lattice-based forward-secure ring signature scheme in the quantum random oracle model ( QROM ) that simultaneously achieves security against quantum adversaries and compact signature size. Notably, the signature size is logarithmic in the number of members in the ring, enabling significantly better scalability compared to prior constructions.

Theoretical Computer Science•Jan 29, 2026•2 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
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.
Traceable signatures (Kiayas et al., 2004) is an anonymous digital signature system that extends the tracing power of opening authority in group signatures. There are many known constructions of traceable signatures but all are based on number-theoretical/pairing assumptions. For such reason, they may not be secure in the presence of quantum computers. This work revisits the notion of traceable signatures and presents a lattice-based construction provably secure in the quantum random oracle model (QROM).
Recent developments in quantum computers pose an imminent threat to cryptography since many widely used cryptographic schemes will no longer be secure. This worrisome scenario motivated a growing interest in the field of post-quantum cryptography, which aims to design cryptosystems that are postquantum secure, i.e. secure against quantum-capable adversaries. While finding post-quantum computational hardness assumptions is pivotal to achieve this goal, an issue that is often overlooked is provable security. In fact, to prove that the post-quantum computational hardness necessarily implies post-quantum security of the derived cryptosystem, the reduction argument that establishes this implication also needs to be post-quantum. As such, many new methods have been devised in the last few years to handle this adaptation to the quantum setting. In particular, the quantum analogue of the Random Oracle Model has garnered special interest, as it is the foundation of many cryptographic schemes, from public-key encryption to digital signatures. It is also very problematic and usually the main culprit of the failure of security proofs when transitioning to the quantum setting. This work offers a comprehensive exposition on the most influential techniques developed in the last decade to enable or facilitate the construction of security proofs in the Quantum Random Oracle Model (QROM). Each presented technique offers an unique purpose and a solution to a problem provoked by the QROM, and, as such, as a whole, this works allows for an understanding of the most common strategies to construct these type of security proofs. This is accomplished by presenting and analyzing the security proof of three cryptographic schemes set in this model, which underlines the central role these techniques take in provable quantum security.
Ring signatures, a novel cryptographic primitive, were introduced by Rivest, Shamir, and Tauman at ASIACRYPT 2001. It allows a member of a group to sign a message on behalf of an ad-hoc group of users, known as a ring, without revealing its identity. Ring signatures, initially introduced for applications such as whistle-blowing and confidential disclosures, have since gained significant relevance and widespread adoption across various domains, including blockchain technologies, ad-hoc networks, anonymous transactions, location-based services, cloud computing platforms, and outsourced computation. However, traditional ring signatures are vulnerable if the signers’ keys are compromised. To resolve this vulnerability, Liu and Wong introduced the notion of forward-secure ring signatures at IJNS 2008. Forward-security ensures that even if a signer’s secret key is compromised, signatures generated in prior time periods remain secure. It significantly reduces the damage caused by secret key exposure, making it crucial for long-term security in applications such as whistle-blowing or anonymous authentication. However, most existing forward-secure ring signature schemes are based on number-theoretic assumptions, making them vulnerable to quantum adversaries. Yu and Wang proposed a quantum-safe forward-secure ring signature scheme at ICICS 2023, and Yu et al. further extended this work in Computer Networks (2025), retaining the same ring signature scheme with forward security. But the scheme suffers from large signatures that grow linearly with the ring size. In this paper, we propose a lattice-based forward-secure ring signature scheme in the quantum random oracle model ( QROM ) that simultaneously achieves security against quantum adversaries and compact signature size. Notably, the signature size is logarithmic in the number of members in the ring, enabling significantly better scalability compared to prior constructions.
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.