Improved broadcast encryption schemes with enhanced security

Abstract

A broadcast encryption scheme is one of important primitives to achieve message confidentiality in distributed network, which supports one-to-many encryption under insecure channels. In this paper, we show that any balanced incomplete block design constructed by perpendicular array can be used to realize secure BE schemes. Its broadcast rate, broadcast information rate and the upper bound of the number of collusion resistant are also obtained. According to the characteristics of the block, a more efficient broadcast encryption, using the strong part balanced incomplete block design constructed by rational normal curve is presented. This scheme is secure under an enhanced security model compared with the first construction. Particularly, even any two users are absent in the block, it can achieve fully collusion resistant. Moreover, an improved scheme is given based on the efficiency comparison of these two schemes, in which the broadcast rate is invariant while its broadcast information rate is significantly higher than that of the first construction. Finally, we propose a block reservation scheme, which provides the function of appending users dynamically.

1 Introduction

Broadcast encryption (BE) is an important primitive for broadcasting messages to a group of users with only one-time encryption. It can dynamically select user groups in order to send messages. In this way, only the privileged users are able to obtain their information while the unauthorized users cannot decrypt and extract the message even they collude. The concept of BE was firstly introduced by Fiat and Naor (1994). After that, many BE schemes and some related properties (Boneh and Franklin 1999; Dodis and Fazio 2002; Boneh et al. 2005; Naor et al. 2001; Halevy and Shamir 2002; Stinson and Van Trung 1998; Shamir 1979; Libert et al. 2012; Li et al. 2010, 2013; Zhao and Zhang 2011; Fazio and Perera 2012) were proposed to achieve different functions such as the better efficiency or enhanced security et al. These works are divided into two categories, that is, the symmetric BE and asymmetric BE.

In asymmetric BE, each user is issued a public and private key pair. There is no broadcast center and any user is able to encrypt a message to a set of users. However, in symmetric BE, each user only has private keys, which is issued from a central authority. The symmetric broadcast encryption always achieves better efficiency compared with the asymmetric BE (Boneh and Franklin 1999; Dodis and Fazio 2002; Boneh et al. 2005). Thus, most applications utilize the symmetric BE to save the computational cost.

In a symmetric BE, there are three phases including set-up phase, transmission phase, decryption phase. It allows users to pre-distribute secret information (Stinson 1997; Quinn 1994) by the center during the set-up phase of this system. After each user in the group gets a private key, they can communicate with each through efficient BE. In the transmission phase, to encrypt a message, a session key is generated and the message is encrypted using the session key. After that, the user also encrypts the session key with public parameters and public keys of the set of privileged users. In the decryption phase, a privileged user uses his/her secret information to obtain one of the keys with which the session key has been encrypted. There are two important parameters of a BE scheme from the perspective of efficiency. They are broadcast rate and broadcast information rate. Moreover, the tolerance of maximum number of colluding users is also an important security parameter of a BE scheme. Thus, how to construct a efficient BE scheme with better broadcast rate and broadcast information rate is a challenge.

1.1 Related work

As mentioned before, broadcast encryption allows a sender to select an arbitrary set of receivers S, in the encryption algorithm (Fiat and Naor 1994). Naor et al. (2001) proposed the first fully collusion-resistant BE scheme called NNL-BE, which uses a tree structure. The NNL-BE scheme (Naor et al. 2001) is defined for $n$ users where $n$ is a power of two, i.e, $n\,=\,2^{l_{0}}$ for some $l_{0}\,>\,0$. During the construction of the tree, each user is considered to be a leaf of a full binary tree with $l_{0}$ levels. A subsequent work by Halevy and Shamir (2002) introduced a variant of the SD method, which is called the layered subset difference (LSD) scheme. However, this work is also defined for $n$ users where $n\,=\,2^{l_{0}}$. Different from the above one, the basic idea is to partition the tree into several layers.

Another important tool for the construction of BE was introduced by Stinson and Van Trung (1998), which is called balanced incomplete block design (BIBD) method. Unlike the previous works, this scheme allows arbitrary number of users, without the restriction of the number of users. In BIBD, any subset of users is considered to be the blocks while users are considered to be the points of the block. Two important parameters, namely broadcast rate and broadcast information rate in BE scheme, are defined (Stinson and Van Trung 1998).

There are two kinds of security definitions for BE, that is, the BE with adaptive security and static security. Most of the previous can only achieve static security (Yao et al. 2008). To dynamically allow users to join or leave the system, it additionally has to rely some trusted authority in these works. In more details, the adaptive security allows the adversary to see some corrupted users’ private keys and public keys adaptively. For static security, the adversary can only determine the set of the corrupted users before the setup of the system. Thus, for practical applications, it prefers the adaptive security. There are also some results on how to transform a BE with static security to adaptive security. Therefore, it is only necessary to construct a static BE in theory as it can be transformed into adaptive secure BE. However, such direct transformation has some restriction as the huge computational overhead.

