1 Introduction

Multi-sender authentication code was given by Gilbert, Macwilliams and Sloane firstly in Ref.[1] in 1974. Multi-sender authentication system refers to that a group of senders cooperatively transmits a message to a receiver, and then the receiver should be able to ascertain that the message is authentic. The results of the study on authentication codes and Multi-sender authentication codes were very fruitful and many scholars made great contributions ^[2-16].

In the realistic computer network communications, Multi-sender authentication code includes two kinds of models, that is, sequential model and simultaneous model. Sequential model refers to that each sender uses his own encoding rules to encode a source state in order, and the final sender transmits the encoded message to the receiver, the receiver receives the message and identities whether the message is legal or not. Simultaneous model refers to that all senders use their own encoding rules to encode a source state, and each sender transmits the encoded message to the synthesizer respectively, then the synthesizer forms an authenticated message and transmits the authenticated message to the receiver, the receiver receives the message and identifies whether the message is legal or not. In this article, the second model is adopted.

In a simultaneous model, there are four participants: a group of senders U={U₁, U₂, …, U_n}, a receiver R, the keys distribution center and a synthesizer. The keys distribution center is responsible for the key distribution to senders and receiver, including settling the disputes between senders and receiver. The synthesizer only runs the reliable synthesis algorithm. Each sender and receiver have their own Cartesian authentication code respectively. Let (S, E_i, T_i; f_i)(i=1, 2, …, n) be the sender's Cartesian authentication code, (S, E_R, T; g) be the receiver's Cartesian authentication code, h: T₁×T₂×…×T_n→T be the synthesis algorithm, π_i: E→E_i be a subkey generation algorithm, where E is the key set of the key distribution center. When authenticating a message, the senders and the receiver should comply with the agreement: the key distribution center randomly selects an encoding rule e∈E and transmits e_i=π_i(e) to the ith sender U_i(1, 2, …, n) secretly, then it computes e_R by e according to an efficient algorithm, and secretly transmits e_R to the receiver R. If the senders would like to transmit a source state s to the receiver R, U_i computes t_i=f_i(s, e_i) (i=1, 2, …, n) and transmits m_i=(s, t_i)(i=1, 2, …, n) to the synthesizer through an open channel. The synthesizer receives the message m_i=(s, t_i)(i=1, 2, …, n) and computes t=h(t₁, t₂, …, t_n) by the synthesis algorithm h, then transmits the message m=(s, t) to the receiver, it checks the authenticity by identifying whether t=g(s, e_R) or not. If the equality holds, the message is authentic and is accepted. If not, the message is rejected.

Suppose the key distribution center is reliable, though he knows the senders' and receiver's encoding rules, it will not participate in any communication activities. When senders and receiver are disputing, the key distribution center solves it. At the same time, suppose the system follows the Kerckhoff's principle which excepts the actual used keys, the other information of the whole system is public.

In a Multi-sender authentication system, suppose that the whole senders are cooperated to form a valid message, that is, all senders as a whole and receiver are reliable. But there are some malicious senders, they unite to deceive the receiver, the part of senders and receiver are not reliable, they can take impersonation attack and substitution attack. In the whole system, suppose {U₁, U₂, …, U_n} are senders, R is a receiver, E_i is the encoding rules set of the sender U_i, e_R is the decoding rules set of the receiver R. If the source state space S and the key space E_R of receiver R conform to a uniform distribution, then the message space M and the tag space T are determined by the probability distribution of S and E_R.We denote L={i₁, i₂, …, i_l}⊂ {1, 2, …, n}, l < n, U_L={U_i1, U_i2, …, U_il}, E_L={E_i1, E_i2, …, E_il}. Now study the attacks from malicious groups of transmitters. We consider three kinds of spoofing attack:

1) The opponent's impersonation attack to receiver.U_L, after receiving their secret keys, encodes a message and transmits it to receiver. U_L is successful if receiver accepts it as legitimate message. Denote P_I the largest probability of some opponent's successful impersonation attack to receiver, it can be represented as:

$ {P_I} = \mathop {\max }\limits_{m \in M} \left\{ {\frac{{\left| {\left\{ {{e_R} \in {E_R}\left| {{e_R} \subset m} \right.} \right\}} \right|}}{{\left| {{E_R}} \right|}}} \right\} $

2) The opponent's substitution attack to the receiver.U_L uses another message m′ instead of the message m, after they observe a legitimate message m. U_L is successful if the receiver accepts it as a legitimate message, it can be represented as:

$ {P_S} = \mathop {\max }\limits_{m \in M} \left\{ {\frac{{\mathop {\max }\limits_{m' \ne m \in M} \left| {\left\{ {{e_R} \in {E_R}\left| {{e_R} \subset m,m'} \right.} \right\}} \right|}}{{\left| {\left\{ {{e_R} \in {E_R}\left| {{e_R} \subset m} \right.} \right\}} \right|}}} \right\} $

3) There might be l malicious senders who unite to cheat the receiver, that is, the part of senders and the receiver are not reliable, they can take impersonation attack.

Let L={i₁, i₂, …, i_l}⊂{1, 2, …, n}, l < n, E_L={E_i1, E_i2, …, E_il}. Assume U_L={U_i1, U_i2, …, U_il}, U_L after receiving their secret keys, transmits a message m to the receiver R, U_L is successful if the receiver accepts it as a legitimate message. Denote P_U(L) the maximum probability of success of the impersonation attack to the receiver. It can be represented as:

$ {P_U}\left( L \right) = \mathop {\max }\limits_{{e_L} \in {E_{L,}}} \mathop {\max }\limits_{{e_L} \in {e_u}} \left\{ {\frac{{\mathop {\max }\limits_{m \in M} \left| {\left\{ {{e_R} \in {E_R}\left| {{e_R} \subset m} \right.,{\rm{and}}\;p\left( {{e_R},{e_U}} \right) \ne 0} \right\}} \right|}}{{\left| {\left\{ {{e_R} \in {E_R}\left| {\;p\left( {{e_R},{e_U}} \right) \ne 0} \right.} \right\}} \right|}}} \right\} $

