1 Introduction

At the inspiration of Zheng's public key signcryption idea^[1] and with the purpose to meet the need of network multicast, a large number of multi-receiver signcryption schemes are proposed. Typically, Baek et al.^[2] designed multi-receiver signcryption scheme based on identity. Elkamchouchi and Abouelseoud^[3] constructed a publicly verifiable multi-receiver signcryption scheme based on identity, which meets the need of the firewall or gateway to verify the identity of the sender. Lal and Kushwah^[4] designed multi-receiver signcryption scheme based on identity in which the sender is anonymous.Recently, a number of new signcryption schemes have also been put forward^[5-6].

The schemes described above are designed mainly at the basis of the bilinear, and the length of the ciphertext and the number of the receivers are linear, so the ciphertext is expanding quickly with the number of receivers increasing. Meanwhile, the bilinear problem has been solved by polynomial time quantum algorithm^[7]. Thus, in the post quantum era, we have to design a multi-receiver signcryption scheme based on new assumption.

Maybe extending bilinear to multilinear is one of the solutions. In 2003, Boneh and Silverberg^[8] proposed the idea of designing efficient cryptographic primitives by using multilinear mapping structures. However, not until 2013 Garg, Gentry and Halevi (GGH)^[9] proposed the candidate multilinear mapping structure based on the ideal lattice. Based on GGH's program, many public key encryption schemes are designed, such as in Refs. [10-11]. Following the idea of GGH, several multilinear mapping schemes are proposed. Langlois et al.^[12] proposed a GGH variant scheme. Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi (CLT)^[13] designed a multilinear mapping structure based on integer instead of ideal lattice. Although the CLT scheme is cracked by Cheon et al.^[14] by zero attack, CLT proposed a modified multilinear mapping structure based on integer which can avoid zero attack^[15]. Recently, Hu et al.^[16] can attack GGH effectively with zero attack. While Gu^[17] proposed new multilinear mapping structure without zero encodings, thus completely eradicating the zero attack.

At present, the known multilinear mapping encoding systems all adopt the GGH's idea of "graded". And they have similar algorithms like sample level-0 encoding, level-i encoding, extraction and 0 encoding decision. According to these features, we propose a generic graded multilinear mapping encoding system, disregarding the data structure and concrete realization of an encoding system. As with the definition of GDDH, we define the generic graded decision Diffie-Hellman problem (GGDDH).

In the application of public key encryption, once the user secret key is leaked, the past cipher can be easily decrypted by intruder. Some people proposed some solutions such as in Ref. [18]. In 1997, Anderson^[19] firstly introduced the idea of forward-security in the key exchange protocol to public key cryptosystem, in order to solve the leakage problem of private key. Inspired by his idea, a series of forward-secure public key cryptosystems are proposed. Li et al.^[20] designed forward secrecy signcryption scheme based on elliptic curve cryptosystem. The landmark is that in 2003, Canetti et al.^[21] firstly constructed a forward-secure public key encryption scheme, based on a hierarchical encryption scheme^[22]. Subsequently, Canetti et al.^[23] also gave a general method of constructing the forward-secure public key encryption scheme using binary tree. This method has been widely applied to the design of forward-secure encryption scheme based on identity^[24-25] and forward-secure encryption scheme based on the certificate^[26]. David and Olivier^[27] proposed a forward-secure non interactive key exchange protocol that also used the binary tree^[23] to design.

Based on the generic graded multilinear mapping encoding system, we design a forward-secure multi-receiver signcryption scheme. Our scheme also uses binary tree to manage the evolution of the user's private key. The entire life cycle of the user private key is divided into N time period, and each time period is only corresponding to a node of binary tree. Beginning from the first time period, the user's private key evolves each time after a time period finishes, and user destroys the private key of the current time period. But the public key is kept unchanged. The sender uses the current time period and the private key to signcrypt message and only the recipient with the private key in the same time period can decrypt and verify successfully.

This ensures that in current time period if the private key of the recipient is exposed, the ciphertext created in the past time period is still safe. This also ensures when the current time period private key of the sender is exposed, the attacker still cannot forge the signcryption of the past time period.

Our contributions: firstly, we define the generic graded multilinear mapping encoding system and assumption of the generics graded decision Diffie-Hellman problem (GGDDH). Moreover, we design a forward-secure multi-receiver signcrypiton scheme based on the generic graded multilinear mapping encoding system, and prove it security under the assumption of GGDDH problem.

Secondly, for the first time we elaborate the forward-secure multi-receiver signcryption security model. Basically, a multi-receiver signcryption scheme should guarantee the message confidentiality and unforgeability at any time period. At the same time, in order to guarantee the forward security, if the private key is leaked in time period j, and then the message confidentiality should be guaranteed in i < j; similarly, if the private key of the sender is leaked in j, the scheme can guarantee that attacker cannot forge signcryption in i < j.