1.2 Our contributions

In this paper, according to the BIBD technique introduced in Stinson and Van Trung (1998), we prove that the BE scheme can be constructed from any BIBD. Then we prove that perpendicular array can construct BIBD where broadcast rate and broadcast information rate are $t\left( n\lambda _{t}\left( {\begin{array}{c}s-\tau \\ t-\tau \end{array}}\right) \right) ^{-1}$ and $\left( \lambda _{t}\left( {\begin{array}{c}s\\ t\end{array}}\right) \right) ^{-1}$, respectively. Furthermore, the tolerance of the maximum number of colluding users is $\lfloor \frac{1}{2}+\frac{1}{2}\sqrt{1+8\frac{s-1}{n(n-1)}}\rfloor$.

Considering the demand for reducing the number of blocks, we point out that scheme based on strong partly balanced incomplete block design (SPBIBD) achieves better performance. Particularly, when colluding users do not belong to the same group, they can not learn any secret information. Increasing broadcast information rate is another contribution of our work. The construction using block design has a low rate of broadcast information because of its huge number of blocks. Thus in this paper, we use dual design to improve the basic construction and optimize broadcast information rate.

Ensuring the forward secrecy is another contribution in this paper. We point out that a method of “reserve block” ensures that the keys of members remain the same. However, the public key for blocks can be automatically updated when a new member joins.

2 Preliminaries

In this section, we briefly introduce some definitions of blocks design technique.

2.1 Broadcast structure

In this section, we briefly introduce some definitions for broadcast encryption.

Definition 2.1

Let $\mathcal {V}$ and $\mathcal {B}$ be two disjoint sets, and $\mathcal {I}$be a binary relation between $\mathcal {V}$ and $\mathcal {B}$, namely $\mathcal {I}\subseteq \mathcal {V}\times \mathcal {B}$. Then we say that $\mathcal {D}=(\mathcal {V},\mathcal {B},\mathcal {I})$ is an incidence structure.

The elements of $\mathcal {V}$ and $\mathcal {B}$ are defined for point and block, and $\mathcal {I}$ is called incidence relation.

Let $p\in \mathcal {V},B\in \mathcal {B}$, if $(p,B)\in \mathcal {I}$, namely $p$ and $B$ are of incidence relation. It is described as $p\mathcal {I}B.$

Let $\mathcal {D}=(\mathcal {V},\mathcal {B},\mathcal {I})$ be a limited incidence structure, in which $\mathcal {V}$ and $\mathcal {B}$ are limited sets. If $p\in \mathcal {V},B\in \mathcal {B}$, let $r_{p}$ be the multiplicity of $p$ while $k_{B}$ be the capacity of $B$. If $S$ be any t-subset of $\mathcal {V}$ , then $\lambda _{s}$ is the number of blocks which is of incidence relation with every point of $S.$

We also give the following definitions used in this construction.

• 1. Regularity: There are constants $r$ such that for all $p\in \mathcal {V}$, we have $r_{p}=r$;

• 2. Uniformity There are constants $k$ such that for all $B\in \mathcal {B}, k_{B}=k$;

• 3. t-equilibration: For a given positive integer $t$, there are a constant $\lambda$ such that for any t-subset $S, \lambda _{s}=\lambda$.

Particularly, 1-equilibration is regularity, while 2-equilibration is equilibration. The limited incidence structure which satisfies the conditions of regularity, uniformity and equilibration is called balanced incomplete block design.

2.2 Balanced incomplete block design

In this section, we show some notions and definitions of balanced incomplete block design.

Definition 2.2

(Colbourn and Charles 1996) A balanced incomplete block design (BIBD) is a pair $(\mathcal {V},\mathcal {B})$ where $\mathcal {V}$ is a $\nu -$set and $\mathcal {B}$ is a collection of b $k-$set of $\mathcal {V}$ (blocks) such that each element of $\mathcal {V}$ is contained in exactly $r$ block and any 2-subset of $\mathcal {V}$ is contained in exactly $\lambda$ blocks. The number $\nu ,b,r,k,\lambda$ are parameters of the BIBD.

Lemma 2.3

(Colbourn and Charles 1996) Trivial condition for the existence of a BIBD $(\nu ,b,r,k,\lambda )$ are (1) $\nu r=bk$, and (2) $r(k-1)=\lambda (\nu -1)$. Parameter sets that satisfy (1) and (2) are admissible.

Defination 2.4