2 Preliminary Knowledge 2.1 Definition of Finite Fields and Some Relevant Conclusions

Definition 2.1.1  A finite field is a field that contains finite elements.

Theorem 2.1.2  Let F_q be the finite field with q elements, denote F_q^* all nonzero elements set of F_q, and F_q^* forms a cycle group.

Definition 2.1.3  A generator α of F_q^* is called a primitive element of F_q.

Definition 2.1.4  Let α be a primitive element of F_q, then 1, α, α², …, α^n-1 are linearly independent, furthermore, α, α², …, αⁿ(n < q) are also linearly independent.

Theorem 2.1.5  Let α be a generator of F_q^*, and if k is an integer that is relatively prime to m, then α^k is also a generator of F_q^*.

The above conclusions come from the Ref.[17].

2.2 Eigenvalues and Eigenvectors of a Matrix and the Relevant Properties

Definition 2.2.1  Let A be a matrix over F_q^n×n, x be a n dimension non-zero column vector over F_q, λ∈F_q be a number, if the equation Ax=λx holds, then we call x an eigenvector of A, and call λ an eigenvalue of A corresponding to x.

Theorem 2.2.2  A n×n matrix A is diagonalized if and only if A has n linearly independent eigenvectors.

Theorem 2.2.3  Let A be a n×n diagonalized matrix over F_q, x₁, x₂, …, x_n be n linearly independent unit eigenvectors (column vector) of A, and λ₁, λ₂, …, λ_n be corresponding eigenvectors of x₁, x₂, …, x_n respectively. If we have the matrices

$ \mathit{\boldsymbol{P}} = \left[ {{x_1},{x_2}, \cdots ,{x_n}} \right] $

$ \mathit{\boldsymbol{ \boldsymbol{\varLambda} }} = \left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right] $

then the equation A=PΛP^-1 holds.

Theorem 2.2.4  A n order invertible symmetrical matrix must be diagonalized.

Lemma 2.2.5  If A is a n×n invertible symmetrical matrix, then the eigenvectors of corresponding different eigenvalues are orthogonal. Making these linearly independent eigenvector which are corresponding multiple eigenvalue of A are orthogonal to each other by Schmidt orthogonal method, and making them unitization again, we get a group of orthogonal unitization eigenvectors ξ₁, ξ₂, …, ξ_n. Denote P=[ξ₁, ξ₂, …, ξ_n], obviously, P is an orthogonal matrix and the equation A=PΛP^-1 holds.

The above conclusions come from the Pef.[18].

Theorem 2.2.6^[19]  The number of invertible matrix over F_q^n×n is

$ \prod\limits_{j = 0}^{n - 1} {\left( {{q^n} - {q^j}} \right)} = {q^{\frac{{n\left( {n - 1} \right)}}{2}}}\prod\limits_{j = 1}^n {\left( {{q^j} - 1} \right)} $

Theorem 2.2.7^[18]  If for any n order square matrix A, a n order square matrix P satisfying the equation AP=PA, then P is a n order scalar matrix.

2.3 Related Definition of Authentication Codes

Definition 2.3.1^[3]  Let S, E and M be nonempty set. Assume f: S×E→M is a surjective mapping from S×E to M, if for any given e∈E, m∈M, s satisfying f(s, e)=m is uniquely determined by e and m, then we called the tetrad (S, E, M; f) an authentication code.

2.4 Some Definition and Related Properties of Group Theory

Definition 2.4.1  Suppose G is a group, H is a subgroup of G, then the number of left (or right) cosets of H in G is called index of H in G, denoted by [G: H].

Theorem 2.4.2  Let G be a finite group. If H is a subgroup of G, then |G|=|H|[G: H].

Definition 2.4.3  Suppose Ω be the object set and the group G effects on Ω, a∈Ω, then Ω_a={g(a)|g∈G} is called an orbit of Ω under G, a is called representative element of the orbit.

Definition 2.4.4  Let the group G effect on Ω, a∈Ω, then G_a={g|g∈G, g(a)=a} is called stable subgroup about the element a, denoted by Stab_G^a.

Theorem 2.4.5  For the group G, the orbit Ω_a and the stable subgroup G_a, the orbit formula about them is as follows: |Ω_a|=[G: G_a].

The above conclusions come from the Ref.[20].

2.5 Some Definition and Properties of the Matrix Over Finite Fields

Definition 2.5.1  Let S be an n×n invertible symmetric matrix over F_q, a n×n invertible symmetric matrix T is called orthogonal with respect to S, if the following equation holds: TST^T=S.

Theorem 2.5.2  A n×n invertible symmetric matrix over F_q is cogredient to one and only one of the following four normal forms:

$ {\mathit{\boldsymbol{S}}_{2\nu }} = \left[ {\begin{array}{*{20}{c}} 0&{{I^{\left( \nu \right)}}}\\ {{I^{\left( \nu \right)}}}&0 \end{array}} \right] $

$ {\mathit{\boldsymbol{S}}_{2\nu + 1,1}} = \left[ {\begin{array}{*{20}{c}} 0&{{I^{\left( \nu \right)}}}&0\\ {{I^{\left( \nu \right)}}}&0&0\\ 0&0&0 \end{array}} \right] $

$ {\mathit{\boldsymbol{S}}_{2\nu + 1,z}} = \left[ {\begin{array}{*{20}{c}} 0&{{I^{\left( \nu \right)}}}&0\\ {{I^{\left( \nu \right)}}}&0&0\\ 0&0&z \end{array}} \right] $

$ {\mathit{\boldsymbol{S}}_{2\nu + 2}} = \left[ {\begin{array}{*{20}{c}} 0&{{I^{\left( \nu \right)}}}&0&0\\ {{I^{\left( \nu \right)}}}&0&0&0\\ 0&0&1&0\\ 0&0&0&{ - z} \end{array}} \right] $