Thirdly, there are two group elements in the ciphertext of our scheme much less than the number of group elements in Refs.[3-4]. Because in Refs.[3-4], the length of the ciphertext and the number of the receivers are linear, the size of ciphertext is expanding quickly with the number of receivers increasing. Meanwhile, the existing multi-receiver schemes are designed mainly based on bilinear and the bilinear problem has polynomial time quantum solution. However, there is no polynomial time quantum solution of GGDDH problem on which our scheme is proposed based.

2 Preliminaries 2.1 Generic Graded Multilinear Mapping Encoding System

Definition   1   Generic Graded Multilinear Mapping Encoding System. For the cyclic group G₁, G_T with the same order p, a level-κ multilinear mapping e:G₁×…×G₁→G_T is satisfied e(α₁g, α₂g, …, α_κg)=$\prod\limits_{i = 1}^\kappa {} $α_i·e(g, g, …, g), in which g∈G₁ is the generator of G₁, G_T. Furthermore, the encoding system includes the following algorithms:

1) The system initial algorithm InstGen(1^λ, 1^κ) takes as input security parameter λ and maximum encoding level κ. It returns public parameters params.

2) The level-0 encoding sampling algorithm samp() takes as input public parameters params. It returns a random level-0 encoding d.

3) The level-i encoding algorithm enc(i, d) takes as input public parameters params, i≤κ and level-j encoding d, such that j≤i. It returns level-i encoding of d. The process of encoding includes the default randomization process, that is, the noise is added to the encoding.

4) The add algorithm add (u₁, u₂) takes as input level-i encoding u₁, u₂. It returns the sum of u₁ and u₂, that is level-i≤κ encoding u=u₁+u₂.

5) The multiply algorithm mult(u₁, u₂) takes as input level-i encoding u₁ and level-j encoding u₂, such that i+j≤κ.It returns level-(i+j) encoding u=u₁·u₂.

6) The zero test algorithm is Zero(u) takes as input encoding u. It returns 1 if u is zero encoding, otherwise it returns 0.

7) The extraction algorithm ext(u) takes as input level-κ encoding u. It returns according characteristic bit string b∈{0, 1}^λ.

For convenience's sake, and under circumstances of no confusion, we will directly use the mathematical symbols '+' and '·' instead of add(u₁, u₂) and mult(u₁, u₂).

Similar to the definition of GDDH problem, we give the definition of generic graded decision Diffie-Hellman problem (GGDDH).

Definition   2    GGDDH problem. Considering the process described below, and the attacker is given the parameters params.

1)  e_j←samp(), j=0, 1, …, κ; //randomly sample κ+1 level-0 encodings

2)  Let u_j←enc(1, e_j), j=0, 1, …, κ;

3)  f←samp(); //randomly sample a level-0 encoding

4)  Let $\boldsymbol{v} = {\boldsymbol{e}_0}\prod\limits_{i = 1}^\kappa {{\boldsymbol{u_i}}, \boldsymbol{v'} = \boldsymbol{f}\prod\limits_{i = 1}^\kappa {{\boldsymbol{u_i}}.} } $

The generic graded decision Diffie-Hellman problem (GGDDH) is how to distinguish v and v^′ for an attacker. In other words, how to distinguish the distribution D_GGDDH={params, u₀, …, u_k, v} and distribution D_RAND={params, u₀, …, u_k, v^′} for an attacker.

2.2 Definition of Forward-Secure Multi-Receiver Signcryption Scheme

This section defines the notion of forward-secure multi-receiver signcryption scheme (fs-MSC). A formal definition follows:

Definition  3   A (public key) forward-secure multi-receiver signcryption scheme(fs-MSC) is a tuple of PPT (probabilistic polynomial time) algorithms (KeyGen, Upd, fs-Signcrypt, fs-DeSigncrypt) such that:

1) The key generation algorithm KeyGen takes as input a security parameter λ and the total number of time periods N. It returns a public key pk_sand an initial secret key sk_s for sender ID_s and pair of public key and private key for every receiver in {ID₁, ..., ID_τ} in addition to some public parameters denoted as PP.

2) The key update algorithm Upd takes as input PP, current time period i∈[0, N-1), and the associated secret key sk_i. It returns the secret key sk_i+1 for the next time period i+1.

3) The encryption algorithm fs-Signcrypt takes as input the name of a node s∈S_n which represents the current time period, the receiver set ID₁, …, ID_τ, sender ID_s's private key sk_s and message M. It returns a signcryption C.

4) The decryption algorithm fs-DeSigncrypt takes as input a receiver ID_i's private key sk_i, a ciphertext C, the current time period i. It returns correct plaintext M∈{0, 1}^$\ell$ if the identity of sender is verified correctly, else it returns ⊥.

3 Our Forward-Secure Multi-Receiver Signcryption (fs-MSC) Scheme

