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

TURKISH JOURNAL OF MATHEMATICS

A novel 3-pass identification scheme and signature scheme based on multivariate quadratic polynomials

Sedat Akleylek, Meryem Soysaldı

Published Jan 18, 2019• 10 citations
Publisher

Abstract

Identification schemes are used to verify identities of parties and signatures. Recently, systems based on multivariate polynomials have been preferred in identification schemes due to their resistance against quantum attacks. In this paper, we propose a quantum secure $3$-pass identification scheme based on multivariate quadratic polynomials. We compare the proposed scheme with the previous ones in view of memory requirements, communication length, and computation time. We define an efficiency metric by using impersonation probability and computation time. According to the comparison results, the proposed one has the same computation time as that of Monteiro et al. and reduces impersonation probability compared to the work of Sakumoto et al. We also propose a new signature scheme constructed from the proposed identification scheme. In addition, we compare the signature scheme with the previous schemes in view of signature and key sizes. We improve the signature size compared to that given in previous work by Chen et al.

DOI
10.3906/mat-1803-92

Related papers

Identification schemes in the post-quantum area based on multivariate polynomials with applications in cloud and IoT

Sedat Akleylek, Meryem Soysaldı

In this chapter, we survey the identification schemes based on multivariate polynomials over a finite field. We provide some basic definitions needed to construct the structure of identification schemes based on multivariate polynomials over a finite field. Then, we provide a brief survey of identification schemes based on multivariate polynomials by considering applications in different platforms. We analyze them in view of the zero knowledge property and the number of passes such as 3-pass and 5-pass. By considering open problems in the literature, we propose a novel identification scheme based on multivariate quadratic polynomials. Then, we compare them in terms of efficiency. We also provide a discussion for cloud, IoT, and big data applications of quantum secure identification schemes.

Institution of Engineering and Technology eBooks•Mar 11, 2019•1 citation

Quantum Attack-Resistent Certificateless Multi-Receiver Signcryption Scheme

Huixian Li, Xubao Chen, Liaojun Pang +1 more

The existing certificateless signcryption schemes were designed mainly based on the traditional public key cryptography, in which the security relies on the hard problems, such as factor decomposition and discrete logarithm. However, these problems will be easily solved by the quantum computing. So the existing certificateless signcryption schemes are vulnerable to the quantum attack. Multivariate public key cryptography (MPKC), which can resist the quantum attack, is one of the alternative solutions to guarantee the security of communications in the post-quantum age. Motivated by these concerns, we proposed a new construction of the certificateless multi-receiver signcryption scheme (CLMSC) based on MPKC. The new scheme inherits the security of MPKC, which can withstand the quantum attack. Multivariate quadratic polynomial operations, which have lower computation complexity than bilinear pairing operations, are employed in signcrypting a message for a certain number of receivers in our scheme. Security analysis shows that our scheme is a secure MPKC-based scheme. We proved its security under the hardness of the Multivariate Quadratic (MQ) problem and its unforgeability under the Isomorphism of Polynomials (IP) assumption in the random oracle model. The analysis results show that our scheme also has the security properties of non-repudiation, perfect forward secrecy, perfect backward secrecy and public verifiability. Compared with the existing schemes in terms of computation complexity and ciphertext length, our scheme is more efficient, which makes it suitable for terminals with low computation capacity like smart cards.

PLoS ONE•Jun 5, 2013•6 citations

Designing High-Performance Identity-Based Quantum Signature Protocol With Strong Security

Sunil Prajapat, Pankaj Kumar, Sandeep Kumar +3 more

Due to the rapid advancement of quantum computers, there has been a furious race for quantum technologies in academia and industry. Quantum cryptography is an important tool for achieving security services during quantum communication. Designated verifier signature, a variant of quantum cryptography, is very useful in applications like the Internet of Things (IoT) and auctions. An identity-based quantum-designated verifier signature (QDVS) scheme is suggested in this work. Our protocol features security attributes like eavesdropping, non-repudiation, designated verification, and hiding sources attacks. Additionally, it is protected from attacks on forgery, inter-resending, and impersonation. The proposed scheme benefits from the traditional designated verifier signature schemes. In the proposed scheme, the signer encrypts a message with his or her private key, and the designated verifier validates the accompanying QDVS using the signer’s public key, which is the signer’s name or email address, which makes the quantum signature system’s key management simpler. It uses an entangled state while signing and verifying the signature; however, the verifier is not required to compare quantum states. A detailed comparison analysis with other similar schemes provides more security for the proposed scheme. Furthermore, the proposed scheme’s effectiveness and feasibility are validated using quantum simulations.