The above is the corresponding form successively when n=2ν, n=2ν+1, n=2ν+1 and n=2ν+2 respectively. In order to cover the four cases at the same time, we introduce the sign S_{2ν+δ, Δ}, where ν is its index, Δ denotes its definite part, the expression of Δ is as follows:

$ \Delta = \left\{ \begin{array}{l} \begin{array}{*{20}{c}} {\phi ,}&{\;\;\;\;\;\;\;\;\;\;\delta = 0} \end{array}\\ \begin{array}{*{20}{c}} {\left( 1 \right){\rm{or}}\left( z \right),}&{\delta = 1} \end{array}\\ \begin{array}{*{20}{c}} {\left[ {\begin{array}{*{20}{c}} 1&0\\ 0&{ - z} \end{array}} \right],}&{\delta = 2} \end{array} \end{array} \right. $

Theorem 2.5.3  Denote the set of all matrices which is orthogonal with respect to S_{2ν+δ, Δ} over F_q by O_{2ν+δ, Δ(Fq)}, then,

$ {O_{2\nu + \delta ,\Delta \left( {{F_q}} \right)}} = {q^{\nu \left( {\nu + \delta - 1} \right)}}\prod\limits_{i = 1}^\nu {\left( {{q^i} - 1} \right)} \prod\limits_{i = 0}^{\nu + \delta - 1} {\left( {{q^i} + 1} \right)} $

The above conclusions come from the Ref.[19].

3 Construction of the Multi-sender Authentication Code 3.1 Construction of the Multi-sender Authentication Code

Let F_q be a finite field of characteristic not 2, with q≥5, A be a nonsingular symmetric matrix over F_q^n×n, λ₁, λ₂, …, λ_n be eigenvalues of A, ξ₁, ξ₂, …, ξ_n be corresponding orthogonal unit eigenvectors, P=[ξ₁, ξ₂, …, ξ_n], obviously P is an orthogonal matrix, Λ be a diagonal matrix over F_q^n×n, its form is as follows:

$ \mathit{\boldsymbol{ \boldsymbol{\varLambda} }} = \left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right] $

From Theorem 2.2.5, we know that A=PΛP^-1, Λ=P^-1AP. Set α is a primitive element of F_q, N={1, 2, …, n}.

The source states set S=F_q^*;

The encoding rules set of the senders is E_Ui={(λ₁, i)|λ_i∈F_q^*, i∈N}(1≤i≤n).

The decoding rules set of the receiver is E_R={(P, A, α)|P, A∈F_q^n×n, α is a primitive element};

The label set of the sender T_i=F_q^*(1≤i≤n);

The label set of the receiver is T=F_q^*;

The encoding function of the sender U_i: f_i:

$ S \times {E_{{U_i}}} \to {T_i},{f_i}\left( {s,{e_{{U_i}}}} \right) = {\lambda _i}{s^i},1 \le i \le n $

The decoding function of the receiver R:

$ g:S \times {E_R} \to T $

$ \mathit{\boldsymbol{g}}\left( {s,{e_R}} \right) = \left[ {s,{s^2}, \cdots ,{s^n}} \right]{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{AP}}\left[ {\begin{array}{*{20}{c}} \alpha \\ {{\alpha ^2}}\\ \vdots \\ {{\alpha ^n}} \end{array}} \right] $

The Multi-sender authentication code works as follows:

1) Key distribution. The key distribution center randomly generates a n×n nonsingular symmetric matrix A over F_q. He computes n eigenvalues and n corresponding orthogonal unit eigenvectors, and selects a eigenvalue randomly, denoted by λ_i. If λ_i is a k- tuples eigenvalue, then it is taken k times at most, and it selects a eigenvector from all these orthogonal unit eigenvectors belonging to λ_i, denoted by ξ_i, and it sends privately (λ_i, i) to the sender U_i(1≤i≤n), it means e_Ui=(λ_i, i). After all e_Ui have been sent, ξ₁, ξ₂, …, ξ_n will be defined. When he generates the matrix P=[ξ₁, ξ₂, …, ξ_n], he selects a primitive elements α of F_q, and sends (A, P, α) to the receiver R, it means e_R=(A, P, α).

2) Broadcast. If the senders would like to transmit a source state s∈S to the receiver R, then the sender U_i computes t_i=f_i(s, e_Ui)=λ_isⁱ(1≤i≤n) and sends t_i to the synthesizer H.

3) Synthesis.After the synthesizer receives t₁, t₂, …, t_n, it computes h(t₁, t₂, …, t_n)=t₁α+t₂α²+…+t_nαⁿ=t and transmits m=(s, t) to the receiver R.

4) Verification. When the receiver R receives m=(s, t), it calculates

$ t' = g\left( {s,{e_R}} \right) = \left[ {s,{s^2}, \cdots ,{s^n}} \right]{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{AP}}\left[ {\begin{array}{*{20}{c}} \alpha \\ {{\alpha ^2}}\\ \vdots \\ {{\alpha ^n}} \end{array}} \right] $

If t=t′, it accepts t; If not, it rejects it.

From the definition of these parameters, we know when there is no attack.

$\begin{array}{l} t' = \left[ {s,{s^2}, \cdots ,{s^n}} \right]{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{AP}}\left[ {\begin{array}{*{20}{c}} \alpha \\ {{\alpha ^2}}\\ \vdots \\ {{\alpha ^n}} \end{array}} \right] = \\ \left[ {s,{s^2}, \cdots ,{s^n}} \right]\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}\left[ {\begin{array}{*{20}{c}} \alpha \\ {{\alpha ^2}}\\ \vdots \\ {{\alpha ^n}} \end{array}} \right] = \\ \left[ {s,{s^2}, \cdots ,{s^n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} \alpha \\ {{\alpha ^2}}\\ \vdots \\ {{\alpha ^n}} \end{array}} \right] = \\ {\lambda _1}s\alpha + {\lambda _2}{s^2}{\alpha ^2} + \cdots + {\lambda _n}{s^n}{\alpha ^n} = \\ {t_1}\alpha + {t_2}{\alpha ^2} + \cdots + {t_n}{\alpha ^n} = t \end{array} $