In this section we presents an fs-MSC scheme based on the generic graded multilinear mapping. As described in the introduction, our scheme uses binary tree to manage the evolution of the user's private key. The entire life cycle of the user private key is divided into N time period, and each time period only corresponds to one node of binary tree. The order of time period is the same as the pre-order traversal of the binary tree.

As shown in Fig. 1, each node of the binary tree corresponds to a random selection of level-0 encoding h_s, where s is the path from the root node to this node (not including the root node). Time period i is often represented by s of the tree node. The level-1 encoding of the level-0 encoding x of the root node is the public key. The level-1 encoding of the other nodes H_s=enc(1, h_s) are public parameters and h_s will be destroyed. From the property of the binary tree, after getting rid of the root node, if level of binary tree is n, and then the set of all path is s_n, such that |s_n|=2ⁿ⁺¹-2, so, the total time period is N=2ⁿ⁺¹-2.

If a path of binary tree node is s=b₁b₂…b_$\ell$∈s_n, the private key of the time period corresponding to this node is level-l encoding ${z_s} = x \cdot \prod\limits_{i = 1}^\ell {{\boldsymbol{H}_{{b_1} \cdots {b_i}}} = enc\left( {\ell, x \cdot \prod\limits_{i = 1}^\ell {{\boldsymbol{h}_{b1 \cdots {b_i}}}} } \right)} $. To guarantee forward-security, the private key in last time period is destroyed after a key evolution. Obviously, x will be destroyed when the private key in the first time period z₀=enc(1, x·H₀) is created. Therefore, the right sub-tree corresponding to private keys cannot be created, if the left sub-tree traversal is over, for example: z₁=enc(1, x·H₁) cannot be created because x has been destroyed.

Supposed the path length of a binary-tree node is $\ell$, path s=b₁b₂…b_$\ell$∈s_n. Let integer set Ψ_s={i:1≤i≤$\ell$, b_i=0} represents the subscript of all 0 bit in s. In order to guarantee the key evolution, subsequent private key information ∪_i∈Ψs{z_b1…bi-11} must be saved in advance, so the private key for the path s=b₁b₂…b_$\ell$ is sk_s=∪_i∈Ψs{z_b1…bi-11}∪z_s.

Supposed that total time period is N=2ⁿ⁺¹-2, where n is the level of binary tree(get rid of root node), and the maximum multilinear encoding level κ=n+2. Our fs-MSC scheme has the following algorithms.

1) KeyGen(1^κ, 1^λ): first of all, generate multilinear mapping parameters params. Then randomly sample n-1 level-0 encodings (g₂, g₃, …, g_n)←samp(), and make their level-1 encoding (G₂, G₃, …, G_n) public. Sample level-0 encoding h_s←samp() for bit string s∈S_n corresponding to every binary tree node. Make H_s=enc(1, h_s) public and destroy h_s. Lastly, output PP={params, (G₂, G₃, …, G_n), {H_s}}.

Pick a random level-0 encoding x_s for sender ID_s and compute private key sk_s=0=(z₀, z₁)=(enc(1, x·H₀), enc(1, x·H₁)), public key pk_s=enc(1, x_s). Choosing two random level-0 encodings x_{i, 1}, x_{i, 2} for each receiver ID_i∈{ID₁, …, ID_τ}. Let x_i=x_{i, 1}·x_{i, 2}, to compute receiver's private key sk_{s, i}=(z_{0, i}, z_{1, i})=(enc(1, x_i·H₀), enc(1, x_i·H₁)). To compute receiver's public key (pk_{i, 1}, pk_{i, 2})=(enc(1, x_{i, 1}), enc(1, x_{i, 2})).

2) Upd(sk_s): Supposed that s=b₁b₂…b_$\ell$, for any sender or receiver, the evolution of his private key is as follows.

(1) If the length of path $\ell$ < n, the path in next time period should be s||0, to compute level-($\ell$+1) encoding z_s||0=z_s·H_s||0 and z_s||1=z_s·H_s||1, and return new private key sk_s||0=(sk_s\{z_s})∪{z_s||0, z_s||1} and destroy z_s.

(2) If $\ell$=n, s=b₁b₂…b_n is the path of a leaf node. If s=1ⁿ, the current time period is the last one, to return ⊥. Otherwise, supposed that j is the maximum integer in Ψ_s, and binary tree path of next time period is s^*=b₁b₂…b_j-11, so, to compute and return private key sk_s^*=sk_s\(∪_{i∈Ψs, i>j}{z_b1…bi-11}, z_s)=∪_i∈Ψs^*{z_b1…bi-11}∪z_s^*.