(Colbourn and Charles 1996) Let $\mathcal {V}$ be a $v-$ set, $\mathcal {B}=\{B_{1},\ldots ,B_{b}\}$ in which $B_{j}\subseteq \mathcal {B}(j=1,2\ldots ,b)$ is a $k$-subset, then $B_{j}$ is called a block. $(\mathcal {V},\mathcal {B})$ is called a $t$-partly balanced design, namely $t-(\nu ,k,\lambda ,0)-$ design. For any $t-$ subset of $\mathcal {V}$, it is either absent in any blocks of $B$ or it is contained in exactly $\lambda$ blocks of $B$ (where $\nu ,k,t,\lambda$ are integers).

Definition 2.5

(Colbourn and Charles 1996) The design of $(\mathcal {V},\mathcal {B})$ mentioned above is a strong partially balanced incomplete block design (SPBIBD) for a given positive integer $r$, where $r\le t$. $(\mathcal {V},\mathcal {B})$ is a $r$-partly balanced incomplete block design.

In this paper, the broadcast encryption scheme is constructed by 2-strong partly balanced incomplete block design.

2.3 Perpendicular array

Definition 2.6

(Colbourn and Charles 1996) A perpendicular array $PA_{\lambda }(s,n,\nu )$ is a $\lambda \left( {\begin{array}{c}\nu \\ s\end{array}}\right) \times n$, $A=(a_{j,i})$, with entries from a $\nu -$set, say Y, such that the following properties are satisfied:

• each row of A contains n different elements of Y.

• for any $s-$set of Y, and for any s columns of A, there are exactly $\lambda$ rows of A in which the s given elements occur in the s given columns (in predefined order).

2.4 Rational normal curve

Definition 2.7

[Pei (2006)] We define a curve $\mathcal {C}$ in $PG(n,\mathcal {F}_{q})$ to be the image of the map

$$\begin{aligned}&\quad \quad PG(1,\mathcal {F}_{q})\rightarrow PG(n,\mathcal {F}_{q}), \\&(x_{0},x_{1})\mapsto (x_{0}^{n},x_{0}^{n-1}x_{1},\ldots ,x_{1}^{n}). \end{aligned}$$

The projective line $PG(1, \mathcal {F}_{q})$ consists of the following $q+1$ points:

$$\begin{aligned} \{(1,a):a\in \mathcal {F}_{q}\}\, \bigcup \,\{(0,1)\}. \end{aligned}$$

Therefore, the curve $\mathcal {C}$ consists of the following $q+1$ points:

$$\begin{aligned} \{(1,\,a,\,a^{2}, \ldots , a^{n}):a\in \mathcal {F}_{q}\}\,\bigcup \,\{(0,\, 0, \ldots , 0,\, 1)\} \end{aligned}$$

(2)

It is easy to see that the $q+1$ points in (2) are all the solutions of the following system of homogeneous equations:

$$\begin{aligned} \left\{ \begin{array}{ll} \, X_{i}^{2}-X_{i-1}X_{i+1}{}=0, 1\le i\le n-1\\ X_{1}X_{n-1}-X_{0}X_{n}{}=0.\\ \end{array} \right. \end{aligned}$$

We call the image of the curve $\mathcal {C}$ under any projective transformation a rational normal curve.

3 A BE scheme based on BIBD

In this section, we first show how to design an efficient BE scheme based on BIBD. Then, we show its performance with respect to the broadcast rate and broadcast information rate etc.

3.1 The construction

According to Stinson’s scheme (Stinson and Van Trung 1998), let $N$ be a set of all users. Then, $\mathcal {B}=\{B_{1},\,B_{2},\, B_{b}\}$ is the set of users. Let $P$ be a set of privileged users in broadcast and the number of users is $|N|=\eta$. Generally, a typical symmetric broadcast encryption system includes the following three phases, that is, Setup, Broadcast and Decrypt.

• 1. Setup: Input a safety parameter $l$, a set of all users $N=\{u_{1},u_{2},\ldots ,u_{\eta }\}$, and all user subsets $B_{1},B_{2},\ldots ,B_{m}$. Then a BIBD is selected for users subsets. For $1\le i\le m$, $CA$ outputs sub-key $\{s_{B_{i}}$, $s_{B_{i}}$, $u_{i}^{1}$, $\ldots ,$ $s_{B_{i}}$, $u_{i}^{k-1}$, $s_{B_{i}}$, $u_{i}^{k+1}$, $\ldots$, $s_{B_{i}}$, $u_{i}^{\tau }\}$ for every user $u_{i}^{k}$ of $B_{i}$.

• 2. Broadcast: Let $q\ge r+1$ be a prime power and $CA$ randomly selects r nonzero numbers $a_{i}\in \mathcal {GF}_{q}(0\le i\le r-1)$ which are non-identical to each other. Then a $r-1$ order polynomial is constructed: $f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{r-1}x^{r-1}\cdots \cdots (1)$, where $a_{0}$ is a secret information in broadcast. $CA$ input the set of privileged users $P$, then these users are existed in some $B_{i}$. They compute blocks shared as follow:

  • For any $B_{i}(1\le i\le m)$, randomly select $x_{B_{i}}\in \mathcal {GF}_{q}$, calculate $f(x_{B_{i}})$. Let $y_{B_{i}}=(x_{B_{i}},f(x_{B_{i}}))\cdots \cdots (2)$ as a share of block $B_{i}$;

  • Let the subsets of privileged users are $P_{i}=B_{i}\bigcap P$, then the public key of privileged users in $P_{i}$ is $K_{B_{i}\bigcap P}=s_{B_{i}}+\sum _{\{u\in B_{i},u\notin B_{i}\bigcap P\}}s_{B_{i},u}\cdots \cdots (3)$;

  • Calculate the share of each block$b_{B_{i}}=y_{B_{i}}+K_{B_{i}\bigcap P}$;

  • Output cipher in broadcast $b_{p}=(b_{B_{i}})\cdots \cdots (5)(1\le i\le m)$.

• 3. Decrypt: When privileged users receive the cipher, they firstly judge which subset they are included in. If $u\in P$, let $A_{u}={B, u\in B}$, then $u$ use his sub-key to dispose as follow: For each $B\in A_{u}$, he calculates $K_{B_{i}\bigcap P}=s_{B_{i}}+\sum _{\{u\in B_{i},u\notin B_{i}\bigcap P\}}s_{B_{i},u}$, Then for B’s corresponding share $y_{B}=b_{B}-K_{B_{i}\bigcap P}$.

Because $|A_{u}|=r$, the user can obtain $r$ block shares and recover $r$ order polynomial. Consequently, he could get the secret information $a_{0}$.

3.2 Broadcast and broadcast information rate

Let the set of key be $\mathcal {K}\subset GF(q)$ and $q$ be a prime power. Generally, each key $\kappa (\kappa \subset \mathcal {K})$ is equal to any element in $GF(q)$. According to information theory, the information rate of key is $H(K_{P})=\log q$. Then we define the broadcast rate and broadcast information rate as follow:

• The broadcast rate: $\rho =min\{\frac{H(K_{p})}{H(U_{j})}|1\le j\le n, p\in P\}$;

• The broadcast information rate: $\rho _{B}=min\{\frac{H(K_{p})}{H(B_{p})}| p\in P\}$;

We also have the following notions. Specifically, $H(U_{j})$ means the information rate of user $j$ and $H(B_{p})$ means the information rate of user group.

4 BE Scheme Based on Perpendicular Array

In this section, we prove perpendicular array (PA) is able to construct BIBD and show how to implement the BE scheme.

4.1 BIBD based on Perpendicular Array

Lemma 4.1

Suppose that $t\le \frac{1}{2}(n+1)$ is a positive integer and $1\le \tau \le t-1$. Then, for any $PA_{\lambda _{t}(t,n,s)}$, there exists a $PA_{\lambda _{t}(\tau ,n,s)}$, where $\lambda _{\tau }=\frac{\lambda _{t}\left( {\begin{array}{c}s-\tau \\ t-\tau \end{array}}\right) }{\left( {\begin{array}{c}t\\ \tau \end{array}}\right) }$.

Theorem 1

Let $A$ be a perpendicular array $PA_{\lambda _{t}(t,n,s)}$. There exists a $(\nu ,\beta ,r ,\lambda )-BIBD$ with the following properties:

• 1. The number of point set is $|\mathcal {V}|=\nu =s$;

• 2. The number of block is $|\mathcal {B}|=\beta =\lambda _{t}\left( {\begin{array}{c}s\\ t\end{array}}\right)$ ;

• 3. For any $p\in \mathcal {V}$, $r_{p}=r=\lambda _{1}=\frac{\lambda _{t}\left( {\begin{array}{c}s-1\\ t-1\end{array}}\right) }{t}$;

• 4. For any $p, q\in \mathcal {V}$, $p\ne q$, $\lambda _{\{p,q\}}=\lambda =\lambda _{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right) =\frac{\lambda _{t}\left( {\begin{array}{c}s-2\\ t-2\end{array}}\right) \left( {\begin{array}{c}n\\ 2\end{array}}\right) }{\left( {\begin{array}{c}t\\ 2\end{array}}\right) }$, where $\nu ,\beta ,r ,\lambda$ are given positive integers.

Proof

Suppose A be a perpendicular array $PA_{\lambda _{t}(t,n,s)}$. Let point set $\mathcal {V}$ be S and the number of $\mathcal {V}$ be $|\mathcal {V}|=s$. Let $A=(A_{1},A_{2},\ldots ,A_{N})$, where $A_{i}$ is row $i$ of the matrix $(1\le i\le N)$. Let $B_{i}=A_{i}$, we construct a set of block $\mathcal {B}=\{B_{1},B_{2},\ldots ,B_{N}\}$, then $|\mathcal {B}|=\beta =N=\lambda _{t}\left( {\begin{array}{c}s\\ t\end{array}}\right)$.

To get the conclusions of (3) and (4), we only need to prove the following two facts:

• (1) For any point p belongs to $\mathcal {V}$, p is contained in exactly r-blocks, where $r=\frac{\lambda _{t}\left( {\begin{array}{c}s-1\\ t-1\end{array}}\right) }{t}$ .

• (2) For any 2-subset of $\mathcal {V}$, when they are not equal to each other, they are contained in exactly $\lambda$-blocks, where $\lambda =\frac{\lambda _{t}\left( {\begin{array}{c}s-2\\ t-2\end{array}}\right) \left( {\begin{array}{c}n\\ 2\end{array}}\right) }{\left( {\begin{array}{c}t\\ 2\end{array}}\right) }$.

By the lemma above and the properties of PA, every element of S occurs in any row in A at most once and appears exactly $\lambda _{1}$ times in each column in S, where $\lambda _{1}=\frac{\lambda _{t}\left( {\begin{array}{c}s-1\\ t-1\end{array}}\right) }{t}$. According to the construction of blocks and the point set $\mathcal {V}$ mentioned above, any point $p\in \mathcal {V}$ exactly belongs to $r_{p}$ blocks, where $r_{p}=r=\lambda _{1}n=\frac{n\lambda _{t}\left( {\begin{array}{c}s-1\\ t-1\end{array}}\right) }{t}$.

On the other hand, we can get any 2-subset of S appear exactly $\lambda _{2}$ times in matrix A, where $\lambda _{2}=\frac{\lambda _{t}\left( {\begin{array}{c}s-2\\ t-2\end{array}}\right) }{\left( {\begin{array}{c}t\\ 2\end{array}}\right) }$. In the matrix A, to gain two different columns has $\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ methods and any 2-subset appears $\lambda _{2}$ times in each of them. (Because any two elements are not repeated in the same line). Thus, any 2-subset of S appear exactly in $\lambda _{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ rows. Thus, the conclusion is established. $\square$

4.2 Example

According to the structure of the theorem 1, we can direct implementation BE. Using BIBD structured by PA to realize BE, we can select proper PA to divide registered users in setup phase. In the structure of $PA_{\lambda _{1}(3,7,8)}$, CA selects eight keys to every block containing 7 users. Because each registered user appears in 49 blocks, each of them will get $49\times 8$ keys in key pre-distribution phase. In the broadcast phase, CA achieve message encryption and give broadcasting according to the Sect. 3. Given the PA, CA distributes keys to the users and constructs a 48-polynomial. Suppose the set of privileged users is $P=\{1,5,8\}$, and the set of collusion attack users is $F=\{3,6\}$, then the following Table 1 shows the number of blocks that they belong to, the number of block keys that they can calculate, and the number of blocks that they share.

Table 1 The Number of Shared Block

The table shows that privileged users are able to reconstruct the 48-polynomial, which can obtain the broadcasting information plaintext $M=a_{0}$. But if $\omega (\omega =2)$ illegal users in collusion, they cannot reconstruct the original polynomial, thus fail to obtain the secret information.

Theorem 2

Suppose there is a $(\nu ,\beta ,r,\lambda )-BIBD$, then there exists a BE scheme based on it, having broadcast rate $\rho =t(n\lambda _{t}\left( {\begin{array}{c}s-\tau \\ t-\tau \end{array}}\right) )^{-1}$ and broadcast information rate $\rho _{B}=(\lambda _{t}\left( {\begin{array}{c}s\\ t\end{array}}\right) )^{-1}$. The upper bound of the number of users in collusion is $\lfloor \frac{1}{2}+\frac{1}{2}\sqrt{1+8\frac{s-1}{n(n-1)}}\rfloor$.

In a BE scheme, the number of secrets to be stored by a user is $r\times n$, where $r=\frac{\lambda _{t}\left( {\begin{array}{c}s-\tau \\ t-\tau \end{array}}\right) }{t}$. The number of block is $\beta$, where $\beta =\lambda _{t}\left( {\begin{array}{c}s\\ t\end{array}}\right)$. As defines in 3.2, $H(U_{j})=rn\log q$ and $H(B_{p})=\beta$. The broadcast rat and broadcast information rate can be gained. On the other hand, suppose $\omega =|F|$, where $F$ is the set of unauthorized users. If the number of secrets they have is less than the order of polynomial, then they can not attack the security of the scheme.

5 A BE scheme based on rational normal curve

In this section, we use SPBIBD, which is weaker than BIBD, to effectively improve the security of BE scheme. We prove that rational normal curve (RNC) can be constructed as SPBIBD. We also present its security and efficiency.

5.1 Property of rational normal curve and structure of SPBIBD

Lemma 5.1

(Pei et al. 2010) There are $q +1$ points on each RNC in $PG(N,F_{q})$. For $n\le q$, any $n+1$ points on a RNC are linearly independent.

Lemma 5.2

(Pei et al. 2010) Suppose that $q\ge n+2$ . For any $n+3$ points in $PG(N,F_{q})$, among which any $n+1$ points are linearly independent, there exists a unique RNC passing through these $n+3$ points.

Lemma 5.3

(Pei et al. 2010) Let $n\ge 2$ be an integer and $q\ge n+2$ be a prime power. Then the total number of RNCs in $PG(N,F_{q})$ is $\frac{1}{2}qn(n+1)-\prod (q^{i}-1)$.

Lemma 5.4

Let $t\ge 5$ be a positive integer, and $q\ge t-1$ be a prime power. There exists a $t-(\nu ,\kappa ,1,0)$ design, where $\nu =(q^{t-2}-1)(q-1)^{-1}$ and $k=q+1$.

It is also a $r-(\nu ,\kappa ,\lambda _{r},0)$-design $(3\le r\le t-1)$ and a $r-(\nu ,\kappa ,\lambda _{r})$ design $(1\le r\le 2)$, where $\lambda _{1}=q^{\frac{1}{2}(t-2)(t-3)-1}\prod \nolimits _{i=2}^{t-3}(q^{i}-1)$, $\lambda _{r}=q^{\frac{1}{2}(t-2-r)(r+t-3)-1}\prod \nolimits _{i=1}^{t-3-r}(q^{i}-1)\prod \nolimits _{i=1}^{r-2}(q-i)$, $(2\le r\le t-3)$, $\lambda _{t-2}=(q=1)^{t-4}\prod \nolimits _{i=1}^{t-4}(q^{i}-1)$, $\lambda _{t-1}=\prod \nolimits _{i=2}^{t-3}(q-1)$. Especially, when $r=2$, $\prod \nolimits _{i=1}^{r-2}(q-i)=1$.

Let $t\ge 5$ be a positive integer, and let $n=t-3$, $M=PG(N,F_{q})$. Then the blocks of $\mathcal {B}$ are equal to the number of RNCs in M. According to lemma5.4, $(M,\mathcal {B})$ is a t-SPBIBD. We let $r=\lambda _{1}$ and $\lambda =\lambda _{2}$, having this correspondence, we can construct SPBIBD as follow:

Theorem 3

Let $t\ge 5$ be a positive integer, $q\ge t-1$ be a prime power, there exists a $(\nu ,b,\kappa ,\gamma ,\lambda )-SPBIBD$, where $\nu ,b,\kappa ,\gamma ,\lambda$ are all positive integers and $|M|=\nu$, $|\mathcal {B}|=b$, $k=q+1$.

Theorem 4

Suppose that there is a secure SPBIBD. Then there exists a BE scheme based on it, with rate $\rho =(q+1)^{-1}q^{1-\frac{1}{2}(t-2)(t-3)}\prod \nolimits _{i=2}^{t-3}(q^{i}-1)^{-1}$ and broadcast information rate $\rho _{B}=q^{1-\frac{1}{2}(t-2)(t-3)}\prod \nolimits _{i=2}^{t-3}(q^{i}-1)^{-1}$. When any two users collude in the block, it could achieve fully collusion resistant. Otherwise, the upper bound is $\lfloor \frac{1}{2}+\frac{1}{2}\sqrt{1+8\nu q(q^{t-3}-1)\sum q^{i}}\rfloor$.

Proof

In this application, SPBIBD is different from BIBD from the perspective of presence of the two points. Similar to theorem 2, the broadcast rate and broadcast information rate respectively depend on the number of secret information that the user stored and the number of block. In lemma 5.4, $n\times r=(q+1)q^{\frac{1}{2}(t-2)(t-3)-1}\prod \nolimits _{i=2}^{t-3}(q^{i}-1)$ and $\beta =q^{\frac{1}{2}(t-2)(t-3)-1}\prod \nolimits _{i=2}^{t-3}(q^{i}-1)$, thus $\rho$ and $\rho _{B}$ can be calculated easily.

To illustrate the advantage of SPBIBD in resisting collusion attack, we make the following analysis. Suppose that there are a number of unauthorized users conspire to obtaining secret information $a_{0}$ in broadcast. Let the set of unauthorized users be F, and $|F|\le \omega$, obviously $F\bigcap P=\emptyset$. Obviously, any unauthorized users $x\notin P$ are unable to obtain secret information $a_{0}$ in broadcasting. Assumes that F and B $(B\bigcap P\ne \emptyset )$ have two or more common users, then the public key $k_{B\bigcap P}$ of block B can be calculated by the defected users of B. Denote the set of these blocks by $A_{F}=\{B\subset \mathcal {B}||B\bigcap F|\ge 2 \, \,{\rm and}\, \,F\bigcap P=\emptyset \}$, then $A_{F}\le \lambda \left( {\begin{array}{c}\omega \\ 2\end{array}}\right)$, because $|F|\le \omega$ (in this scenario, $r$ and $\lambda$ are constants. With this conclusion, we can get the upper bound of the number of resist conspiracy attacks in above scheme:

• Case 1: when $\lambda =0$, any unauthorized users collusion can not get any information.(There exists no example in BIBD)

• Case 2: when $\lambda \ne 0$, if $\lambda _{2}\left( {\begin{array}{c}\omega \\ 2\end{array}}\right) <\lambda _{1}$, similar to case 1, illegal users can not recover $r-1$ order polynomial $f(x)$ and fail to obtain the plaintext $a_{0}$. The users of the set $F$ conspired can only calculate $\lambda _{1}-1$ public keys at most. They can gain $r-1$ shares corresponding to public key and can not recover $r-1$ order polynomial $f(x)$. Thus, the plaintext is kept secure.

If the probability of above two cases is relatively low, we use probability to measure the success rate of collusion attack. Let $\vartheta$ be the probability of any two users of F occurred in any block, where $0\le \vartheta \le 1$. The number of keys that the collusion attackers can gain is $\lambda _{1}(1-\vartheta )\left( {\begin{array}{c}\omega \\ 2\end{array}}\right) +\lambda _{2}\vartheta \left( {\begin{array}{c}\omega \\ 2\end{array}}\right)$, where $\lambda _{1}=0$. Thus, this scheme can prevent $\omega$ unauthorized users’ collusion attack, where $\lambda _{1}(1-\vartheta )\left( {\begin{array}{c}\omega \\ 2\end{array}}\right) +\lambda _{2}\vartheta \left( {\begin{array}{c}\omega \\ 2\end{array}}\right) <r$. $\square$

Considering the parameters into number field, the security of schemes is shown as follow (Table 2):

Table 2 Comparison of schemes’ security

6 An improved construction

In this section, we use dual design to improvement program, and compare the performance differences between schemes.

Definition 6.1

(Colbourn and Charles 1996) Let $\mathcal {D}=(\mathcal {V },\mathcal {B },I)$ be a limited correlation structure. Let $\mathcal {D}^{*}=(\mathcal {V }^{*},\mathcal {B }^{*},I^{*})$, where $\mathcal {V }^{*}=\mathcal {B }$, $\mathcal {B }^{*}=\mathcal {V }$. we say that $\mathcal {D}^{*}$ is the dual design of D if and only if $\mathcal {B }^{*}IP^{*}$ having $P ^{*}I^{*}\mathcal {B }^{*}$ for any $P^{*}\in \mathcal {V }^{*}$ ,$B^{*}\in \mathcal {B}^{*}$.

Obviously, this kind of special designs exists dual designs when $\lambda _{t}=1$. So we have proposition as follow:

Theorem 5

For a $PA(t,s)$, there exists a $\left(s,\left( {\begin{array}{c}s\\ t\end{array}}\right) ,t^{-1}\left( {\begin{array}{c}s-1\\ t-1\end{array}}\right) , \left( {\begin{array}{c}s-2\\ t-2\end{array}}\right) \left( {\begin{array}{c}n\\ 2\end{array}}\right) \left( {\begin{array}{c}t\\ 2\end{array}}\right) ^{-1}\right)$ -design, and its dual scheme is $(\left( {\begin{array}{c}s\\ t\end{array}}\right) ),s,n,t-1)-$ design.

Theorem 6

Let $t\ge 5$ be a positive integer, for any prime power $q\ge t-1$. There exists a $((q-1)^{-1}(q^{t-2}-1),\beta ,q+1,\beta ,1:0)-$ design, and its dual scheme is $(\beta ,(q-1)^{-1}(q^{t-2}-1),q+1,t-1)-$ design, where

$$\begin{aligned} \beta =q^{\frac{(t-2)(t-3)}{2}-1}\prod \nolimits _{i=2}^{t-3}(q^{i}-1). \end{aligned}$$

The key distinction between design and its dual design to construct a BE scheme is that in the original construction, the users corresponding to points of blocks, user groups corresponding to the blocks. While using the dual design scheme, the user groups corresponding to points of blocks, users corresponding to the blocks. Thus, the improvement program can improve the broadcast information rate more obvious (Table 3).

Table 3 Comparison of efficiency

By using the list above, the broadcast information rate of improvement scheme is improved significantly. For example, in Sect. 5, let $q=5, n=2$, then we can construct a $(31,\,3000,\,600,\,5)-$design. That is, this construction only accommodates $32$ users with $3000$-user group having $\rho _{B}=\frac{1}{3000}$. It is not optimal obviously. While using its dual design, namely exchange points and blocks, then we get a $(3000,31,6,4)-$design. Its broadcast information rate becomes $\frac{1}{31}$. In practice, the broadcast encryption involves large numbers of user. When the number of users is determined, we can realize BE scheme by selecting the appropriate q. So, dual design not only conforms to the actual demand but also improve the efficiency of it.

7 Block reservation

In the BE schemes based on BIBD, when adding new users, it has to update all the keys held by authorized users. The scheme even has to be updated in the whole system. In this section, we introduce a new solution where the authorized users are treated as points in reserved blocks (see Fig. 1). Thus, the number of new users and authorized users is related with the searching block design. Then, the work including key pre-distribution as well as initialization can be performed easily. For example, in the block reserved PA scheme, broadcasting center (BC) selects an appropriate PA according to the number mentioned above. Then, the user allocation and key pre-distribution can be done by the blocks of this PA, while the keys corresponding to the reserved blocks are stored by BC for the registration of new users.

Fig. 1

The structure chart of differentiated users with blocks reservation

7.1 Block reservation scheme

A typical block reservation BE system based on BIBD includes five phases, that is, system initialization, key pre-distribution, registration of new users, sending broadcast message, receiving broadcast message. Without loss generality, we assume that the number of new users and old users are equal to each other.

• 1. System Initialization. The trusted authority (TA) selects a BD instance satisfying the numbers of old users and new users, such that each old user can be mapped into a different point in this BD instance.

• 2. Key Pre-distribution. After generating all the keys required by the system, almost one half of keys are transmitted to old users by Stinson Scheme (Stinson and Van Trung 1998) and the other half which are intended to be transmitted to new users are stored by TA. Now one set of keys, one point of BD instance and one user are linked together.

• 3. Registration of New Users. Once new users are requiring for joining this network, the TA is to transmit the prior stored keys to them respectively by mapping them to points.

• 4. Sending Broadcast Message. When a set of legal users is chosen, BC encrypts and broadcasts a message by the method introduced in Sect. 3.

• 5. Receiving Broadcast Message. Any legal user in this set can decrypt the message through the keys he owns, while the illegal users can not.

7.2 Comparison of block reservation schemes

We compare the proposed constructions in this paper in terms of the storage and length of messages.

• Storage: The storage of user keys is determined by the repetitions of this user (a point) $r$ and the size of user group (a block) $k$. Since the reserved blocks are concatenated by some blocks, both $r$ and $k$ are constant. Therefore, the storage of block reservation schemes is the same as that of the original one (Table 4).

• Length of Message: Let $N^{'}$ be the number of old users and $N^{*}$ be the number of new users. The total number of users is $N=N^{'}+N^{*}$. Let $S^{'}$ be the number of blocks and $S^{*}$ be the number of reserved blocks. According to the definition of broadcast information rate, the length of broadcast message is the number of blocks that have legal users. In the worse case that all blocks have legal users, the length of broadcast message in block reservation scheme is $S=S^{'}+S^{*}$ for new users are in reserved blocks. Specially in the case $N^{'}=N^{*}$, the performance comparison of schemes is shown in Table 5.

Table 4 The storage of scheme with blocks reservation

Table 5 Comparision of scheme performances with blocks reservation

For the block reservation scheme, the storage overhead is the same as that of the original constructions while the length of message increases with the number of blocks. Thus, the information rate keeps the same, and the broadcast information rate increases with the number of blocks decrease.

7.3 Security analysis

Block reservation scheme is an extension of the original scheme. It guarantees that it is as secure as the original one. It is necessary to look into the forward security that new registered users are not able to decrypt the broadcast message sent before registration. In block reservation scheme, the keys associated with block and reserved block are independent and old message is encrypted under those keys, so that the new joined users will not be issued with those keys and are not able to get any information of the message before their registrations. Consequently, the forward security is achieved.

8 Conclusion

In this paper, we showed that any BIBD can be used to realize secure BE schemes. According to the characteristics of the block, a more efficient broadcast encryption, using the SPBIBD constructed by rational normal curve was also presented. This scheme is secure under an enhanced security model compared with the first construction. Moreover, an improved scheme was given based on the efficiency comparison of these two schemes, in which the broadcast rate is invariant while its broadcast information rate is significantly higher than that of the first construction. We also calculated the broadcast rate, the broadcast information rate and the maximum number of collusion resistant. Finally, we proved that higher broadcast information rate can be achieved in these constructions.