3.2 The Rationality of the Constructed Authentication Code

Lemma 3.2.1  Let C_i=(S, E_Ui, T_i; f_i)(1≤i≤n). Then the code is an A-code for the sender.

Proof  For any e_Ui∈E_Ui, s∈S, because E_Ui=(F_q^*, N), S=F_q^*, so t_i=λ_isⁱ∈F_q^*=T_i. For any t_i∈T_i=F_q^*, because F_q^* forms a cyclic group and the primitive element α of F_q is a generator of F_q^*, so we can assume t_i=α^k. We choose e_Ui=(λ_i, i)=(α^k-i, i)∈(F_q^*, N)=E_Ui, then there is s=α such that f_i(s, e_Ui)=λ_isⁱ=α^k-i·αⁱ=α^k=t_i holds, so f_i is surjective.

If s′∈S is another source state satisfying t_i=λ_isⁱ(1≤i≤n), that is,

$ \left[ {s',{{s'}^2}, \cdots ,{{s'}^n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} t\\ {{t^2}}\\ \vdots \\ {{t^n}} \end{array}} \right] $

then

$ \begin{array}{*{20}{c}} {\left[ {s',{{s'}^2}, \cdots ,{{s'}^n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} t\\ {{t^2}}\\ \vdots \\ {{t^n}} \end{array}} \right] = }\\ {\left[ {s,{s^2}, \cdots ,{s^n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right]} \end{array} $

and

$ \left[ {s - s',{s^2} - {{s'}^2}, \cdots ,{s^n} - {{s'}^n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right] = 0 $

Because λ_i∈F_q^*, that is, λ_i≠0, so

$\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right] $

is invertible. Therefore [s-s′, s²-s′², …, sⁿ-s′ⁿ]=[0, 0, …, 0], then s′=s, that is, s is the unique source state determined by e_Ui and t_i.

In conclusion, C_i(1≤i≤n) is an A-code for the senders.

Lemma 3.2.2  Let C=(S, E_R, T; g), then the code is an A-code for the receiver.

Proof  (1) For any s∈S, e_R∈E_R, because S=F_q^*, E_R={(P, A, α)|P, A∈F_q^n×n, α is a primitive element}, then

$ \begin{array}{l} g\left( {s,{e_R}} \right) = \left[ {s,{s^2}, \cdots ,{s^n}} \right]{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{AP}}{\left[ {\alpha ,{\alpha ^2}, \cdots ,{\alpha ^n}} \right]^{\rm{T}}} = \\ \;\;\;\;\;\;t \in F_q^ * \end{array} $

otherwise, we suppose

$ \left[ {s,{s^2}, \cdots ,{s^n}} \right]{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{AP}}{\left[ {\alpha ,{\alpha ^2}, \cdots ,{\alpha ^n}} \right]^{\rm{T}}} = t = 0 $

Because α₁, α₂, …, α_n is linearly independent, so [s, s², …, sⁿ]P^-1AP=0, but P^-1AP is invertible, so [s, s², …, sⁿ]=[0, 0, …, 0], that is, s=0, it is a contradiction to s∈S=F_q^*.Meanwhile, for any t∈T, we choose e_R∈E_R. Since s∈S such that g(s, e_R)=t holds, then

$ \left[ {s,{s^2}, \cdots ,{s^n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} \alpha \\ {{\alpha ^2}}\\ \vdots \\ {{\alpha ^n}} \end{array}} \right] = t $

It is equivalent to

$\left[ {{\alpha _1},{\alpha _2}, \cdots ,{\alpha _n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} s\\ {{s^2}}\\ \vdots \\ {{s^n}} \end{array}} \right] = t $

Let x₁=s, x₂=s², …, x_n=sⁿ be unknown variable, getting the matrix B as follows:

$ \mathit{\boldsymbol{B}} = \left[ {{\alpha _1},{\alpha _2}, \cdots ,{\alpha _n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right] $

So getting a system of linear equations in the variables

$ {x_1},{x_2}, \cdots ,{x_n}:\mathit{\boldsymbol{B}}\left[ {\begin{array}{*{20}{c}} {{x_1}}\\ {{x_2}}\\ \vdots \\ {{x_n}} \end{array}} \right] = t $

where B is the coefficient matrix of the system of linear equations. Obviously rank(B)=1, B=[B, t] is the augmented matrix the system of linear equations, from the definition of α, λ_i, t, we know rank(B)=1, that is, rank (B)=rank(B)=1.Therefore, from Theorem 2.2.8, the system of linear equations has solution, that is, there exists s satisfying g(s, e_R)=t. So g is surjective.

(2) If s′ is another source state satisfying t=g(s′, e_R), so get

$ \begin{array}{*{20}{c}} {\left[ {s',{{s'}^2}, \cdots ,{{s'}^n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} \alpha \\ {{\alpha ^2}}\\ \vdots \\ {{\alpha ^n}} \end{array}} \right] = t = }\\ {\left[ {s,{s^2}, \cdots ,{s^n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} \alpha \\ {{\alpha ^2}}\\ \vdots \\ {{\alpha ^n}} \end{array}} \right]}\\ {\left[ {s - s',{s^2} - {{s'}^2}, \cdots ,{s^n} - {{s'}^n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} \alpha \\ {{\alpha ^2}}\\ \vdots \\ {{\alpha ^n}} \end{array}} \right]{\rm{ = }}0}\\ {\left[ {{\alpha _1},{\alpha _2}, \cdots ,{\alpha _n}} \right]\left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {s - s'}\\ {{s^2} - {{s'}^2}}\\ \vdots \\ {{s^n} - {{s'}^n}} \end{array}} \right] = 0} \end{array} $

(1)

Because α is primitive element, from Theorem 2.1.4, we know that α, α², …, αⁿ linearly independent. So

$ \left[ \begin{array}{c} {\lambda _1}\;\;0\;\; \cdots \;\;0\\ 0\;\;{\lambda _2}\;\; \cdots \;\;0\\ \vdots \;\;\; \vdots \;\;\; \vdots \;\;\;\;\; \vdots \\ 0\;\;0\;\; \cdots \;\;{\lambda _n} \end{array} \right]\left[ \begin{array}{l} s - s'\\ {s^2} - {{s'}^2}\\ \vdots \\ {s^n} - {{s'}^n} \end{array} \right] = 0 $

Because λ_i≠0 1≤i≤n,

$ \left[ {\begin{array}{*{20}{c}} {{\lambda _1}}&0& \cdots &0\\ 0&{{\lambda _2}}& \cdots &0\\ \vdots&\vdots&\vdots&\vdots \\ 0&0& \cdots &{{\lambda _n}} \end{array}} \right] $

is invertible. Therefore, the above system of the Eq.(1) has only zero solution. Then

$ \left[ {s - s',{s^2} - {{s'}^2}, \cdots ,{s^n} - {{s'}^n}} \right]{\rm{ = }}\left[ {0,0, \cdots ,0} \right] $

So s-s′=0, s′=s, that is, s satisfying g(s, e_R)=t is the unique determined by e_R and t.

In conclusion, the code is an A-code for the receiver.

From Lemmas 3.2.1 and 3.2.2, it can be seen that the construction of this Multi-sender authentication code is reasonable. Next, we will begin to calculate the relevant parameters of constructed Multi-sender authentication code.

3.3 Computation of the Relevant Parameters About the Constructed Authentication Code

Lemma 3.3.1  Some relevant parameters of Multi-sender authentication code are as follows:

$ \begin{array}{*{20}{c}} {\left| S \right| = q - 1,\left| T \right| = q - 1,\left| {{T_i}} \right| = q - 1}\\ {{E_{{U_i}}} = n\left( {q - 1} \right)\left( {1 \le i \le n} \right)} \end{array} $

Proof  From the definitions of S, T, T_i and E_Ui, these results are obvious.

Theorem 3.3.2  Let A be n×n invertible symmetrical matrix over F_q. If A is cogredient to S_{2υ+δ, Δ} of Theorem 2.5.2, where 2υ+Δ=n, then the number of such A is:

$ \mathit{\Theta } = \frac{{{q^{n\left( {n - 1} \right)}}\prod\limits_{j = 1}^n {\left( {{q^j} - 1} \right)} }}{{{q^{v\left( {v + \delta - 1} \right)}}\prod\limits_{i = 1}^v {\left( {{q^i} - 1} \right)} \prod\limits_{i = 0}^{v + \delta - 1} {\left( {{q^i} + 1} \right)} }} $

Proof  Let G be the set of all invertible matrix over F_q^n×n. Obviously, (G, ×) is a group, where × is the multiplication with matrix, Ω be the set of all invertible symmetrical matrix over F_q^n×n. Choose S_2υ+δ∈Ω. We assume that Ω forms an orbit under G, Ω_S2υ+δ={T(S_2υ+δ, Δ)T∈G}, where T satisfies T(S)=TST^T. Obviously, T(S) is cogredient to S, then the stable subgroup of S_{2υ+δ, Δ}is:

$ {G_{{S_{2v + \delta ,\Delta }}}} = \left\{ {\mathit{\boldsymbol{T}}\left| {\mathit{\boldsymbol{T}} \in G} \right.,\mathit{\boldsymbol{T}}\left( {{S_{2v + \delta ,\Delta }}} \right) = {S_{2v + \delta ,\Delta }}} \right\} $

T contained in G_{S2υ+δ, Δ} satisfies the equation T(S_{2υ+δ, Δ})=TS_{2υ+δ, Δ}T^T=S_{2υ+δ, Δ}. According to Definition 2.5.1, T is orthogonal with respect to S_{2υ+δ, Δ}, G_{S2υ+δ, Δ} is composed of all T orthogonal with respect to S_{2υ+δ, Δ}. Therefore, from Theorem 2.5.3, we know that

$ \begin{array}{l} \left| {{G_{{S_{2v + \delta ,\Delta }}}}} \right| = \left| {{O_{{S_{2v + \delta ,\Delta }}}}\left( {{F_q}} \right)} \right| = \\ \;\;\;{q^{v\left( {v + \delta - 1} \right)}}\prod\limits_{i = 1}^v {\left( {{q^i} - 1} \right)} \prod\limits_{i = 0}^{v + \delta - 1} {\left( {{q^i} + 1} \right)} \end{array} $

Therefore, by Theorem 2.4.4 and Theorem 2.4.7, we get

$ \left| {{\mathit{\Omega }_{{S_{2v + \delta ,\Delta }}}}} \right| = \left| {G:{G_{{S_{2v + \delta ,\Delta }}}}} \right| = \frac{{\left| G \right|}}{{\left| {{G_{{S_{2v + \delta ,\Delta }}}}} \right|}} $

Because G is the set of all invertible matrices over F_q^n×n again, by Theorem 2.2.6, we know $\left| G \right| = {q^{\frac{{n\left( {n - 1} \right)}}{2}}}\prod\limits_{j = 1}^n {\left( {{q^j} - 1} \right)} $. Therefore,

$ \begin{array}{l} \left| {{\mathit{\Omega }_{{S_{2v + \delta ,\Delta }}}}} \right| = \frac{{\left| G \right|}}{{\left| {{G_{{S_{2v + \delta ,\Delta }}}}} \right|}} = \\ \;\;\;\;\;\;\frac{{{q^{n\left( {n - 1} \right)}}\prod\limits_{j = 1}^n {\left( {{q^j} - 1} \right)} }}{{{q^{v\left( {v + \delta - 1} \right)}}\prod\limits_{i = 1}^v {\left( {{q^i} - 1} \right)} \prod\limits_{i = 0}^{v + \delta - 1} {\left( {{q^i} + 1} \right)} }} \end{array} $

Since Ω_{S2υ+δ, Δ} is made up of all elements A which are cogredient to S_{2υ+δ, Δ}, |Ω_{S2υ+δ, Δ}| is equal to the number of invertible symmetrical matrix over F_q^n×n cogredienting to S_{2υ+δ, Δ}, that is,

$ \mathit{\Theta } = \frac{{{q^{n\left( {n - 1} \right)}}\prod\limits_{j = 1}^n {\left( {{q^j} - 1} \right)} }}{{{q^{v\left( {v + \delta - 1} \right)}}\prod\limits_{i = 1}^v {\left( {{q^i} - 1} \right)} \prod\limits_{i = 0}^{v + \delta - 1} {\left( {{q^i} + 1} \right)} }} $

Lemma 3.3.3  If α is a primitive element of F_q, then there are φ(n-1) choices for α, where φ(n-1) expresses the number of less than q-1 and relatively prime to q-1.

Proof  Because α is a primitive element of F_q, by Definition 2.1.3, α is a generator of F_q^*, the order of α is m, from the properties of generator, m=|F_q^*|=q-1. If k is an integer that relatively prime to m, by Theorem 2.1.5, α^k is a generator of F_q^*, that is, α^k is a primitive element of F_q.

When k > m, α^k=α^k-m and k-m relatively prime to m, the number of generator in F_q^* is equal to the number of positive integer less than m and relatively prime with m, because m=q-1. Therefore, there are φ(n-1) choices of α.

Lemma 3.3.4

$ \left| {{E_R}} \right| = \mathit{\Theta }\varphi \left( {q - 1} \right)n!\prod\limits_{i = 1}^m {\frac{{{q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{{\mathit{\boldsymbol{s}}_i}!}}} $

where Θ is given by Theorem 3.3.2, s_i means the multiple number of the eigenvalue λ_i and when i≠j, λ_i≠λ_j, 1≤i, j≤m, $\sum\limits_{i = 1}^m {{s_i} = n} $.

Proof  For any given n×n invertible symmetrical matrix A over F_q, it has m eigenvalues λ₁, λ₂, …, λ_m and they are different from each other, where λ_i is s_i multiple eigenvalues, 1≤i≤m≤n and $\sum\limits_{i = 1}^m {{s_i} = n} $. Because A is a symmetrical matrix, the eigenvalue λ_i has s_i linearly independent eigenvectors. In order to solve the corresponding eigenvectors of λ_i, need to solve the homogeneous linear equations (λ_iE-Α)x=0. Since the rank of coefficient matrix λ_iE-Α is n-s_i, there are s_i free variables, the number of solutions of the homogeneous linear equations is equal to the number of invertible matrix, where the order of invertible matrix is s_i over F_q. By the theorem 2.2.5, the number of such invertible matrix is

$ \prod\limits_{j = 0}^{{s_i} - 1} {\left( {{q^{{s_i}}} - {q^j}} \right)} = {q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} $

Once the basic solutions system of λ_iE-A is determined, then s_i linearly independent eigenvectors of λ_i are also unique determined and these eigenvectors are in order, when these eigenvectors are no order, suppose there are k_i possible choices for s_i eigenvectors, then there is the equation:

$ {k_i}{s_i}! = {q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} $

so

$ {k_i} = \frac{{{q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{{s_i}!}} $

By Schmidt orthogonal method, because the results of the orthogonality of the vector group x₁, x₂, …, x_n and the vector group kx₁, kx₂, …, kx_n (k≠0) are the same, so there are

$ \frac{{{k_i}}}{{q - 1}} = \frac{{{q^{\frac{{{s_i}\left( {{s_i} - 1} \right)}}{2}}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}} $

choice for s_i unit eigenvectors of corresponding to λ_i. Therefore, for any given matrix A, the number of ξ₁, ξ₂, …, ξ_n possible choice is

$ \prod\limits_{i = 1}^m {\frac{{{k_i}}}{{q - 1}}} = \prod\limits_{i = 1}^m {\frac{{{q^{\frac{{{s_i}\left( {{s_i} - 1} \right)}}{2}}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} $

where ξ₁, ξ₂, …, ξ_n are no order.

From the construction method of P from the above, every possible choice of P all is a permutation for ξ₁, ξ₂, …, ξ_n, therefore, for any given ξ₁, ξ₂, …, ξ_n, there are n! possible choice of P. So for any given A, the number of all possible cases of P is

$ n!\prod\limits_{i = 1}^m {\frac{{{q^{\frac{{{s_i}\left( {{s_i} - 1} \right)}}{2}}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} $

Because e_R=(A, P, α), where there are Θ possible cases for A, the number of P is

$ n!\prod\limits_{i = 1}^m {\frac{{{q^{\frac{{{s_i}\left( {{s_i} - 1} \right)}}{2}}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} $

and there are φ(n-1) choice for α.Therefore, there are

$ \mathit{\Theta }n!\prod\limits_{i = 1}^m {\frac{{{q^{\frac{{{s_i}\left( {{s_i} - 1} \right)}}{2}}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} $

choice for e_R=(A, P, α). That is,

$ \left| {{E_R}} \right| = \mathit{\Theta }\varphi \left( {q - 1} \right)n!\prod\limits_{i = 1}^m {\frac{{{q^{\frac{{{s_i}\left( {{s_i} - 1} \right)}}{2}}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} $

Lemma 3.3.5  For each m∈M, the number of e_R contained in m is 2φ³(q-1).

Proof  For each

$ m\left( {s,t} \right) \in M,{e_R} = \left( {P,A,\alpha } \right) \in {E_R} $

if e_R⊂m, then

$ \begin{array}{l} g\left( {s,{e_R}} \right) = \\ \;\;\;\left[ {s,{s^2}, \cdots ,{s^n}} \right]{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{AP}}{\left[ {\alpha ,{\alpha ^2}, \cdots ,{\alpha ^n}} \right]^{\rm{T}}} = \\ \;\;\;\left[ {s,{s^2}, \cdots ,{s^n}} \right]\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}{\left[ {\alpha ,{\alpha ^2}, \cdots ,{\alpha ^n}} \right]^{\rm{T}}} = t \end{array} $

For any α, suppose there is another Λ′ such than [s, s², …, sⁿ]Λ′[α, α², …, αⁿ]^T=t. We have

$ \left[ {s,{s^2}, \cdots ,{s^n}} \right]\left( {\mathit{\boldsymbol{ \boldsymbol{\varLambda} }} - \mathit{\boldsymbol{ \boldsymbol{\varLambda} '}}} \right){\left[ {\alpha ,{\alpha ^2}, \cdots ,{\alpha ^n}} \right]^{\rm{T}}} = 0 $

Because α, α², …, αⁿ are linearly independent, we get [s, s², …, sⁿ](Λ-Λ′)=0, from [s, s², …, sⁿ] is arbitrarily, we have Λ-Λ′=0, that is, Λ=Λ′. Therefore, Λ is only determined by α, so the number of α is φ(q-1).

In the following, we will discuss when Λ is determined, the number of A and P satisfying P^-1AP. Let G be the set of all invertible matrix over F_q^n×n. Obviously, (G, ×) is a group, where "×" is multiplication with matrix. Let Ω be the set of all invertible symmetrical matrix over F_q^n×n. We choose A∈Ω and assume Ω forms an orbit Ω_A under the action of G: Ω_A={P(A)|P∈G}, where P(A)=P^-1AP, then stable subgroup of A is G_A={P|P∈G, P(A)=A}, P contained in G_A satisfies the equation P(A)=P^-1AP=A i.e. AP=PA. By Theorem 2.2.7, such P is scalar matrix λE, because P∈G is an orthogonal matrix, PP^T=E. So λ=±1, P=±E, where E is a n order unit matrix. Then |G_A|=2.

From the orbit formula and the Lagrange theorem, we know that |G|=|Ω_A|·|G_A|. Now because the elements of Ω_A taking the form P(A)=P^-1AP and P^-1AP is only determined by α, for P^-1AP, there are φ(q-1) possible cases, that is, |Ω_A|=φ(q-1). So |G|=2φ(q-1), that is, there are 2φ(q-1) possible choices for P.

Because |Ω_A| is the number of all A turned into diagonal matrix by the similarity transformation P^-1AP, therefore, the number of A is φ(q-1) now. So when P^-1AP is determined, the number of (A, P) is 2φ²(q-1). In summary, the number of the triple (A, P, α) satisfying the known condition is 2φ³(q-1), that is, the number of e_R which is contained in m is 2φ³(q-1).

Lemma 3.3.6  For each m=(s, t)∈M, and m′=(s′, t′)∈m′ with s≠s′, the number of e_R which is contained m and m′ is 2φ²(q-1).

Proof  We assume e_R=(P, A, α). If e_R⊂m and e_R⊂m′, then

$ \begin{array}{*{20}{c}} {g\left( {s',{e_R}} \right) = \left[ {s',{{s'}^2}, \cdots ,{{s'}^n}} \right]{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{AP}}{{\left[ {\alpha ,{\alpha ^2}, \cdots ,{\alpha ^n}} \right]}^{\rm{T}}} = }\\ {\left[ {s',{{s'}^2}, \cdots ,{{s'}^n}} \right]\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}{{\left[ {\alpha ,{\alpha ^2}, \cdots ,{\alpha ^n}} \right]}^{\rm{T}}} = t'} \end{array} $

Furthermore, we obtain

$ \left[ {s - s',{s^2} - {{s'}^2}, \cdots ,{s^n} - {{s'}^n}} \right]\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}{\left[ {\alpha ,{\alpha ^2}, \cdots ,{\alpha ^n}} \right]^{\rm{T}}} = t - t' $

If t=t′, then t-t′=0. Since α, α², …, αⁿ is linearly independent,

$ \left[ {s - s',{s^2} - {{s'}^2}, \cdots ,{s^n} - {{s'}^n}} \right]\mathit{\boldsymbol{ \boldsymbol{\varLambda} }} = 0 $

Because Λ is invertible, we get

$ \left[ {s - s',{s^2} - {{s'}^2}, \cdots ,{s^n} - {{s'}^n}} \right] = 0 $

so s=s′, it is contradiction with the known conditions. So t≠t′, t-t′≠0. We obtain

$ {\left( {t - t'} \right)^{ - 1}}\left\lfloor {\left[ {s - s',{s^2} - {{s'}^2}, \cdots ,{s^n} - {{s'}^n}} \right]\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}{{\left[ {\alpha ,{\alpha ^2}, \cdots ,{\alpha ^n}} \right]}^{\rm{T}}}} \right\rfloor = 1 $

For any given m=(s, t), m′=(s′, t′), where s, s′, t and t′ are only determined. From the uniqueness of inverse element over finite fields, Λ[α, α², …, αⁿ]^T is only determined. From the properties of Λ and α, we know that such Λ and α are also only determined respectively. Similar to the proof of Lemma 3.3.5, the number of two-tuple (A, P) is 2φ²(q-1). So the number of e_R which is contained m and m′ is 2φ²(q-1).

Lemma 3.3.7  For each e_U containing a given e_L, the number of e_R which is incidence with e_U is

$ \left| {{E_R}} \right| = \mathit{\Theta }\varphi \left( {q - 1} \right)n!\prod\limits_{i = 1}^m {\frac{{{q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} $

Proof  From the above construction methods and the properties of e_U and e_R, we know that for any source state s,

$ \left| {{E_R}} \right| = \mathit{\Theta }\varphi \left( {q - 1} \right)n!\prod\limits_{i = 1}^m {\frac{{{q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} $

Lemma 3.3.8  For each e_U containing a given e_L, and m=(s, t), the number of e_R which is incidence with e_U and contained in m is 2φ²(q-1).

Proof  For any s∈S, e_R∈E_R, from Lemma 3.3.7, we know that for any given e_U, all of e_R are incidence with e_U Because e_R⊂m, so

$ \begin{array}{*{20}{c}} {g\left( {s,{e_R}} \right) = \left[ {s,{s^2}, \cdots ,{s^n}} \right]{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{AP}}{{\left[ {\alpha ,{\alpha ^2}, \cdots ,{\alpha ^n}} \right]}^{\rm{T}}} = }\\ {\left[ {s,{s^2}, \cdots ,{s^n}} \right]\mathit{\boldsymbol{ \boldsymbol{\varLambda} }}{{\left[ {\alpha ,{\alpha ^2}, \cdots ,{\alpha ^n}} \right]}^{\rm{T}}} = t} \end{array} $

Furthermore, t^-1[s, s², …, sⁿ]Λ[α, α², …, αⁿ]^T=1.

Similar to Lemma 3.3.6, it can be seen that Λ[α, α², …, αⁿ]^T is uniquely determined. Therefore, the number of e_R which is incidence with e_U and contained in m is 2φ²(q-1).

3.4 Computation of the Attack Probability About the Authentication Code

Theorem 3.4.1  In the constructed Multi-sender authentication code, if the senders' encoding rules and the receiver's decoding rules are chosen conforming to a uniform probability distribution, then the largest probabilities of success for different types of spoofing attack respectively are:

$ {P_I} = \frac{{2{\varphi ^2}\left( {q - 1} \right)}}{{n!\frac{{{q^{n\left( {n - 1} \right)/2}}\prod\limits_{j = 1}^n {\left( {{q^j} - 1} \right)} }}{{{q^{v\left( {v + \delta - 1} \right)}}\prod\limits_{i = 1}^v {\left( {{q^j} - 1} \right)} \prod\limits_{i = 0}^{v + \delta - 1} {\left( {{q^i} + 1} \right)} }}\prod\limits_{i = 1}^m {\frac{{{q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} }} $

$ {P_S} = \frac{1}{{\varphi \left( {n - 1} \right)}} $

$ {P_U}\left( L \right) = \frac{{2\varphi \left( {q - 1} \right)}}{{n!\frac{{{q^{n\left( {n - 1} \right)/2}}\prod\limits_{j = 1}^n {\left( {{q^j} - 1} \right)} }}{{{q^{v\left( {v + \delta - 1} \right)}}\prod\limits_{i = 1}^v {\left( {{q^i} - 1} \right)} \prod\limits_{i = 0}^{v + \delta - 1} {\left( {{q^i} + 1} \right)} }}\prod\limits_{i = 1}^m {\frac{{{q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} }} $

Proof  By Lemma 3.3.4 and Lemma 3.3.5,

$ \begin{array}{*{20}{c}} {{P_I} = \mathop {\max }\limits_{m \in M} \left\{ {\frac{{\left| {\left\{ {{e_R} \in {E_R}\left| {{e_R} \subset m} \right.} \right\}} \right|}}{{\left| {{E_R}} \right|}}} \right\} = \frac{{2{\varphi ^3}\left( {q - 1} \right)}}{{\mathit{\Theta }\varphi \left( {q - 1} \right)n!\prod\limits_{i = 1}^m {\frac{{{q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} }} = }\\ {\frac{{2{\varphi ^2}\left( {q - 1} \right)}}{{n!\frac{{{q^{n\left( {n - 1} \right)/2}}\prod\limits_{j = 1}^n {\left( {{q^j} - 1} \right)} }}{{{q^{v\left( {v + \delta - 1} \right)}}\prod\limits_{i = 1}^v {\left( {{q^i} - 1} \right)} \prod\limits_{i = 0}^{v + \delta - 1} {\left( {{q^i} + 1} \right)} }}\prod\limits_{i = 1}^m {\frac{{{q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} }}} \end{array} $

By Lemma 3.3.5 and Lemma 3.3.6, we get

$ {P_S} = \mathop {\max }\limits_{m \in M} \left\{ {\frac{{\mathop {\max }\limits_{m \ne m' \in M} \left| {\left\{ {{e_R} \in {E_R}\left| {{e_R} \subset m,m'} \right.} \right\}} \right|}}{{\left| {\left\{ {{e_R} \in {E_R}\left| {{e_R} \subset m} \right.} \right\}} \right|}}} \right\} = \frac{{2{\varphi ^2}\left( {q - 1} \right)}}{{2{\varphi ^3}\left( {q - 1} \right)}} = \frac{1}{{\varphi \left( {q - 1} \right)}} $

By Lemma 3.3.7 and Lemma 3.3.8, we get

$ \begin{array}{l} {P_U}\left( L \right) = \mathop {\max }\limits_{{e_L} \in {E_{L,}}} \mathop {\max }\limits_{{e_L} \in {e_u}} \left\{ {\frac{{\mathop {\max }\limits_{m \in M} \left| {\left\{ {{e_R} \in {E_R}\left| {{e_R} \subset m,} \right.{\rm{and}}\;p\left( {{e_R},{e_U}} \right) \ne 0} \right\}} \right|}}{{\left| {\left\{ {{e_R} \in {E_R}\left| {p\left( {{e_R},{e_U}} \right) \ne 0} \right.} \right\}} \right|}}} \right\} = \frac{{2{\varphi ^2}\left( {q - 1} \right)}}{{\mathit{\Theta }\varphi \left( {q - 1} \right)n!\prod\limits_{i = 1}^m {\frac{{{q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} }} = \\ \frac{{2\varphi \left( {q - 1} \right)}}{{n!\frac{{{q^{n\left( {n - 1} \right)/2}}\prod\limits_{j = 1}^n {\left( {{q^j} - 1} \right)} }}{{{q^{v\left( {v + \delta - 1} \right)}}\prod\limits_{i = 1}^v {\left( {{q^i} - 1} \right)} \prod\limits_{i = 0}^{v + \delta - 1} {\left( {{q^i} + 1} \right)} }}\prod\limits_{i = 1}^m {\frac{{{q^{{s_i}\left( {{s_i} - 1} \right)/2}}\prod\limits_{j = 1}^{{s_i}} {\left( {{q^j} - 1} \right)} }}{{\left( {q - 1} \right){s_i}!}}} }} \end{array} $