3) fs_Signcrypt(PP, M, s, ∪_1≤i≤τ(ID_i), sk_s):Taking as input the sender ID_s's private key sk_s, receiver set ∪_1≤i≤τ(ID_i) with public key ∪_1≤i≤τ(pk_{i, 1}, pk_{i, 2}). ID_s chooses level-0 encoding r←samp() at random, and computes c₁←enc(1, r).Then to compute c_{2, i}←ext(r·z_s·$\prod\limits_{j = \ell + 1}^n {{\boldsymbol{G_j}}} $·pk_{i, 1}·pk_{i, 2})ⓧM, i=1, …, τ and c₂=∪_1≤i≤τc_{2, i}. Next, to compute c₃←enc($\ell$, M·hash($\sum\limits_{i = 1}^\tau {{c_{2, i}}} $)·z_s). Finally, output c=(c₁, c₂, c₃).

4) fs_DeSigncrypt(PP, c, s, sk_{s, i}): Taking as input the cipher and private key of number i receiver sk_{s, i}. The decryption algorithm outputs M←ext(c₁·z_{s, i}·pk_s·$\prod\limits_{j = \ell + 1}^n {{\boldsymbol{\mathit{G}}_j}} $)ⓧc_{2, i}, and then calls is Zero(enc (κ, c₃·pk_{i, 1}·pk_{i, 2})-enc(κ, M·hash ($\sum\limits_{i = 1}^\tau {{c_{2, i}}} $)·z_{s, i}·pk_s)) to verify the sender's identity. If the function returns 1, receiver accepts plaintext, otherwise, outputs ⊥.

Correctness: r·z_s·$\prod\limits_{j = \ell + 1}^n {{\boldsymbol{\mathit{G}}_j}} $·pk_{i, 1}·pk_{i, 2} in c_{2, i} and c₁·z_{s, i}·pk_s·$\prod\limits_{j = \ell + 1}^n {{\boldsymbol{\mathit{G}}_j}} $ all belong to the level-κ encoding of r·x_s·x_i·${\prod\limits_{j = 1}^\ell {{h_{b1 \cdots {b_i}}}} }$·$\prod\limits_{j = \ell + 1}^n {{\boldsymbol{\mathit{G}}_j}} $, so, each receiver can get correct plaintext through extraction algorithm. Meanwhile, enc(κ, c₃·pk_{i, 1}·pk_{i, 2}) and enc(κ, M·hash($\sum\limits_{i = 1}^\tau {{c_{2, i}}} $)·z_{s, i}·pk_s) all belong to the level-κ encoding of M·x_s·x_i·${\prod\limits_{i = 1}^\ell {{h_{b1 \cdots {b_i}}}} }$·hash($\sum\limits_{i = 1}^\tau {{c_{2, i}}} $), so, if algorithm returns 1, and the identity of sender is verified correctly, receiver accepts plaintext M, otherwise, receiver rejects plaintext.

Performance Comparison and efficiency Analysis: There is simply Ο(n) multiply on polynomial ring in the encryption algorithm, the same as the decryption algorithm. Since our scheme does not need paring computation and exponentiation, so our scheme has lower computational complexity compared to the existing multi-receiver encryption scheme as shown in Table 1.

There are Ο(n) group elements in the ciphertext of Refs. [3-4], and only Ο(1) group elements in our scheme. Thus, the length of ciphertext of our scheme is significantly reduced.

Finally, with regard to the safety of contrast, the last column of Table 1 (Quantum Algorithm) means whether there is a polynomial time quantum algorithm to solve the hardness assumption like BDH and GGDDH. It is seen from the foregoing, BDH problem has polynomial time quantum algorithm, so the schemes [3, 4, 24] will be unsafe in the post quantum era. In addition, the scheme [3-4] does not meet the demand of forward secure. If the user secret key is leaked, the past cipher can be easily decrypted.

In Table 1, 丨G₁丨is the bit length of one element in group G₁; 丨ID丨is the bit length of one receiver identity ID and丨m丨means the bit length of plaintext m. Meanwhile, n is the number of receiver and N is the total number of time period.

4 Security of Our Construction 4.1 Security Model

A secure fs-MSC scheme should keep the secrecy of signcryption in a time period s even if the private key of other nodes (as long as they are not the ancestors of s) has been exposed. As mentioned in Ref. [23], we define the attack scenario a selective-node (SN) attack, in which the adversary is required to provide the target node in advance(i.e., before seeing the public key). First of all, we give the definition of message confidentiality and unforgeability.

Definition 4   A fs-MSC scheme is confidentiality secure against selective-node, and chosen-plaintext attacks (secure in the sense of SN-CPA) if for all PPT adversaries Α, the advantage of A in the following game is negligible in the security parameter λ.

Init: Α outputs a name s^*∈S_n of a node which represents a specified time period. Simulator calls KeyGen(1^κ, 1^λ) outputs public parameters PP. Without loss of generality, we specify the sender ID_s^* with the public key pk_s^*and the set of receiver's identity R^*={ID₁^*, …, ID_τ^*} with public key {(pk_{i, 1}, pk_{i, 2})}. Simulator calls Keygen(1^κ, 1^λ) to get sender's private key SK_s^* and private key of each receiver.

Queries: Α can make two types of query to simulator Β.

