Figures
Abstract
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.
Citation: Li H, Chen X, Pang L, Shi W (2013) Quantum Attack-Resistent Certificateless Multi-Receiver Signcryption Scheme. PLoS ONE 8(6): e49141. https://doi.org/10.1371/journal.pone.0049141
Editor: Gerardo Adesso, University of Nottingham, United Kingdom
Received: September 12, 2012; Accepted: March 22, 2013; Published: June 5, 2013
Copyright: © 2013 Li et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Funding: This work was supported by Natural Science Foundation of China under Grant Nos. 61103178 and 60803151, and the Research Fund for the Doctoral Program of Higher Education of China under Grant No. 20096102120045. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
Competing interests: The authors have declared that no competing interests exist.
Introduction
Signcryption is a cryptographic primitive that provides both signature and encryption simultaneously to sensitive information at a lower computation and communication overhead than the traditional signature-then-encryption approach [1]. In terms of the implementation method, there are two kinds of signcryption schemes. One is based on traditional public key infrastructure [2], which causes the costly certificate management problem; the other is based on identity-based public key cryptography [3], which avoids the certificate management, but induces the key escrow problem.
In 2003, Al-Riyami et al. [4] proposed the certificateless cryptosystem (CLC). In their certificateless cryptosystem, a user’s secret key is derived from two parts: one is an identity-based secret key generated by Key Generation Center (KGC) and the other is a self-generated secret key. Thus CLC solves the key escrow problem as well as the certificate management problem, and it also reduces the implementation complexity of the cryptosystem. In 2008, Barbosa et al. [5] first proposed the certificateless signcryption scheme (CLSC) based on bilinear pairing operations. However, they did not give the security proof of their scheme. Since then, certificateless signcryption schemes [6]–[7] have been studied extensively. In 2010, Li et al. proposed another CLSC [8] and proved its security formally. However, these schemes [5]–[8] are inefficient in computation because they use the bilinear pairing operation, a quite complex computation. Selvi et al. [9] and Jing et al. [10] constructed an efficient CLSC based on the CDH (Computational Diffie-Hellman) problem without bilinear pairing operations, respectively. At the same time, they proved their schemes’ security in the random oracle model. However, their schemes are only single-receiver ones. If there are multiple receivers at the same time, these schemes need to signcrypt the same message for each receiver separately, so they are very inefficient for the multi-receiver scenario. In order to improve the efficiency of signcryption in the multi-receiver setting, Selvi et al. [11] proposed the certificateless multi-receiver signcryption scheme (CLMSC), and this scheme only needs two bilinear pairing operations and (t+2) exponentiation operations (t denotes the number of the receivers) in the signcryption and designcryption phases. However, they found that this scheme cannot resist the forgery attack and then presented an enhanced scheme [12] later. But Miao et al. [13] showed that the enhanced scheme is still insecure against the internal attack and provided a detailed security analysis.
To date, the implementations of almost all certificateless signcryption schemes [5]–[13] are based on traditional public key cryptosystems, in which the security mainly relies on the hard problems, such as factor decomposition and discrete logarithm. However, in 1994, Shor [14] proposed a polynomial-time quantum algorithm that can successfully factor large integers, which shows that quantum computing has brought a potential challenge to these hard mathematical problems. Once quantum computers is developed successfully, they will pose a fatal threat to the security of almost all certificateless signcryption schemes which are based on public key cryptosystems such as RSA, ElGamal and ECC. So it is more and more urgent to design a certificateless signcryption scheme that can resist quantum attack. Multivariate public key cryptography (MPKC), which can resist quantum attack, is one of the alternative solutions to guarantee the security of communications in the post-quantum age. The security of MPKC is based on the Multivariate Quadratic (MQ) problem and the Isomorphism of Polynomials (IP) problem. Compared with identity-based cryptography, MPKC has lower calculation complexity and is higher in efficiency, which makes MPKC well suitable to implement strongly secure communications for low-end devices. The MPKC-based schemes have been studied widely, and several excellent schemes have been proposed. For example, SFLASH, a signature scheme based on MPKC, has been recommended by the NESSIE European Consortium since 2003 as the best known solution for implementation on low-cost smart cards [15].
Our contribution.
Motivated by these concerns, we employ MPKC to construct an efficient quantum attack-resistent certificateless multi-receiver signcryption scheme, which combines the certificateless cryptosystem and MPKC. The new scheme not only has the advantage of the certificateless cryptosystem, which avoids the problem of key management, but also resists quantum attack only with light-weight computation like the multivariate quadratic polynomial operations. In our scheme, 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. Therefore, our scheme is more efficient than the existing CLMSC schemes, and it is suitable for mobile terminals with low computing power. Security analysis shows that our scheme is a secure MPKC-based multi-receiver signcryption scheme, and it also has the important security properties such as message confidentiality, unforgeability, non-repudiation, perfect forward secrecy, perfect backward secrecy and public verifiability.
Preliminaries
1 MQ Problem and IP Problem
In this section, we shall briefly recall some basic concepts of MPKC including multivariate polynomial equations, the MQ problem and the IP problem.
Let G be a finite field of prime order p. Let n be the number of variables, namely, x1, x2, …, xn in the multivariate polynomial equation, g be the number of the multivariate polynomial equations, and d be the degree of the multivariate polynomial equations.
A tuple of multivariate quadratic polynomials consists of a finite ordered set of polynomials of the following form:(1)where i = 1, 2, …, g, and xj, xk∈G, and the coefficients {aijk, bij, ci} are over G [16]. Then, the MQ problem can be described as follows:
Definition 1.
(MQ). Given a tuple P = (p1, p2, …, pg) of g multivariate quadratic polynomials with n unknowns defined over G, and the image y = (p1(z), p2(z), …, pg(z)) of an element z randomly chosen from Gn(Gn denotes the nth extension of G), the problem to find an element x of Gn such that y = (p1(x), p2(x), …, pg(x)) is called the MQ problem [16].
Solving a set of randomly chosen quadratic equations with several variables over a finite field is considered as an NP hard problem [17].
Definition 2.
(IP). Given P and Q be two public sets of n quadratic equations with n variables over G, if P and Q are isomorphism, then (
denotes composition of mappings), where T and V are two invertible affine transformations on
. Finding (T, V) for P, Q such that
is called the IP problem [18].
2 Multivariate Public Key Cryptosystem
In a primitive multivariate public key cryptosystem [19], for a user U with identity IDU, his/her public key is and his/her secret key is the 3-tuple
The encryption operation for a message m is denoted by σ = PU(m) and the corresponding decryption operation for the ciphertext σ is denoted by
. For example, Alice wants to send a message m to Bob with identity IDB. Alice computes the ciphertext
with Bob’s public key. Bob receives the ciphertext σ from Alice and then decrypts the ciphertext σ by computing
In a word, Bob computes
and
sequentially. At last, Bob obtains the plaintext message
3 Framework of CLMSC
A certificateless multi-receiver signcryption scheme consists of five probabilistic polynomial-time algorithms, namely Setup, Partial Key Extract, Key Extract, Signcrypt and De-signcrypt. According to the features of MPKC, we improve the existing CLMSC model, that is, KGC produces the common partial public key and partial secret key in the phase of Partial Key Extract.
- Setup: This algorithm is run by KGC. It takes as input a security parameter s and returns the public parameters params.
- Partial Key Extract: This algorithm is run by KGC. KGC first chooses a random number w as the system master key. Then it takes as input w and params and returns the common partial public key PPu and partial secret key PSu.
- Key Extract: This algorithm is run by a user U. It takes as input params, PPu, PSu and an identity IDu and returns the full public key PKu and the full secret key SKu of the user.
- Signcrypt: To securely send a message m to a group of receivers {ID1, ID2, …, IDt}, the sender S should run this algorithm to signcrypt it first. It takes as input params, a message m, the sender’s identity IDS, the full keys PKu and SKu of the sender, and lists of the receiver identities and their public keys, and returns a ciphertext σ.
- De-signcrypt: This algorithm takes as input a ciphertext σ, the receiver’s identity IDi, the receiver’s full keys PKi and SKi, the identity IDs and the public key PKs of the sender, and returns either a plaintext m or an error symbol ⊥.
4 Security Model for CLMSC
Our security model is established based on Selvi et al.’s security model [11]. For a certificateless signcryption scheme, there are two types of attacks corresponding to two types of attackers, namely A1 and A2. In the attack of Type 1, A1 does not have access to the system master key, but he/she has the ability to replace the public key of any user with a value that he/she chooses arbitrarily. A2 has access to the master key, but he/she cannot change public key of any user.
Definition 3.
Confidentiality under the attack of Type 1. A certificateless multi-receiver signcryption scheme is Type-1-CCA2 secure if no probabilistic polynomial-time attacker A has a non-negligible advantage in winning the IND-CLMSC-CCA2-1 game [11].
For A, there are the following constraints. A can not have access to the master key w. No Extract Secret Key query is allowed on any of the challenge identities. No De-signcrypt query is allowed on the challenge ciphertext.
Definition 4.
Confidentiality under the attack of Type 2. A certificateless multi-receiver signcryption scheme is Type-2-CCA2 secure if no probabilistic polynomial-time attacker A has a non-negligible advantage in winning the IND-CLMSC-CCA2-2 game [11].
For A, there are the following constraints. No Extract Secret Key query is allowed on any of the challenge identities. No Replace Public Key query is allowed on any of the challenge identities. No De-signcrypt query is allowed on the challenge ciphertext.
Definition 5.
Unforgeability under the attack of Type 1. A certificateless multi-receiver signcryption scheme is Type-1-sEUF-CMA-1 secure if no probabilistic polynomial-time attacker A has a non-negligible advantage in winning the EUF-CLMSC-CMA-1 game [11].
For A, there are the following constraints. A can not have access to the master key w. No Extract Secret Key query is allowed on any of the challenge identities.
Definition 6.
Confidentiality under the attack of Type 2. A certificateless multi-receiver signcryption scheme is Type-2-sEUF-CMA-2 secure if no probabilistic polynomial-time attacker A has a non-negligible advantage in winning the EUF-CLMSC-CMA-2 game [11].
For A, there are the following constraints. No Extract Secret Key query is allowed on any of the challenge identities. No Replace Public Key query is allowed on any of the challenge identities.
Methods
In order to construct our scheme, we employed the Perturbed Matsumoto-Imai-Plus (PMI+) cryptosystem [20], which can resist the linearization attack, rank attacks, and the differential attack and is much faster than RSA and ECC. The new scheme that we proposed consists of five probabilistic polynomial-time algorithms, namely Setup, Partial Key Extract, Key Extract, Signcrypt and De-signcrypt. We shall give a detailed description of the proposed scheme as follows.
Setup.
Given a security parameter s as input, KGC returns a big positive integer q and a small positive integer p. Let G be a finite field of order q and characteristic two, and define two non-collision hash functions H1: and H2:
, where Gn is the nth extension of G and Gn+p is the (n+p)th extension of G. The positive integer n is the number of variables in the equation (1) and lm is the bit length of the message m. Then KGC selects a positive integer g to denote the number of equations. At last, KGC publishes the public parameters params denoted by
.
Partial Key Extract
- KGC selects a secure MPKC, which is PMI+ in our scheme. The system public key can be expressed as a typical multivariate quadratic system:
where T is a randomly chosen invertible affine transformation on
, V is a randomly chosen invertible affine transformation on
, and F is a public set of (n+p) quadratic equations with n variables over G. The system secret key is (T, F, V). The related parameters refer to [20].
- KGC randomly chooses T0 and V0, where T0 is a randomly chosen invertible affine transformation on
and V0 is a randomly chosen invertible affine transformation on
. Then, compute
.
is the system partial public key, and
is the system partial secret key. It is worth noting that KGC needs to compute the new system partial secret key when some user drops out of the group.
Key Extract.
Each user runs this algorithm to compute his/her full public and secret keys. The user U randomly chooses Tu and Vu, where Tu is an invertible affine transformation on and Vu is an invertible affine transformation on
. Then, compute the public key Fu of user U, that is,
, which should be sent to KGC. The secret key of user U is (
).
Signcrypt.
Suppose that Alice, whose identity is IDA, wants to signcrypt a message m to t different receivers denoted by L = {ID1, ID2, …, IDt}. Alice performs the following steps:
- Alice chooses
randomly, and computes
,
and
.
- For all IDi, i = 1, 2, …, t, compute
and
.
- Return ciphertext
.
De-signcrypt.
Each receiver IDi, i = 1, 2, …, t, uses his/her secret key to decrypt σ.
- IDi extracts his/her corresponding ciphertext information (S, Y, Z, Wi) according to his/her position in L.
- IDi computes
and checks whether the equation
holds. If it holds, IDi continues to decrypt σ as follows; otherwise, IDi outputs ⊥.
- IDi computes
and
.
- Check whether the equations
and
hold. If both of them hold, output
; otherwise, output ⊥.
Discussion
1 Correctness Analysis
Proof.
Upon receiving a ciphertext σ, each receiver IDi, i = 1, 2, …, t, extracts his/her own corresponding ciphertext information (S, Y, Z, Wi) from σ. According to the Signcrypt algorithm, we have , so the receiver IDi can compute
. It is worth noting that only the sender, Alice, can generate the correct Y such that
because only she knows her secret key
. The receiver, IDi, can decrypt the ciphertext by computing
and
. IDi can judge whether m′ is correct by checking whether
and
hold. Note that only IDi can obtain
correctly because only he/she knows his/her secret key
. Therefore, the De-signcrypt algorithm of our scheme is correct.
2 Security Analysis
2.1 Security of MPKC.
In the last twenty years, many MPKC schemes were proposed, and they are mainly based on four basic MPKC schemes including the Matsumoto Imai (MI) cryptosystem, the Hidden Field Equation (HFE) cryptosystem, the Oil Vinegar (OV) cryptosystem and the Stepwise Triangular System [20]. Although most of them have been broken, some variants of the basic MPKC schemes, such as Rainbow and PMI+ [20], have survived known attacks like the linearization equation attack, the rank attack and the differential attack. In 2011, Hashimoto et al. [21] proposed two types of fault attacks which further weaken the security of the MPKC schemes. They detailed the fault attack on the MPKC schemes such as UOV, Rainbow, TTS and HFE, and most of the MPKC schemes were proven insecure. However, the PMI+ cryptosystem is one of the few approved cryptosystems which survived the linearization equation attack, the rank attack, the differential attack and even the fault attacks. PMI+ uses the Plus (+) method of external perturbation to prevent attacks without significantly decreasing the efficiency of the system [20]. So in our work, we used PMI+ which is based on the IP problem to construct our scheme.
Cryptosystems based on the IP problem belong to a major category of MPKC. Faugère et al. [22] gave an upper bound on the theoretical complexity of the “IP-like” problem, and presented a new algorithm to solve the IP problem when S and T are linear mappings. Bouillaguet et al. [23] proposed an improved algorithm combining the linear algebra techniques, together with Gröbner bases and statistical tools. To date, the best algorithm for the IP problem is exponential. For the IP problem used in our scheme, the attacking complexity of the best algorithm will be Ο(n3.5⋅qn/2) [24], where n is the number of variables and q is the cardinality of the finite field. So the IP problem will be computationally hard if we can choose the parameter properly.
With the knowledge of the most efficient attacks on the IP problem, in order to strengthen the security of our scheme, we suggest that the parameters of our scheme should satisfy the following conditions: the transformations T and V should be affine; the polynomials in P and Q should be homogeneous. In our method, for example, if we choose n = 16 and q = 29, the attacking complexity should be greater than Ο(n3.5⋅qn/2) = 163.5•(29)16/2 = 286. Usually, it is considered to be a computationally secure MPKC scheme if the attacking complexity is greater than 280 [24]. Therefore, our scheme is a secure MPKC-based scheme.
Although we used PMI+ for the construction of the proposed multi-receiver signcryption scheme, there are still some other multivariate cryptosystems suitable for the construction of our scheme, such as the internally perturbed HFE cryptosystem (IPHFE) [25]. Different from PMI+, IPHFE is build by using the idea of internal perturbation. Vivien et al. [26], [27] and Ding et al. [28], [29] analyzed the security of IPHFE, and their work showed that IPHFE with appropriate parameters can withstand all known attacks. So IPHFE can be substituted for PMI+ in our construction. Due to space limitations, we do not introduce the detailed realization of the construction based on IPHFE.
2.2 Message Confidentiality. Theorem 2.
Confidentiality under the attack of Type 1. In the random oracle model, if an IND-CLMSC-CCA2-1 adversary A has a non-negligible advantage ε against the security of our scheme when performing queries to random oracles Hi (i = 1, 2), qske Extract Secret Key queries, qpke Extract Public Key queries, qpkr Replace Public Key queries, qsc Signcrypt queries and qdsc Designcrypt queries, then there exists an algorithm C that can solve the MQ problem with advantage defined as:
(2)where t is the number of receivers in the challenge set and G2 denotes the bit length of the element over Gn.
Proof.
We show how to build an algorithm C that solves the MQ problem with the help of an adversary A. Let C receive a random instance {f(x), Y0 = f(X0)} of the MQ problem, and the goal of C is to compute X0. To solve this problem, C acts as A’s challenger in the IND-CLMSC-CCA2-1 game.
Setup.
C sets as the system public key, chooses an invertible affine transformation T0 on
, and chooses an invertible affine transformation V0 on
randomly. So the system partial secret key is
, and the partial public key is
. C sends the system parameters
, the system public key and the system partial secret key to A. Then A outputs a set of target identities, denoted by
. To handle A’s queries, C maintains a list Li for each Hi (i = 1, 2) query.
H1 queries.
A can perform an H1 query on the input of (m, IDi, X, L) and then C checks the list L1. If an entry corresponding to (m, IDi, X, L) is present in L1, then C retrieves the hash value hi from L1 and returns hi. Otherwise, it returns a random number and stores the entry (hi, m, IDi, X, L, ∇, Δ) in L1, where the symbols ∇ and Δ denote the signature information and the encryption information of the message m, respectively.
H2 queries.
A can perform an H2 query on the input of (IDs, S, X) for IDi and then C checks the list L2. If an entry corresponding to IDi is present in L2, then C retrieves Zi from L2 and returns Zi. Otherwise, it returns a random number Zi and stores the entry (Zi, IDs, S, X, IDi, Λ, □, ◊, bi = 0) in L2, where the symbols Λ, □ and ◊ denote the public key Fi, the secret parameters Ti and Vi, respectively. The bit bi is a flag bit used to denote whether the public keys have been replaced or not.
Extract Secret Key queries.
A can perform an Extract Secret Key query on the input of IDi. C first checks whether holds. If
holds, then C aborts the query. Otherwise, C retrieves the entry (Zi, IDs, S, X, IDi, Fi, Ti, Vi, bi = 0) from L2. If bi = 0, then C returns the secret key
; otherwise, the public key of the identity IDi has been replaced and in this case, C asks A for the new secret parameters (Ti, Vi), computes the new secret key
and returns it to A.
Extract Public Key queries.
A can perform an Extract Public Key query on the input of IDi and then C checks L2. If an entry corresponding to IDi is present in L2, then C retrieves Fi from L2 and returns Fi. Otherwise, C chooses , returns the public key
and updates the entry corresponding to IDi in L2 with Ti, Vi and Fi.
Replace Public Key queries.
When A performs a Replace Public Key query on the input of , C searches the corresponding entry
in L2. If the entry is found, then C replaces the public key in the entry corresponding to IDi in L2 with
and sets the flag bit bi to 1. Otherwise, C generates the public key using the Extract Public Key query and then replaces the public key of IDi with
.
Signcrypt queries.
A can perform a Signcrypt query on the input of (m, IDs, L = {IDR1, IDR2, …, IDRt}). If IDs = IDRi, , or if
and at least one
, then C aborts the query. Otherwise, C knows the secret key of the sender and performs the computations as the signcryption algorithm to return the ciphertext
. If
, C does not know the secret key of the sender and in this case, it generates the ciphertext as follows:
First, C retrieves the entry (⋅, IDs, Fs, Ts, Vs, bs) from L2 and chooses and
. C computes
, extracts Y = hs by calling the oracle H1 with the input
and computes the signature S. Then, C retrieves the corresponding entry
in L2 and then computes Wi = Fi(S||X) and Z = Zs⊕m. C updates the corresponding entry in L1. Note that if bi = 1, then the public key of the receiver has been replaced and in this case, the challenger asks A for (Ti, Vi) and uses it in place of the old value stored in the entry. Finally, add
in L2 (C fails if H2 is already defined on any of such entries, but this happens only with probability
). At last, C sends
to A.
Designcrypt queries.
When A submits a ciphertext , a receiver’s identity IDR and a sender’s identity IDs, C extracts (S, Y, Z, Wi, L) from σ. If
, then C knows the secret key of IDR and hence designcrypts σ using the De-signcrypt Algorithm. Otherwise, C searches all entries (Y, ⋅, IDs, ⋅, L, ⋅, Z) in L1, and if no such entries exist, the symbol ⊥ is returned to indicate that the ciphertext is invalid. Meanwhile, C searches the entry (Zi, IDs, S, X, IDs, Fs, Ts, Vs, bs) in L2, and if it is not found, C rejects the ciphertext σ. If the ciphertext σ passes the above verification, C computes
,
, and
. If
and
hold, and
passes the verification, then C returns m; otherwise, C rejects σ. Note that a valid ciphertext is rejected with probability at most
Challenge.
A outputs two messages m0 and m1 together with an arbitrary sender’s identity on which A wishes to be challenged. C selects a bit
and sends mb to the t target identities denoted by
. C chooses
and
, sets
and then computes
,
and
. Then, C responds with the ciphertext
Phase2.
A performs new queries as in Phase 1. However, A is not allowed to ask Designcrypt queries on σ* for
Guess.
At the end of the game, A returns his/her guess result. C ignores the answer to A’s guess. According to the above discussion, we know that as long as the simulation of the attacker’s environment is perfect, the probability that A asks the value of Wi = Fi(X*||S*), i = 1, 2, …, t, by the H1 oracle is the same as the probability in a real attack. C fetches a random entry (hi, m, IDi, X, L, S, Wi) from L1. With probability (as L1 contains no more than t⋅qsc+
elements by our construction), the chosen entry contains the right element
. C returns X0 as a solution to the MQ problem.
Now, we analyze the probability of C’s success. Let E be the event that A outputs the correct bit b* = b.
Simulation fails if any of the following events occurs:
E1: Extract Secret Key query is executed for some chosen challenge identity.
E2: Both the sender and at least one of receivers belong to the challenge set in some Signcrypt query.
E3: The H2 oracle collides in Signcrypt queries.
E4: C rejects a valid ciphertext in some Designcrypt query.
According to the above discussion, we know that Pr[E] = ε, where E implies that E1 and E2 never occur, that is, . Also, we have
since A conducts a total of qsc Signcrypt queries and there are at most t⋅qsc+
entries in L2.
represents the probability of rejection of valid ciphertexts.
The event E5 implies that C chooses the correct entry from L1 in the Guess Phase. And we know that So, the advantage
of C is defined as:
(3)
Theorem 3.
Confidentiality under the attack of Type 2. In the random oracle model, if an IND-CLMSC-CCA2-2 adversary A has a non-negligible advantage ε against the security of our scheme when performing queries to random oracles Hi (i = 1, 2), qske Extract Secret Key queries, qpke Extract Public Key queries, qsc Signcrypt queries and qdsc Designcrypt queries, then there exists an algorithm C that can solve the MQ problem with an advantage
defined as:
(5)where t is the number of receivers in the challenge set and G2 denotes the bit length of the element over Gn.
The attacker has access to the master key, but cannot perform public key replacement under the attack of Type 2. The proof is similar to that of Theorem 2.
2.3 Unforgeability. Theorem 4.
Unforgeability under the attack of Type 1. In the random oracle model, if an SUF-CLMSC-CMA-1 adversary A has a non-negligible advantage ε against the security of our scheme when performing queries to random oracles Hi (i = 1, 2), qske Extract Secret Key queries, qpke Extract Public Key queries, qpkr Replace Public Key queries, qsc Signcrypt queries and qver Verify queries, then there exists an algorithm C that can solve the IP problem with an advantage
defined as:
(6)where t is the number of receivers in the challenge set and G2 denotes the bit length of the element over Gn.
Proof.
We show how to build an algorithm C that solves the IP problem with the help of an adversary A. Let C receive a random instance of the IP problem, and the goal of C is to compute (Ts, Vs). To solve this problem, C acts as A’s challenger in the SUF-CLMSC-CMA-1 game.
Setup.
C sets as the system public key, and chooses an invertible affine transformation T0 on
and an invertible affine transformation V0 on
randomly. So the system partial secret key is
, and the partial public key is
. C sends the system parameters
, the system public key and the system partial secret key to A. Then A outputs a set of target identities, denoted by
. To handle A’s queries, C maintains a list Li for each Hi (i = 1, 2) query.
H1 queries.
A can perform an H1 query on the input of (m, IDi, X, L) and then C checks the list L1. If an entry corresponding to (m, IDi, X, L) is present in L1, then C retrieves hi from L1 and returns hi. Otherwise, it returns a random number and stores the entry (hi, m, IDi, X, L, ∇, Δ) in L1, where the symbols ∇ and Δ denote the signature information and the encryption information for message m, respectively.
H2 queries.
A can perform an H2 query on the input of (IDs, S, X) for IDi and then C checks the L2. If an entry corresponding to IDi is present in L2, then C retrieves Zi from L2 and returns Zi. Otherwise, it returns a random number Zi and stores the entry (Zi, IDs, S, X, IDi, Λ, □, ◊, bi = 0) in L2, where the symbols Λ, □ and ◊ denote the public key Fi, the secret parameters Ti and Vi, respectively. The bit bi is a flag bit used to denote whether the public keys have been replaced or not.
Extract Secret Key queries.
A can perform an Extract Secret Key query on the input of IDi, and C first checks whether holds. If
holds, then C aborts the query. Otherwise, C retrieves the entry (Zi, IDs, S, X, IDi, Fi, Ti, Vi, bi = 0) from L2. If bi = 0, then C returns the secret key
. Otherwise, the public key of the identity IDi has been replaced and in this case, C asks A for the new secret parameters (Ti, Vi), computes the new secret key
and returns it to A.
Extract Public Key queries.
A can perform an Extract Public Key query on the input of IDi and then C checks L2. If an entry corresponding to IDi is present in L2, then C retrieves Fi from L2 and returns Fi. Otherwise C chooses Ti∈R Gn+p and Vi∈R Gn, returns the public key and updates the entry corresponding to IDi in L2 with Ti, Vi and Fi.
Replace Public Key queries.
When A performs a Replace Public Key query on the input of , C searches the corresponding entry
in L2. If the entry is found, then C replaces the public keys in the entry corresponding to IDi in L2 with
and sets the flag bit bi to 1. Otherwise, C generates the public key using Extract Public Key query and then replaces the public key of IDi with
.
Signcrypt queries.
A can performs a Signcrypt query on the input of (m, IDs, L = {IDR1, IDR2, …, IDRt}). If IDs = IDRi,, or if
and at least one
, then C aborts the query. If
, then C knows the secret key of the sender and performs the computations as the Signcrypt algorithm to return the ciphertext
. If
, C does not know the secret key of the sender and hence it generates the ciphertext as follows:
First, C retrieves the entry (⋅, IDs, Fs, Ts, Vs, bs) from L2 and chooses and
. C computes
, extracts Y = hs by calling the oracle H1 with the input (m, IDs, X, L) and computes the signature S. Then, C retrieves the corresponding entry
in L2 and then computes Wi = Fi(S||X) and Z = Zs⊕m. C updates the corresponding entry in L1. Note that if bi = 1, then the public key of the receiver has been replaced and in this case, the challenger asks A for (Ti, Vi) and uses it in place of the old value stored in the entry. Finally, add
in L2 (C fails if H2 is already defined on any of such entries, but this happens only with probability
). At last, C sends
to A.
Verify queries.
When A submits a ciphertext , a receiver’s identity IDR and a sender’s identity IDs, C extracts (S, Y, Z, Wi, L) from σ. If
, then C knows the secret key of IDR and hence designcrypts σ using the De-signcrypt Algorithm. Otherwise, C searches all entries (Y, ⋅, IDs, ⋅, L, ⋅, Z) in L1, and if no such entries exist, the symbol ⊥ is returned to indicate that the ciphertext is invalid. Meanwhile, C searches the entry (Zi, IDs, S, X, IDs, Fs, Ts, Vs, bs) in L2, and if it is not found, C rejects the ciphertext σ. If the ciphertext σ passes the above verification, C computes
,
and
. If
and
hold, and
passes the verification test, then C accepts σ; otherwise, C rejects σ. Note that a valid ciphertext is rejected with probability at most
Forge.
After a polynomial-bounded number of queries, the adversary A outputs forged ciphertext (a receiver list L = {IDR1, IDR2, …, IDRt}, and at least one
) and the sender’s identity
According to the above discussion, we know that as long as the simulation of the attacker’s environment is perfect, the probability that A asks the value of (Ts, Vs) by the H2 oracle is the same as the probability in a real attack. C fetches a random entry (Zi, IDs, S, X, IDi, Fi, Ti, Vi, bi) from L2. With probability (as L2 contains no more than t⋅qsc+
elements by our construction, and C chooses IDs with probability 1/t), the chosen entry contains the right element (Ts, Vs). C returns (Ts, Vs) as the solution to the IP problem.
Now, we analyze the probability of C’s success. Let E be the event that the forged ciphertext passes verifications.
Simulation fails if any of the following events occurs:
E1: Extract Secret Key query is executed for some chosen challenge identity.
E2: Both sender and at least one of receivers belong to the challenge set in some Signcrypt query.
E3: The H2 oracle collides in Signcrypt queries.
E4: C rejects a valid ciphertext in Verify queries.
According to the above discussion, we know that Pr[E] = ε, where E implies that E1 and E2 never occur, that is, . Also, we have
, since A conducts a total of qsc Signcrypt queries and there are at most t⋅qsc+
entries in L2.
represents the probability of rejection of valid ciphertexts.
The event E5 implies that C chooses the correct entry from L2 in the last Verify Phase. And we know that . So, the advantage
of C is defined as:
(7)
Theorem 5.
Unforgeability under the attack of Type 2. In the random oracle model, if an SUF-CLMSC-CMA-2 adversary A has a non-negligible advantage ε against the security of our scheme when performing queries to random oracles Hi (i = 1, 2), qske Extract Secret Key queries, qpke Extract Public Key queries, qsc Signcrypt queries and qver Verify queries, then there exists an algorithm C that can solve the IP problem with an advantage
defined as:
(9)where t is the number of receivers in the challenge set and G2 denotes the bit length of the element over Gn.
The attacker has access to the master key, but cannot perform public key replacement under the attack of Type 2. The proof is similar to that of Theorem 4.
2.4 Backward Secrecy.
Each time Alice sends a message m to receivers, she chooses randomly as the session key. Even though she sends the same message m, the corresponding ciphertext σ will be different in different sessions. So the new receiver who joins the group later does not have the previous value
which is computed for the message m, and thus he/she can not obtain the previous message m. Therefore, our scheme is backward secure.
2.5 Forward Secrecy.
Forward secrecy means that the members who have quitted the group are not able to know the later session keys. In our scheme, the session key r is randomly chosen in each session. When some member of the group quits the group, the sender will compute the partial key for the rest members again, which guarantees that the members who have quitted the group cannot obtain the plaintext message from the later ciphertext. So our scheme is forward secure.
2.6 Non-repudiation.
According to Theorem 4 and Theorem 5, our scheme is unforgeable. Suppose that Alice signcrypts a message m. If others want to repudiate her signature S, they have to solve the MQ problem to get the secret key of Alice, and it is computationally infeasible because the MQ problem is an NP-hard problem. Therefore, only Alice knows her secret key and others can not repudiate her behavior of signcrypting the message m. So our scheme is non-repudiation.
2.7 Public Verifiability.
The proposed scheme provides public verifiability of ciphertext source, which is an important requirement in broadcast communications. Any third party can be convinced of the sender of the ciphertext σ by recovering in the second step of the de-signcryption phase and checking whether the equation
holds. This is in fact due to the unforgeability of the signature. This verification procedure does not involve the knowledge of messages or the receiver’s secret key but only the ciphertext σ. Hence, our scheme supports public verifiability.
3 Performance Comparison
In this section, we shall compare our scheme with the existing schemes [8]–[10], [12] in performance. We mainly consider the computation and communication cost.
The proposed scheme does not involve any bilinear pairing operations, exponentiation operations and multiplications in groups. In the signcryption phase, it needs only two hash operations, (t+2) MQ-mapping (it means the mapping operation on the multivariate quadratic equations) operations and one XOR operation, while in the de-signcryption phase, it needs two hash operations, two MQ-mapping operations and one XOR operation. The MQ-mapping operations are linear operations and have much lower computation complexity than bilinear pairing operations and exponentiation operations. According to the above analysis, the computation complexity of our scheme is O(t+4). The ciphertext of our scheme is (t+1)G1+(t+1)G2+|m| bits in length, where t is the number of receivers, G2 is the bit length of the element over Gn, and G1 is the bit length of the element over Gn+p. Compared with the representative CLMSC scheme [12], the new scheme has lower computation complexity without bilinear pairing operation needed. We also compare our scheme with the naive extension of schemes [8]–[10] for multi-receiver setting in Table 1, in which par denotes pairing operation, exp denotes exponentiation operation and ciphertext-size denotes the bit length of the ciphertext. The comparisons are summarized in Table 1.
According to the above analyses, the proposed scheme is more efficient than the existing ones, and it is also provably secure in the random oracle model. The proposed scheme is a very useful tool in multicast communication. With the rapid development of wireless networks, it is particularly important to transfer instruction data from the control center to multiple intelligent terminals securely [30]. The control center needs to encrypt the sensitive information to prevent it from being eavesdropped and cracked before sending it to intelligent terminals, while intelligent terminals need to judge whether the received instruction is from the trusted entity. To solve this security problem, we must take both the security requirements and the performance of the intelligent terminals into account, because intelligent terminals are generally characterized by low power consumption, low computing power and narrow communication bandwidth, which make the traditional identity-based scheme not suitable for them. Through the analyses about the security and performance of our scheme, it can be concluded that our scheme can better address these issues and it is in line with the characteristics of intelligent terminals.
Conclusions
As one of the alternative cryptosystems, multivariate public key cryptography can resist quantum attack, and has been researched by scholars extensively. In this paper, we employ multivariate public key cryptography to propose a new construction of the certificateless multi-receiver signcryption scheme, called a quantum attack-resistent certificateless multi-receiver signcryption scheme. The new scheme inherits the security of multi-variable cryptosystems that could resist quantum attack, and it avoids the certificate management and the key escrow problem. We proved its security under the hardness of the MQ problem and its unforgeability under the IP assumption in the random oracle model. In addition, the scheme also has security properties such as forward secrecy, backward secrecy, non-repudiation and public verifiability. Analyses show that the proposed scheme is more efficient than the existing ones. Although our scheme is constructed by using PMI+, there are still some other multivariate cryptosystems like IPHFE suitable for our construction. In the future work, we will construct the multi-receiver signcryption scheme by using IPHFE or other better multivariate cryptosystem, and compare the performance of the new scheme with that of the scheme proposed in this paper.
Author Contributions
Analyzed the data: HL XC LP WS. Wrote the paper: HL XC LP WS. Conceived and designed the scheme: HL XC. Proved the security of the scheme: HL XC.
References
- 1.
Zheng Y (1997) Digital signcryption or how to achieve cost (signature & encryption)<<cost (signature)+cost (encryption). In: Proc. 17th Annual International Cryptology Conference on Advances in Cryptology. 165–179.
- 2.
Luo M, Wen Y, Zhao H (2008) A certificate-based signcryption scheme. In: Proc. International Conference on Computer Science and Information Technology. 17–23.
- 3. Pang LJ, Gao L, Pei QQ, Cui JJ, Wang YM (2013) A new ID-based multi-recipient public-key encryption scheme. Chinese Journal of Electronics 1: 89–92.
- 4. AI-Riyami SS, Paterson KG (2003) Certificateless public key cryptography. In: Proc. 9th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2003): 452–473.
- 5.
Barbosa M, Farshim P (2008) Certificateless signcryption. In: Proc. ACM Symposium on Information, Computer and Communications Security. 369–372.
- 6.
Barreto PSLM, Deusajute AM, Cruz ES, Pereira GCF, Silva RR (2008) Toward efficient certificateless signcryption from (and without) bilinear pairings. http://sbseg2008.inf.ufrgs.br/proceedings/data/pdf/st03_03_artigo.pdf.
- 7.
Li F, Shirase M, Takagi T (2009) Certificateless hybrid signcryption. In: Proc. 5th International Conference on Information Security Practice and Experience. 112–123.
- 8. Li PC, He MX, Li X, Liu WG (2010) Efficient and provably secure certificateless signcryption from bilinear pairings. Journal of Computational Information Systems 6: 3643–3650.
- 9. Selvi SSD, Vivek S, Rangan CP (2009) Cryptanalysis of certificateless signcryption schemes and an efficient construction without pairing. In: Proc. 5th international conference on Information security and cryptology (Inscrypt’ 09): 75–92.
- 10.
Jing XF (2011) Provably secure certificateless signcryption scheme without pairing. In: Proc. International Conference on Electronic and Mechanical Engineering and Information Technology. 4753–4756.
- 11.
Selvi SSD, Vivek SS, Shukla D, Chandrasekaran PR (2008) Efficient and provably secure certificateless multi-receiver signcryption. In: Proc. 2nd International Conference on Provable Security. 52–67.
- 12.
Selvi SSD, Vivek SS, Rangan CP (2009) A note on the certificateless muli-receiver signcryption scheme. IACR Cryptology ePrint Archive. 308–308.
- 13.
Miao SQ, Zhang FT, Zhang L (2010) Cryptanalysis of a certificateless multi-receiver signcryption scheme. In: Proc. International Conference on Multimedia Information Networking and Security. 593–597.
- 14.
Shor PW (1994) Algorithms for quantum computation: discrete logarithms and factoring. In: Proc. 35th Symposium on Foundations of Computer Science. 124–134.
- 15. Dubois V, Fouque FA, Shamir A, Stern J (2007) Cryptanalysis of the SFLASH signature scheme. In: Proc. 3rd International SKLOIS Conference on Information Security and Cryptology (Inscrypt 2007): 1–4.
- 16. Billet O, Robshaw MJB, Peyrin T (2007) On building hash functions from multivariate quadratic equations. In: Proc. 12th Australasian conference on Information security and privacy (ACISP' 07): 82–95.
- 17.
Patarin J, Goubin L (1997) Trapdoor one-way permutations and multivariate polynomials. In: Proc. first International Conference on Information and Communications Security. 356–368.
- 18.
Patarin J (1996) Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric. In: Proc. International Conference on the Theory and Application of Cryptographic Techniques. 33–48.
- 19.
Bouillaguet C, Faugère JC, Fouque PA, Perret L (2011) Practical cryptanalysis of the identification scheme based on the isomorphism of polynomial with one secret problem. In: Proc.14th International Conference on Practice and Theory in Public Key Cryptography. 473–493.
- 20.
Ding JT, Gower JE (2006) Inoculation multivariate schemes against differential attacks. In: Proc. 9th International Conference on Theory and Practice in Public-Key Cryptography. 290–301.
- 21.
Hashimoto Y, Takagi T, Sakurai K (2012) General fault attacks on multivariate public key cryptosystems. In: Proc. 4th International Workshop on Post-Quantum Cryptography. 1–18.
- 22.
Faugère JC, Perret L (2006) Polynomial equivalence problems: algorithmic and theoretical aspects. In: Proc. 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 30–47.
- 23.
Bouillaguet C, Faugère P, Perret L (2009) Differential algorithms for the isomorphism of polynomials problem. http://eprint.iacr.org/2009/583.pdf.
- 24.
Tang SH, Xu LL (2012) Proxy signature scheme based on isomorphisms of polynomials. In: Proc. 6th International Conference on Network and System Security. 113–125.
- 25. Ding JT, Schmidt D (2005) Cryptanalysis of HFEv and internal perturbation of HFE. In: Proc. 10th International Conference on Practice and Theory in Public-Key Cryptography (PKC 2005): 288–301.
- 26. Dubois V, Granboulan L, Stern J (2007) Cryptanalysis of HFE with Internal Perturbation. In: Proc. 10th International Conference on Practice and Theory in Public-Key Cryptography (PKC 2007): 249–265.
- 27. Dubois V, Gama N (2010) The degree of regularity of HFE Systems. In: Proc. 16th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2010): 557–576.
- 28. Ding JT, Hodges TJ (2011) Inverting HFE systems is quasi-polynomial for all fields. In: Proc. 31th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO 2011): 724–742.
- 29.
Ding JT, Kleinjung T (2012) Degree of Regularity of HFE minus. Journal of Math-for-Industry. 2012, Vol 4, 97–104.
- 30. Pang LJ, Li HX, Pei QQ (2012) Improved multicast key management of Chinese wireless local area network security standard. IET Communications 6: 1126–1130.