IEEE Access•Jan 1, 2024•36 citations

Investigating the Security of MQDSS: A Multivariate Quadratic Digital Signature Scheme in the Quantum Setting

Stuti Kumari, Sumit Kumar Debnath

Much of the assumed safety and security of classical cryptographic building blocks depends on the hardness of number-theoretical problems. However, Shor's algorithm proves that conventional cryptographic systems are no longer secure under quantum systems. As a response to this challenge, researchers started to develop a new cryptographic method known as post-quantum cryptography (PQC), which is based on hard computational problem that can resist the quantum threats. The multivariate public-key cryptography (MPKC) is one such candidate. The theoretical security of MPKC comes from the intractability of the MQ problem, which is believed to be NP-hard. Herein, we analyze the security of MQDSS signature scheme proposed by Chen et al. We investigate the proof of security of MQDSS, assuming that the malicious party can access to the quantum resources. We demonstrate that in its current state, MQDSS has quite a few insecurities in the quantum setting. In response to the proposed threats, we pitch possible modifications to MQDSS. We emphasize that our proposed security threats do not restrict themselves to MQDSS, and can be extended to other MPKC and PQC based cryptographic primitives.

International Journal of Drug Delivery Technology•May 20, 2026•0 citations

Quantum Secure Proxy-Multi Signature Scheme

Satyam Omar, Sanjay Kumar, Prince Solanki +1 more

Authentication of the information is an important objective in distributed environments. In these environments when the multi-device authentication is required, a significant role is played by proxy-multi signature in diminishing the communication and computation overload. In this paper, we propose the first quantum-resistant proxy-multi signature scheme based on multivariate public key cryptography (MPKC). The security of this scheme depends on the hardness of multivariate quadratic problem. The proposed scheme enjoys the fulfilment of all the required security properties.

International Conference on Communication, Computing and Energy Efficient Technologies (I3CEET)•Sep 20, 2024•0 citations

A New 3-pass Zero-knowledge Lattice-based Identification Scheme

Sedat Akleylek, Meryem Soysaldı

It is very important that the communicating parties are able to verify their identity in order to communicate with each other properly. Identification schemes are used for this purpose. The identification schemes, widely used in applications, are based on the hardness of the discrete logarithm or integer factorization problem. Shor proposed an algorithm that solve discrete logarithm and factorization problems by using quantum computers in polynomial-time. Therefore, there is a huge need for identification schemes which can be used post-quantum. In this paper, the identification schemes based on hardness of different lattice problems are surveyed. In addition, a new zero-knowledge lattice-based identification scheme is proposed.