-Create new key: Α is given pk_s^*, {(pk_{i, 1}, pk_{i, 2})}and {sk_s} that is the set of private key of sender and receivers for any node in S_n as long as s is not a prefix of s^*.

-Signcrypt: On input a message M∈{0, 1}^ℯ. Then simulator calculates c←fs_Signcrypt(PP, M, s^*, R^*, sk_s^*) and returns c to A.

Challenge: Α generates a request challenge (s^*, M₀, M₁). Simulator Β selects a random bit β∈{0, 1} and computes c←fs_Signcrypt(PP, M_β, s^*, R^*, sk_s^*). Finally, the adversary is given c.

Guess: The adversary outputs a guess β^′∈{0, 1}. It succeeds if β^′=β. The adversary's advantage is the absolute value of the difference between its success probability and 1/2.

Definition 5   A fs-MSC scheme is unforgeability secure against selective-node, and chosen-plaintext attacks (secure in the sense of SN-CPA) if for all PPT forger F, the advantage of F in the following game is negligible in the security parameter λ.

The init and queries are defined as in Definition 4.

Forge: Finally, F outputs new legal signcryption for a message M that can be decrypted by any receiver in R^*={ID₁^*, …, ID_τ^*} and the sender ID_s^* can be verified. The advantage of F is the probability of his success.

On the basis of message confidentiality and unforgeability, our scheme also ensures the forward-security. The definition of message forward-confidentiality and forward-unforgeability is as follows.

Definition 6   A fs-MSC scheme is forward-confidentiality against chosen-plaintext attacks (secure in the sense of fs-CPA) if for all PPT adversaries whose advantage in the following game is negligible in the security parameter λ.

Setup: Simulator calls KeyGen(1^κ, 1^λ) outputs public parameters PP. Without loss of generality, we specify the sender ID_s^* with the public key pk_s^* and private key sk_s^* and receiver ID_i in R^*={ID₁^*, …, ID_τ^*} has public key {(pk_{i, 1}, pk_{i, 2})}.

Queries: The adversary is allowed one breakin (i) query and one challenge (j, M₀, M₁), in either order, such that 0≤j < i < N. On breakin (i) query, the sender's private key sk_i in i time period is given to the adversary.

Challenge: The adversary generates a request challenge(j, M₀, M₁). Simulator Β selects a random bit β∈0, 1 and computes c←fs_Signcrypt(PP, M_β, j, R^*, sk_s^*). Finally, the adversary is given c.

Guess: The adversary outputs a guess β^′∈0, 1. It succeeds if β^′=β. The adversary's advantage is the absolute value of the difference between its success probability and 1/2.

Definition 7   A fs-MSC scheme is forward-unforgeability against selective-node, and chosen-plaintext attacks (secure in the sense of SN-CPA) if for all PPT forger F, the advantage of F in the following game is negligible in the security parameter λ.

The setup and queries are defined as in Definition 6.

Forge: Finally, F outputs new legal signcryption for a message M in j time period that can be decrypted by any receiver in R^*={ID₁^*, …, ID_τ^*} and the sender ID_s^* can be verified. The advantage of F is the probability of his success.

4.2 Proof of Confidentiality for fs-MSC Scheme

We show that if there exists a PPT attacker Α that can win the game defined in Definition 4 with non-negligible advantage ε for our fs-MSC scheme, and then there exists a PPT simulator Β that can break the GGDDH problem with the same advantage.

Theorem 1   For our fs-MSC scheme, if there is any probability polynomial time (PPT) attacker A that can win the game defined in Definition 4 with non-negligible advantage ε, and then there is an algorithm Β for solving generic graded DDH(GGDDH) problem with the same advantage.

Proof:The simulator takes as input the GGDDH instance (params, u₀, …, u_κ, v) and acts as the role of challenger.The parameter params is public.

Init:   Α outputs a specified time period named s^*∈S_n. Supposed that the time period |s^*|=ℯ and s^*=b₁b₂…b_ℯ, let H_b1b2…bi=u_i, i=1, 2, …, ℯ. Let G_i=u_i, i=ℯ+1, …, n. Choosing h_s←samp() at random and compute H_s=enc(1, h_s) such that s∈S_n and s is not a prefix of s^*. Simulator samples level-0 encoding x_s for sender ID_s^*, to compute his private key sk_s=0=(z₀, z₁)in the first time period and public key pk_s^*=enc(1, x_s). Simulator chooses level-0 encoding x_i for each receiver in R^*={ID₁^*, …, ID_τ^*}\{ID₁^*}, and computes the public key/private key pair ((pk_{i, 1}, pk_{i, 2}), (sk_{s, i})). Without loss of generality, let public key of receiver ID₁^* be (pk_{i, 1}, pk_{i, 2})=(u_n+1, u_n+2). At last, forger Α is given pk_s^*, {(pk_{i, 1}, pk_{i, 2})}.

At last, invader is given public parameters and the public key of sender and every receiver.

Queries:Α can make two types of query to the simulator Β.

-Create new key: Α can query {sk_s}that is the set of private key of any reciever for any node in S_n as long as s is not a prefix of s^*.

-Signcrypt: On input a message M∈{0, 1}^ℯ. Then simulator calculates c←fs_Signcrypt(PP, M, s^*, R^*, sk_s^*) and returns c to Α.

Challenge:Α inputs a pair of message(M₀, M₁). Β chooses β∈0, 1 randomly. The simulator lets c₁←u₀ and computes c_{2, 1}←ext(x_s·v)ⓧM_β, c_{2, i}←ext(c₁·z_s·$\prod\limits_{j = \ell + 1}^n {{\boldsymbol{\mathit{G}}_j}} $·pk_{i, 1}·x_i)ⓧM_β, i=2, …, τ, c₂=∪_i(c_{2, i}) and c₃←enc($\ell$, M_β·hash($\sum\limits_{i = 1}^m {{c_{2, i}}} $)·z_s). At last, Α is given ciphertext c=(c₁, c₂, c₃).

Guess: Α outputs his guess β^′∈0, 1 for β. If β^′=β, Β judges v=e₀$\prod\limits_{i = 1}^\kappa {{\boldsymbol{\mathit{u_i}}}} $. Otherwise, Β judges v=$f\prod\limits_{i = 1}^\kappa {{u_i}} $.

The parameters that Β releases are independently distributed random variables, and consistent with the real scheme. Obviously, if v=${\boldsymbol{e}_0}\prod\limits_{i = 1}^\kappa {{\boldsymbol{u_i}}} $, then x_s·v is legal level-κ encoding of x_s·${e_0}\prod\limits_{i = 1}^\kappa {{u_i}} $ and the ciphertext given by simulator is just the same as the ciphertext that is computed by some people who know the value of e₀. In this case, according to our assumption, Α will judge β with non-negligible advantage ε. On the contrary, if $v = f\prod\limits_{i = 1}^\kappa {{u_i}\;} $, challenge ciphertext is illegal and Α will judge β with negligible advantage. So, according to the results which Α guesses, Β can judge the distribution of v or v^′ with non-negligible advantage ε. Hence Β has a non-negligible advantage ε in breaking the GGDDH assumption. This completes the proof of Theorem 1.

4.3 Proof of Unforgeability for fs-MSC Scheme

We show that if there exists a PPT forger F that can win the game defined in Definition 5 with non-negligible advantage ε for our fs-MSC scheme, and then there exists a PPT simulator Β that can break the GGDDH problem with the same advantage ε.

Theorem 2   For our fs-MSC scheme, if there exists any probability polynomial time(PPT) forger F that can win the game defined in Definition 5 with non-negligible advantage ε, then there exists an algorithm Β for solving generic graded DDH(GGDDH) problem with the same advantage.

Proof:The simulator takes as input the GGDDH instance (params, u₀, …, u_k, v) and acts as the role of challenger.

Init:F outputs a name s^*∈S_n of a node which represents a specified time period. Supposed the time period s^*=b₁b₂…b _$\ell$, let H_b1b2…bi=u_i, i=1, 2, …, $\ell$. Choose h_s←samp() at random and compute H_s=enc(1, h_s) such that s∈S_n and s is not a prefix of s^*. Let G_i=u_i, i=$\ell$+1, …, n. Simulator generates other parameters in the usual way. Simulator samples level-0 encoding x_s for sender ID_s^*, to compute his private key sk_s=0=(z₀, z₁)in the first time period and public key pk_s^*=enc(1, x_s). Simulator chooses level-0 encoding x_i for each receiver in R^*={ID₁^*, …, ID_τ^*}\{ID₁^*}, and computes the public key/private key pair ((pk_{i, 1}, pk_{i, 2}), (sk_{s, i})). Without loss of generality, let public key of receiver ID₁^* be (pk_{i, 1}, pk_{i, 2})=(u_n+1, u_n+2).At last, forger F is given pk_s^*, {(pk_{i, 1}, pk_{i, 2})}.

Query phases:F can make two kinds of query to Β.

-Create new key: F can query {sk_s}that is the set of private key for any node in S_n as long as s is not a prefix of s^*.

-Signcrypt: On input a message M∈{0, 1} ^$\ell$. Then simulator chooses level-0 encoding r←samp() at random, c₁←enc(1, r·u₀). Then, simulator computes c_{2, 1}←ext(r·v)ⓧM, c_{2, i}←ext(c₁·z_{s, i}·$\prod\limits_{j = \ell + 1}^n {{\boldsymbol{\mathit{G}}_j}} $·pk_s^*)ⓧM, i=2, …, τ, c₂=∪_i(c_{2, i}) and c₃←enc($\ell$, M·hash($\sum\limits_{i = 1}^\tau {{c_{2, i}}} $)·z_s). At last, F is given ciphertext c=(c₁, c₂, c₃).