International Conference on Computer Science and Engineering (UBMK)•Sep 1, 2019•1 citation
Identification schemes are used to verify identities of parties and signatures. Recently, systems based on multivariate polynomials have been preferred in identification schemes due to their resistance against quantum attacks. In this paper, we propose a quantum secure 333-pass identification scheme based on multivariate quadratic polynomials. We compare the proposed scheme with the previous ones in view of memory requirements, communication length, and computation time. We define an efficiency metric by using impersonation probability and computation time. According to the comparison results, the proposed one has the same computation time as that of Monteiro et al. and reduces impersonation probability compared to the work of Sakumoto et al. We also propose a new signature scheme constructed from the proposed identification scheme. In addition, we compare the signature scheme with the previous schemes in view of signature and key sizes. We improve the signature size compared to that given in previous work by Chen et al.
In this chapter, we survey the identification schemes based on multivariate polynomials over a finite field. We provide some basic definitions needed to construct the structure of identification schemes based on multivariate polynomials over a finite field. Then, we provide a brief survey of identification schemes based on multivariate polynomials by considering applications in different platforms. We analyze them in view of the zero knowledge property and the number of passes such as 3-pass and 5-pass. By considering open problems in the literature, we propose a novel identification scheme based on multivariate quadratic polynomials. Then, we compare them in terms of efficiency. We also provide a discussion for cloud, IoT, and big data applications of quantum secure identification schemes.
The existing certificateless signcryption schemes were designed mainly based on the traditional public key cryptography, in which the security relies on the hard problems, such as factor decomposition and discrete logarithm. However, these problems will be easily solved by the quantum computing. So the existing certificateless signcryption schemes are vulnerable to the quantum attack. Multivariate public key cryptography (MPKC), which can resist the quantum attack, is one of the alternative solutions to guarantee the security of communications in the post-quantum age. Motivated by these concerns, we proposed a new construction of the certificateless multi-receiver signcryption scheme (CLMSC) based on MPKC. The new scheme inherits the security of MPKC, which can withstand the quantum attack. Multivariate quadratic polynomial operations, which have lower computation complexity than bilinear pairing operations, are employed in signcrypting a message for a certain number of receivers in our scheme. Security analysis shows that our scheme is a secure MPKC-based scheme. We proved its security under the hardness of the Multivariate Quadratic (MQ) problem and its unforgeability under the Isomorphism of Polynomials (IP) assumption in the random oracle model. The analysis results show that our scheme also has the security properties of non-repudiation, perfect forward secrecy, perfect backward secrecy and public verifiability. Compared with the existing schemes in terms of computation complexity and ciphertext length, our scheme is more efficient, which makes it suitable for terminals with low computation capacity like smart cards.
Due to the rapid advancement of quantum computers, there has been a furious race for quantum technologies in academia and industry. Quantum cryptography is an important tool for achieving security services during quantum communication. Designated verifier signature, a variant of quantum cryptography, is very useful in applications like the Internet of Things (IoT) and auctions. An identity-based quantum-designated verifier signature (QDVS) scheme is suggested in this work. Our protocol features security attributes like eavesdropping, non-repudiation, designated verification, and hiding sources attacks. Additionally, it is protected from attacks on forgery, inter-resending, and impersonation. The proposed scheme benefits from the traditional designated verifier signature schemes. In the proposed scheme, the signer encrypts a message with his or her private key, and the designated verifier validates the accompanying QDVS using the signer’s public key, which is the signer’s name or email address, which makes the quantum signature system’s key management simpler. It uses an entangled state while signing and verifying the signature; however, the verifier is not required to compare quantum states. A detailed comparison analysis with other similar schemes provides more security for the proposed scheme. Furthermore, the proposed scheme’s effectiveness and feasibility are validated using quantum simulations.
Much of the assumed safety and security of classical cryptographic building blocks depends on the hardness of number-theoretical problems. However, Shor's algorithm proves that conventional cryptographic systems are no longer secure under quantum systems. As a response to this challenge, researchers started to develop a new cryptographic method known as post-quantum cryptography (PQC), which is based on hard computational problem that can resist the quantum threats. The multivariate public-key cryptography (MPKC) is one such candidate. The theoretical security of MPKC comes from the intractability of the MQ problem, which is believed to be NP-hard. Herein, we analyze the security of MQDSS signature scheme proposed by Chen et al. We investigate the proof of security of MQDSS, assuming that the malicious party can access to the quantum resources. We demonstrate that in its current state, MQDSS has quite a few insecurities in the quantum setting. In response to the proposed threats, we pitch possible modifications to MQDSS. We emphasize that our proposed security threats do not restrict themselves to MQDSS, and can be extended to other MPKC and PQC based cryptographic primitives.
Authentication of the information is an important objective in distributed environments. In these environments when the multi-device authentication is required, a significant role is played by proxy-multi signature in diminishing the communication and computation overload. In this paper, we propose the first quantum-resistant proxy-multi signature scheme based on multivariate public key cryptography (MPKC). The security of this scheme depends on the hardness of multivariate quadratic problem. The proposed scheme enjoys the fulfilment of all the required security properties.
It is very important that the communicating parties are able to verify their identity in order to communicate with each other properly. Identification schemes are used for this purpose. The identification schemes, widely used in applications, are based on the hardness of the discrete logarithm or integer factorization problem. Shor proposed an algorithm that solve discrete logarithm and factorization problems by using quantum computers in polynomial-time. Therefore, there is a huge need for identification schemes which can be used post-quantum. In this paper, the identification schemes based on hardness of different lattice problems are surveyed. In addition, a new zero-knowledge lattice-based identification scheme is proposed.