Response:At last, F outputs a signcryption c^*=(c₁, c₂, c₃). If signcryption is legal, Β judges v=${\boldsymbol{\mathit{e}}_0}\prod\limits_{i = 1}^\kappa {{u_i}}$, otherwise Β judges $\boldsymbol{\mathit{v}} = \boldsymbol{\mathit{f}}\prod\limits_{i = 1}^\kappa {{\boldsymbol{\mathit{u_i}}}\;} $.

Obviously, if v=${\boldsymbol{\mathit{e}}_0}\prod\limits_{i = 1}^\kappa {{u_i}}$, then r·v is legal level-κ encoding of r·${\boldsymbol{\mathit{e}}_0}\prod\limits_{i = 1}^\kappa {{u_i}}$ and the ciphertext given by simulator is just the same as the ciphertext that is computed by some people who know the value of e₀. In this case, according to our assumption, F can forge ciphertext with non-negligible advantage ε. On the contrary, if $\boldsymbol{\mathit{v}} = \boldsymbol{\mathit{f}}\prod\limits_{i = 1}^\kappa {{\boldsymbol{\mathit{u_i}}}\;} $, challenge ciphertext is illegal and F can forge ciphertext with negligible advantage. So, according to the results which F forges, Β can judge the distribution of v or v^′ with non-negligible advantage ε. Hence Β has a non-negligible advantage ε in breaking the GGDDH assumption. This completes the proof of Theorem 2.

4.4 Proof of Forward-Confidentiality for fs-MSC Scheme

We show that if there exists a PPT attacker Α that can win the game defined in Definition 6 with non-negligible advantage ε for our fs-MSC scheme, and then there exists a PPT simulator Β that can break the GGDDH problem with non-negligible advantage.

Theorem 3   For our fs-MSC scheme, if there is any probability polynomial time (PPT) attacker A that can win the game defined in Definition 6 with non-negligible advantage ε, and then there is an algorithm Β for solving generic graded DDH(GGDDH) problem with non-negligible advantage.

Proof:The simulator takes as input the GGDDH instance (params, u₀, …, u_κ, v) and acts as the role of challenger.The parameter params is public.

Init:Simulator calls KeyGen(1^κ, 1^λ) outputs public parameters PP. Α outputs challenge (j, M₀, M₁). The name s^*∈S_n of a node correspond to the time period j. Supposed the time period s^*=b₁b₂…b_$\ell$, let H_b1b2…bi=u_i, i=1, 2, …, $\ell$. Choose h_s←samp() at random and compute H_s=enc(1, h_s) such that s∈S_n and s is not a prefix of s^*. Let G_i=u_i, i=$\ell$+1, …, n. Simulator samples level-0 encoding x_s for sender ID_s, ^* to compute his private key sk_s=0=(z₀, z₁) in the first time period and public key pk_s^*=enc(1, x_s). Simulator chooses level-0 encoding x_i for each receiver in R^*={ID₁^*, …, ID_τ^*}\{ID₁^*}, and computes the public key/private key pair ((pk_{i, 1}, pk_{i, 2}), (sk_{s, i})). Without loss of generality, let public key of receiver ID₁^* be (pk_{i, 1}, pk_{i, 2})=(u_n+1, u_n+2).At last, forger F is given pk_s^*, {(pk_{i, 1}, pk_{i, 2})}.

Queries:The adversary is allowed one breakin (i) query, such that 0≤j < i < N. On query breakin(i), each receiver's private key in i time period that is computed via repeated calling of Upd in the normal way is given to the adversary.

Challenge:Simulator Β chooses β∈0, 1 randomly. The simulator let c₁←u₀. Then, computes c_{2, 1}←ext(x_s·v)ⓧM_β, c_{2, i}←ext(c₁·z_s·$\prod\limits_{j = \ell + 1}^n {{\boldsymbol{\mathit{G}_j}}} $·pk_{i, 1}·x_i)ⓧM_β, i=2, …, τ, c₂=∪_i(c_{2, i}) and c₃←enc($\ell$, M_β·hash($\sum\limits_{i = 1}^m {{c_{2, i}}} $)·z_s). At last, Α is given ciphertext c=(c₁, c₂, c₃).

Guess:Α outputs his guess β^′∈0, 1 for β. If β^′=β, Β judges v=${\boldsymbol{\mathit{e}}_0}\prod\limits_{i = 1}^\kappa {{\boldsymbol{\mathit{u_i}}}} $. Otherwise, Β judges $\boldsymbol{\mathit{v}} = \boldsymbol{\mathit{f}}\prod\limits_{i = 1}^\kappa {{\boldsymbol{\mathit{u_i}}}\;} $.

If the attacker obtains the private key in the time period i, the private key of the future time period can be calculated, so we allow the attacker to query once.

In the process of challenge, if v=${\boldsymbol{\mathit{e}}_0}\prod\limits_{i = 1}^\kappa {{\boldsymbol{\mathit{u_i}}}} $, then x_s·v is legal level-κ encoding of x_s·${\boldsymbol{\mathit{e}}_0}\prod\limits_{i = 1}^\kappa {{\boldsymbol{\mathit{u_i}}}} $ and the ciphertext given by simulator is just the same as the ciphertext that is computed by some people who know the value of e₀. In this case, according to our assumption, Α will judge β with non-negligible advantage ε. On the contrary, if $\boldsymbol{\mathit{v}} = \boldsymbol{\mathit{f}}\prod\limits_{i = 1}^\kappa {{\boldsymbol{\mathit{u_i}}}\;}$, challenge ciphertext is illegal and Α will judge β with negligible advantage. So, according to the results Α guesses, Β can judge the distribution of v or v^′ with non-negligible advantage. As mentioned in Ref. [17], if attacker queries challenge (j, M₀, M₁) firstly, Β has a non-negligible advantage ε in breaking the GGDDH assumption. If attacker queries breakin (i) firstly, Β has a non-negligible advantage ε/N in breaking the GGDDH assumption. This completes the proof of Theorem 3.

4.5 Proof of Forward-Unforgeability for fs-MSC Scheme

We show that if there exists a PPT attacker F that can win the game defined in Definition 7 with non-negligible advantage ε for our fs-MSC scheme, and then there exists a PPT simulator Β that can break the GGDDH problem with non-negligible advantage.

Theorem 4   For our fs-MSC scheme, if there is any probability polynomial time (PPT) attacker A that can win the game defined in Definition 7 with non-negligible advantage ε, there is an algorithm Β for solving generic graded DDH(GGDDH) problem with non-negligible advantage.

Proof:We show that if there exists a PPT attacker F that can win the game defined in Definition 5 with non-negligible advantage ε for our fs-MSC scheme, there exists a PPT simulator Β that can break the GGDDH problem with non-negligible advantage. The simulator takes as input the GGDDH instance (params, u₀, …, u_κ, v) and acts as the role of challenger.The parameter params is public.

Init:   The simulator calls KeyGen(1^κ, 1^λ) and outputs public parameters PP. F outputs a name s^*∈S_n of a node which represents a specified time period j. Supposed the time period s^*=b₁b₂…b_ℯ, let H_b1b2…bi=u_i, i=1, 2, …, ℯ. Choose h_s←samp() at random and compute H_s=enc(1, h_s) such that s∈S_n and s is not a prefix of s^*.Let G_i=u_i, i=ℯ+1, …, n. Simulator lets sender ID_s^*'s public key pk_s^*=u₀. Simulator chooses level-0 encoding x_i for each receiver in R^*={ID₁^*, …, ID_τ^*}\{ID₁^*}, and computes the public key/private key pair ((pk_{i, 1}, pk_{i, 2}), (sk_{s, i})). Without loss of generality, let public key of receiver ID₁^* be (pk_{i, 1}, pk_{i, 2})=(u_n+1, u_n+2).At last, forger F is given pk_s^*, {(pk_{i, 1}, pk_{i, 2})}.

Queries:The adversary is allowed one breakin (i) query, such that 0≤j < i < N. On query breakin (i), sender's private key in i time period can be calculated and given to the adversary because the simulator keep {h_s}, such that s∈S_n and s is not a prefix of s^*.

Response:  At last, if F outputs a legal signcryption c^*=(c₁, c₂, c₃) of message M from ID_s^* to R^*. Because c₃←enc(ℯ, M·hash($\sum\limits_{i = 1}^m {{c_{2, i}}} $)·z_s) and z_s=enc(ℯ, $\prod\limits_{i = 0}^\ell {{\boldsymbol{\mathit{e_i}}}\;}$), so, if isZero(c₃·$\prod\limits_{i = \ell + 1}^\kappa {{\boldsymbol{\mathit{u_i}}}\;} $-v·M·hash($\sum\limits_{i = 1}^m {{c_{2, i}}} $)) returns 1, and then Β judges v=${\boldsymbol{\mathit{e}}_0}\prod\limits_{i = 1}^\kappa {{\boldsymbol{\mathit{u_i}}}} $. Otherwise, Β judges $\boldsymbol{\mathit{v}} = \boldsymbol{\mathit{f}}\prod\limits_{i = 1}^\kappa {{\boldsymbol{\mathit{u_i}}}\;} $. Obviously, Β has the same advantage ε in breaking the GGDDH assumption. This completes the proof of Theorem 4.

5 Conclusions

In this paper, a generic multilinear mapping encoding system is defined, based on which a forward-secure multi-receiver signcryption scheme is designed. The security scheme of a forward-secure multi-receiver signcryption scheme is proposed, which can effectively repair the loss in a public key system because the leakage of current private key.