# A New Construction of Multisender Authentication Codes from Polynomials over Finite Fields

Authors: Xiuli Wang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Multisender authentication codes allow a group of senders to construct an authenticated message for a receiver such that the receiver can verify the authenticity of the received message. In this paper, we construct one multisender authentication code from polynomials over finite fields. Some parameters and the probabilities of deceptions of this code are also computed.


---

## Body

## 1. Introduction

Multisender authentication code was firstly constructed by Gilbert et al. [1] in 1974. Multisender authentication system refers to who a group of senders, cooperatively send a message to a receiver; then the receiver should be able to ascertain that the message is authentic. About this case, many scholars and researchers had made great contributions to multisender authentication codes, such as [2–6].In the actual computer network communications, multisender authentication codes include sequential model and simultaneous model. Sequential model is that each sender uses his own encoding rules to encode a source state orderly, the last sender sends the encoded message to the receiver, and the receiver receives the message and verifies whether the message is legal or not. Simultaneous model is that all senders use their own encoding rules to encode a source state, and each sender sends the encoded message to the synthesizer, respectively; then the synthesizer forms an authenticated message and verifies whether the message is legal or not. In this paper, we will adopt the second model.In a simultaneous model, there are four participants: a group of sendersU={U1,U2,…,Un}, the key distribution center,  he is responsible for the key distribution to senders and receiver, including solving the disputes between them, a receiver R, and a synthesizer, where he only runs the trusted synthesis algorithm. The code works as follows: each sender and receiver has their own Cartesian authentication code, respectively. Let (S,Ei,Ti;fi)(i=1,2,…,n) be the senders’ Cartesian authentication code, (S,ER,T;g) be the receiver’s Cartesian authentication code, h:T1×T2×⋯×Tn→T be the synthesis algorithm, and πi:E→Ei 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 protocol. The key distribution center randomly selects an encoding rule e∈E and sends ei=πi(e) to the ith sender Ui(i=1,2,…,n), secretly; then he calculates eR by e according to an effective algorithm and secretly sends eR to the receiver R. If the senders would like to send a source state s to the receiver R, Ui computes ti=fi(s,ei)(i=1,2,…,n) and sends mi=(s,ti)(i=1,2,…,n) to the synthesizer through an open channel. The synthesizer receives the message mi=(s,ti)(i=1,2,…,n) and calculates t=h(t1,t2,…,tn) by the synthesis algorithm h and then sends message m=(s,t) to the receiver; he checks the authenticity by verifying whether t=g(s,eR) or not. If the equality holds, the message is authentic and is accepted. Otherwise, the message is rejected.We assume that the key distribution center is credible, and though he know the senders’ and receiver’s encoding rules, he will not participate in any communication activities. When transmitters and receiver are disputing, the key distribution center settles it. At the same time, we assume that the system follows the Kerckhoff principle in which, except the actual used keys, the other information of the whole system is public.In a multisender authentication system, we assume that the whole senders are cooperative to form a valid message; that is, all senders as a whole and receiver are reliable. But there are some malicious senders who together cheat the receiver; the part of senders and receiver are not credible, and they can take impersonation attack and substitution attack. In the whole system, we assume that{U1,U2,…,Un} are senders, R is a receiver, Ei is the encoding rules set of the sender Ui, and ER is the decoding rules set of the receiver R. If the source state space S and the key space ER of receiver R are according to a uniform distribution, then the message space M and the tag space T are determined by the probability distribution of S and ER. L={i1,i2,…,il}⊂{1,2,…,n}, l<n, UL={Ui1,Ui2,…,Uil}, EL={EUi1,EUi2,…,EUil}. Now consider that  let us consider the attacks from malicious groups of senders. Here, there are two kinds of attack.The opponent’s impersonation attack to receiver:UL, after receiving their secret keys, encode a message and send it to the receiver. UL are successful if the receiver accepts it as legitimate message. Denote by PI the largest probability of some opponent’s successful impersonation attack to receiver; it can be expressed as
(1)PI=maxm∈M{|{eR∈ER∣eR⊂m}||ER|}.The opponent’s substitution attack to the receiver:UL replace m with another message m′, after they observe a legitimate message m. UL are successful if the receiver accepts it as legitimate message; it can be expressed as
(2)PS=maxm∈M{maxm′≠m∈M|{eR∈ER∣eR⊂m,m′}||{eR∈ER∣eR⊂m}|}.There might bel malicious senders who together cheat the receiver; that is, the part of senders and the receiver are not credible, and they can take impersonation attack. Let L={i1,i2,…,il}⊂{1,2,…,n}, l<n and EL={EUi1,EUi2,…,EUil}. Assume that UL={Ui1,Ui2,…,Uil}, after receiving their secret keys, send a message m to the receiver R; UL are successful if the receiver accepts it as legitimate message. Denote by PU(L) the maximum probability of success of the impersonation attack to the receiver. It can be expressed as
(3)PU(L)=maxeL∈ELmaxeL∈eU{maxm∈M|{eR∈ER∣eR⊂m,p(eR,eP)≠0}||{eR∈ER∣p(eR,eP)≠0}|}.Notes.p(eR,eP)≠0 implies that any information s encoded by eT can be authenticated by eR.In [2], Desmedt et al. gave two constructions for MRA-codes based on polynomials and finite geometries, respectively. To construct multisender or multireceiver authentication by polynomials over finite fields, many researchers have done much work, for example, [7–9]. There are other constructions of multisender authentication codes that are given in [3–6]. The construction of authentication codes is combinational design in its nature. We know that the polynomial over finite fields can provide a better algebra structure and is easy to count. In this paper, we construct one multisender authentication code from the polynomial over finite fields. Some parameters and the probabilities of deceptions of this code are also computed. We realize the generalization and the application of the similar idea and method of the paper [7–9].


## 2. Some Results about Finite Field

LetFq be the finite field with q elements, where q is a power of a prime p and F is a field containing Fq; denote by  Fq* be the nonzero elements set of Fq. In this paper, we will use the following conclusions over finite fields.Conclusion 1.
A generatorα of Fq* is called a primitive element of Fq.Conclusion 2.
Letα∈Fq; if some polynomials contain α as their  root and their leading coefficient are 1 over Fq, then the polynomial having least degree among all such polynomials is called a minimal polynomial over Fq.Conclusion 3.
Let|F|=qn, then F is an n-dimensional vector space over Fq. Let α be a primitive element of Fq and g(x) the minimal polynomial about α over Fq; then dimg(x)=n and 1,α,α2,…,αn-1 is a basis of F. Furthermore, 1,α,α2,…,αn-1 is linear independent, and it is equal to α,α2,…,αn-1,αn (α is a primitive element, α≠0) is also linear independent; moreover, αp,αp2,…,αpn-1,αpn is also linear independent.Conclusion 4.
Consider(x1+x2+⋯+xn)m=(x1)m+(x2)m+⋯+(xn)m, where xi∈Fq,(1≤i≤n) and m is a nonnegative power of character p of Fq.Conclusion 5.
Letm≤n. Then, the number of m×n matrices of rank m over Fq is qm(m-1)/2∏i=n-m+1n(qi-1).More results about finite fields can be found in [10–12].


## 3. Construction

Let the polynomialpj(x)=aj1xpn+aj2xp(n-1)+⋯+ajnxp(1≤j≤k), where the coefficient ail∈Fq, (1≤l≤n), and these vectors by the composition of their coefficient are linearly independent. The set of source states S=Fq; the set of ith transmitter’s encoding rules EUi={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}(1≤i≤n); the set of receiver’s encoding rules ER={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}; the set of ith transmitter’s tags Ti={ti∣ti∈Fq}(1≤i≤n); the set of receiver’s tags T={t∣t∈Fq}.Define the encoding mapfi:S×EUi→Ti, fi(s,eUi)=sp1(xi)+s2p2(xi)+⋯+skpk(xi), 1≤i≤n.The decoding mapf:S×ER→T, f(s,eR)=sp1(α)+s2p2(α)+⋯+skpk(α).The synthesizing maph:T1×T2×⋯×Tn→T, h(t1,t2,…,tn)=t1+t2+⋯+tn.The code works as follows.Assume thatq is larger than, or equal to, the number of the possible message and n≤q.


### 3.1. Key Distribution

The key distribution center randomly generatesk(k≤n) polynomials p1(x),p2(x),…,pk(x), where pj(x)=aj1xpn+aj2xp(n-1)+⋯+ajnxp(1≤j≤k), and make these vectors by composed of their coefficient is linearly independent, it is equivalent to the column vectors of the matrix (a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)  is linearly independent.  He selects n distinct nonzero elements x1,x2,…,xn∈Fq again and makes xi(1≤i≤n) secret; then he sends privately p1(xi),p2(xi),…,pk(xi) to the sender Ui(1≤i≤n). The key distribution center also randomly chooses a primitive element α of Fq satisfying x1+x2+⋯+xn=α and sends p1(α),p2(α),…,pk(α) to the receiver R.


### 3.2.  Broadcast

If the senders want to send a source states∈S to the receiver R, the sender Ui calculates ti=fi(s,eUi)=As(xi)=sp1(xi)+s2p2(xi)+⋯+skpk(xi), 1≤i≤n and then sends As(xi)=ti to the synthesizer.


### 3.3. Synthesis

After the synthesizer receivest1,t2,…,tn, he calculates h(t1,t2,…,tn)=t1+t2+⋯+tn and then sends m=(s,t) to the receiver R.


### 3.4. Verification

When the receiverR receives m=(s,t), he calculates t′=g(s,eR)=As(α)=sp1(α)+s2p2(α)+⋯+skpk(α). If t=t′, he accepts t; otherwise, he rejects it.Next, we will show that the above construction is a well defined multisender authentication code with arbitration.Lemma 1.
LetCi=(S,EPi,Ti,fi); then the code is an A-code, 1≤i≤n.Proof.
(
1
)  For any eUi∈EUi,s∈S, because EUi={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}, so ti=sp1(xi)+s2p2(xi)+⋯+skpk(xi)∈Ti=Fq. Conversely, for any ti∈Ti, choose eUi={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}, where pj(x)=aj1xpn+aj2xp(n-1)+⋯+ajnxp(1≤j≤k), and let ti=fi(s,eUi)=sp1(xi)+s2p2(xi)+⋯+skpk(xi); it is equivalent to
(4)(xipn,xipn-1,…,xip)(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)(ss2⋮sk)=ti.
It follows that
(5)(x1pnx1pn-1⋯x1px2pnx2pn-1⋯x2p⋮⋮⋮⋮xnpnxnpn-1⋯xnp)×(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)(ss2⋮sk)=(t1t2⋮tn).
Denote
(6)A=(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn),X=(x1pnx1pn-1⋯x1px2pnx2pn-1⋯x2p⋮⋮⋮⋮xnpnxnpn-1⋯xnp),S=(ss2⋮sk),t=(t1t2⋮tn).
The above linear equation is equivalent to XAS=t, because the column vectors of A are linearly independent, X is equivalent to a Vandermonde matrix, and X is inverse; therefore, the above linear equation has a unique solution, so s is only defined; that is, fi(1≤i≤n) is a surjection.
(
2
) If s′∈S is another source state satisfying sp1(xi)+s2p2(xi)+⋯+skpk(xi)=s′p1(xi)+s′2p2(xi)+⋯+s′kpk(xi)=ti, and it is equivalent to (s-s′)p1(xi)+(s2-s′2)p2(xi)+⋯+(sk-s′k)pk(xi)=0, then
(7)(xipn,xipn-1,…,xip)×(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)(s-s′s2-s′2⋮sk-s′k)=0.
Thus
(8)(x1pnx1pn-1⋯x1px2pnx2pn-1⋯x2p⋮⋮⋮⋮xnpnxnpn-1⋯xnp)×(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)(s-s′s2-s′2⋮sk-s′k)=(00⋮0).
Similar to (1), we know that the homogeneous linear equation XAS=0 has a unique solution; that is, there is only zero solution, so s=s′. So, s is the unique source state determined by eUi and ti; thus, Ci(1≤i≤n) is an A-code.Lemma 2.
LetC=(S,ER,T,g); then the code is an A-code.Proof.
(
1
) For any s∈S, eR∈ER, from the definition of eR, we assume that ER={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}, g(s,eR)=sp1(α)+s2p2(α)+⋯+skpk(α)∈T=Fq; on the other hand, for any t∈T, choose eR={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}, g(s,eR)=sp1(α)+s2p2(α)+⋯+skpk(α)=t; it is equivalent to
(9)(αpn,αpn-1,⋯,αp)×(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)(ss2⋮sk)=t,A=(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn);
that is, (αpn,αpn-1,…,αp)A(ss2⋮sk)=t. From Conclusion 3, we know that (αpn,αpn-1,…,αp) is linearly independent and the column vectors of A are  also linearly independent; therefore, the above linear equation has unique solution, so s is only defined; that is, g is a surjection.
(
2
) If s′ is another source state satisfying t=g(s′,eR), then
(10)(αpn,αpn-1,…,αp)A(s′s′2⋮s′k)=(αpn,αpn-1,…,αp)A(ss2⋮sk);
that is, (αpn,αpn-1,…,αp)A([s′s′2⋮s′k]-[ss2⋮sk])=0. Similar to (1), we get that the homogeneous linear equation (αpn,αpn-1,…,αp)A(S′-S)=0 has a unique solution; that is, there is only zero solution, so S=S′; that is, s=s′. So, s is the unique source state determined by eR and t; thus, C=(S,ER,T,g) is an A-code.
At the same time, for any validm=(s,t), we have known that α=x1+x2+⋯+xn, and it follows that t′=sp1(α)+s2p2(α)+⋯+skpk(α)=sp1(x1+x2+⋯+xn)+s2p2(x1+x2+⋯+xn)+⋯+skpk(x1+x2+⋯+xn). We also have known that pj(x)=aj1xpn+aj2xp(n-1)+⋯+ajnxp(1≤j≤k); from Conclusion 4, (x1+x2+⋯+xn)pm=(x1)pm+(x2)pm+⋯+(xn)pm, where m is a nonnegative power of character p of Fq, and we get pj(x1+x2+⋯+xn)=pj(x1)+pj(x2)+⋯+pj(xn); therefore, t′=sp1(α)+s2p2(α)+⋯+skpk(α)=(sp1(x1)+s2p2(x1)+⋯+skpk(x1))+(sp1(x2)+s2p2(x2)+⋯+skpk(x2))+⋯+(sp1(xn)+s2p2(xn)+⋯+skpk(xn))=t1+t2+⋯+tn=t, and the receiver R accepts m.From Lemmas1 and 2, we know that such construction of multisender authentication codes is reasonable and there are n senders in this system. Next, we compute the parameters of this code and the maximum probability of success in impersonation attack and substitution attack by the group of senders.Theorem 3.
Some parameters of this construction are|S|=q,|EUi|=[qk(k-1)/2∏i=n-k+1n(qi-1)](q-11)=[qk(k-1)/2∏i=n-k+1n(qi-1)](q-1)(1≤i≤n),|Ti|=q(1≤i≤n),|ER|=[qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1),|T|=q. Where φ(q-1) is the Euler  function of q-1, it represents the number of primitive element of Fq here.Proof.
For|S|=q,  |Ti|=q, and |T|=q, the results are straightforward. For EUi, because EUi={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}, where pj(x)=aj1xpn+aj2xp(n-1)+⋯+ajnxp(1≤j≤k), and these vectors by the composition of their coefficient are linearly independent, it is equivalent to the columns of A=(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn) is linear independent. From Conclusion 5, we can conclude that the number of A satisfying the condition is qk(k-1)/2∏i=n-k+1n(qi-1). On the other hand, the number of distinct nonzero elements xi(1≤i≤n) in Fq is (q-11)=q-1, so |EUi|=[qk(k-1)/2∏i=n-k+1n(qi-1)](q-1). For ER, ER={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}. For α, from Conclusion 1, a generator of Fq* is called a primitive element of Fq, |Fq*|=q-1; by the theory of the group, we know that the number of generator of Fq* is φ(q-1); that is, the number of α is φ(q-1). For p1(x),p2(x),…,pk(x). From above, we have confirmed that the number of these polynomials is qk(k-1)/2∏i=n-k+1n(qi-1); therefore, |ER|=[qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1).Lemma 4.
For anym∈M, the number of eR contained m is φ(q-1).Proof.
Letm=(s,t)∈M, eR={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}∈ER. If eR⊂m, then sp1(α)+s2p2(α)+⋯+skpk(α)=t⇔(αpn,αpn-1,…,αp)A(ss2⋮sk)=t. For any α, suppose that there is another A′ such that (αpn,αpn-1,…,αp)A′(ss2⋮sk)=t, then (αpn,αpn-1,…,αp)(A-A′)(ss2⋮sk)=0, because αpn,αpn-1,…,αp is linearly independent, so (A-A′)(ss2⋮sk)=0, but (ss2⋮sk) is arbitrarily; therefore, A-A′=0; that is, A=A′, and it follows that A is only determined by α. Therefore, as α∈ER, for any given s and t, the number of eR contained in m is φ(q-1).Lemma 5.
For anym=(s,t)∈M and m′=(s′,t′)∈M with s≠s′, the number of eR contained m and m′ is 1.Proof.
Assume thateR={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}∈ER. If eR⊂m and eR⊂m′, then sp1(α)+s2p2(α)+⋯+skpk(α)=t⇔(αpn,αpn-1,…,αp)A(ss2⋮sk)=t, s′p1(α)+s′2p2(α)+⋯+s′kpk(α)=t⇔(αpn,αpn-1,…,αp)A(s′s′2⋮s′k)=t. It is equivalent to (αpn,αpn-1,…,αp)A(s-s′s2-s′2⋮sk-s′k)=t-t′ because s≠s′, so t≠t′; otherwise, we assume that t=t′ and since αpn,αpn-1,…,αp and the column vectors of A both are linearly independent, it forces that s=s′; this is a contradiction. Therefore, we get
(*)(t-t′)-1[(αpn,αpn-1,…,αp)A(s-s′s2-s′2⋮sk-s′k)]=1,
since t,t′ is given, (t-t′)-1 is unique, by equation (*), for any given s,s′ and t,t′, we obtain that (αpn,αpn-1,…,αp)A is only determined; thus, the number of eR contained m and m′ is 1.Lemma 6.
For any fixedeU={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}(1≤i≤n) containing a given eL, then the number of eR which is incidence with eU is φ(q-1).Proof.
For any fixedeU={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}(1≤i≤n) containing a given eL, we assume that pj(xi)=aj1xipn+aj2xip(n-1)+⋯+ajnxip(1≤j≤k,1≤i≤n),  eR={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}. From the definitions of eR and eU and Conclusion 4, we can conclude that eR is incidence with eU if and only if x1+x2+⋯+xn=α. For any α, since Rank(1,1,…,1)=Rank(1,1,…,1,α)=1<n, so the equation x1+x2+⋯+xn=α always has a solution. From the proof of Theorem 3, we know the number of eR which is incident with eU (i.e., the number of all ER) is [qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1).Lemma 7.
For any fixedeU={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}(1≤i≤n) containing a given eL and m=(s,t), the number of eR which is incidence with eU and contained in m is 1.Proof.
For anys∈S,eR∈ER, we assume that eR={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}. Similar to Lemma 6, for any fixed eU={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}, (1≤i≤n) containing a given eL, we have known that eR is incident with eU if and only if
(11)x1+x2+⋯+xn=α.
Again, with eR⊂m, we can get
(12)sp1(α)+s2p2(α)+⋯+skpk(α)=t.
By (11) and (12) and the property of pj(x)(1≤j≤k), we have the following conclusion:
(13)sp1(∑i=1n‍xi)+s2p2(∑i=1n‍xi)+⋯+skpk(∑i=1n‍xi)=t⟺(p1(∑i=1n‍xi),p2(∑i=1n‍xi),…,pk(∑i=1n‍xi))×(ss2⋮sk)=t⟺(∑i=1n‍p1(xi),∑i=1n‍p2(xi),…,∑i=1n‍pk(xi))(ss2⋮sk)=t⟺((∑i=1n‍xi)n,(∑i=1n‍xi)n-1,…,(∑i=1n‍xi))A(ss2⋮sk)=t⟺[(∑i=1n‍p1(xi),∑i=1n‍p2(xi),…,∑i=1n‍pk(xi))-((∑i=1n‍xi)n,(∑i=1n‍xi)n-1,…,(∑i=1n‍xi))A]×(ss2⋮sk)=0,
because s is any given. Similar to the proof of Lemma 4, we can get (∑i=1np1(xi),∑i=1np2(xi),…,∑i=1npk(xi))-((∑i=1nxi)n,(∑i=1nxi)n-1,…,(∑i=1nxi))A=0; that is, ((∑i=1nxi)n,(∑i=1nxi)n-1,…,(∑i=1nxi))A=(∑i=1np1(xi),∑i=1np2(xi),…,∑i=1npk(xi)), but p1(xi),p2(xi),…,pk(xi) and xi(1≤i≤n) also are fixed; thus, α and Aare only determined, so the number of eR which is incident with eU and contained in m is 1.Theorem 8.
In the constructed multisender authentication codes, if the senders’ encoding rules and the receiver’s decoding rules are chosen according to a uniform probability distribution, then the largest probabilities of success for different types of deceptions, respectively, are(14)PI=1qk(k-1)/2∏i=n-k+1n(qi-1),PS=1φ(q-1),PU(L)=1[qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1).Proof.
By  Theorem 3 and Lemma4, we get
(15)PI=maxm∈M{|{eR∈ER∣eR⊂m}||ER|}=φ(q-1)[qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1)=1qk(k-1)/2∏i=n-k+1n(qi-1).
By Lemmas4 and 5, we get
(16)PS=maxm∈M{maxm′≠m∈M|{eR∈ER∣eR⊂m,m′}||{eR∈ER∣eR⊂m}|}=1φ(q-1).
By Lemmas6 and 7, we get
(17)PU(L)=maxeL∈ELmaxeL∈eU{maxm∈M|{eR∈ER∣eR⊂m,p(eR,eP)≠0}||{eR∈ER∣p(eR,eP)≠0}|}=1[qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1).


## 3.1. Key Distribution

The key distribution center randomly generatesk(k≤n) polynomials p1(x),p2(x),…,pk(x), where pj(x)=aj1xpn+aj2xp(n-1)+⋯+ajnxp(1≤j≤k), and make these vectors by composed of their coefficient is linearly independent, it is equivalent to the column vectors of the matrix (a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)  is linearly independent.  He selects n distinct nonzero elements x1,x2,…,xn∈Fq again and makes xi(1≤i≤n) secret; then he sends privately p1(xi),p2(xi),…,pk(xi) to the sender Ui(1≤i≤n). The key distribution center also randomly chooses a primitive element α of Fq satisfying x1+x2+⋯+xn=α and sends p1(α),p2(α),…,pk(α) to the receiver R.


## 3.2.  Broadcast

If the senders want to send a source states∈S to the receiver R, the sender Ui calculates ti=fi(s,eUi)=As(xi)=sp1(xi)+s2p2(xi)+⋯+skpk(xi), 1≤i≤n and then sends As(xi)=ti to the synthesizer.


## 3.3. Synthesis

After the synthesizer receivest1,t2,…,tn, he calculates h(t1,t2,…,tn)=t1+t2+⋯+tn and then sends m=(s,t) to the receiver R.


## 3.4. Verification

When the receiverR receives m=(s,t), he calculates t′=g(s,eR)=As(α)=sp1(α)+s2p2(α)+⋯+skpk(α). If t=t′, he accepts t; otherwise, he rejects it.Next, we will show that the above construction is a well defined multisender authentication code with arbitration.Lemma 1.
LetCi=(S,EPi,Ti,fi); then the code is an A-code, 1≤i≤n.Proof.
(
1
)  For any eUi∈EUi,s∈S, because EUi={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}, so ti=sp1(xi)+s2p2(xi)+⋯+skpk(xi)∈Ti=Fq. Conversely, for any ti∈Ti, choose eUi={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}, where pj(x)=aj1xpn+aj2xp(n-1)+⋯+ajnxp(1≤j≤k), and let ti=fi(s,eUi)=sp1(xi)+s2p2(xi)+⋯+skpk(xi); it is equivalent to
(4)(xipn,xipn-1,…,xip)(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)(ss2⋮sk)=ti.
It follows that
(5)(x1pnx1pn-1⋯x1px2pnx2pn-1⋯x2p⋮⋮⋮⋮xnpnxnpn-1⋯xnp)×(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)(ss2⋮sk)=(t1t2⋮tn).
Denote
(6)A=(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn),X=(x1pnx1pn-1⋯x1px2pnx2pn-1⋯x2p⋮⋮⋮⋮xnpnxnpn-1⋯xnp),S=(ss2⋮sk),t=(t1t2⋮tn).
The above linear equation is equivalent to XAS=t, because the column vectors of A are linearly independent, X is equivalent to a Vandermonde matrix, and X is inverse; therefore, the above linear equation has a unique solution, so s is only defined; that is, fi(1≤i≤n) is a surjection.
(
2
) If s′∈S is another source state satisfying sp1(xi)+s2p2(xi)+⋯+skpk(xi)=s′p1(xi)+s′2p2(xi)+⋯+s′kpk(xi)=ti, and it is equivalent to (s-s′)p1(xi)+(s2-s′2)p2(xi)+⋯+(sk-s′k)pk(xi)=0, then
(7)(xipn,xipn-1,…,xip)×(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)(s-s′s2-s′2⋮sk-s′k)=0.
Thus
(8)(x1pnx1pn-1⋯x1px2pnx2pn-1⋯x2p⋮⋮⋮⋮xnpnxnpn-1⋯xnp)×(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)(s-s′s2-s′2⋮sk-s′k)=(00⋮0).
Similar to (1), we know that the homogeneous linear equation XAS=0 has a unique solution; that is, there is only zero solution, so s=s′. So, s is the unique source state determined by eUi and ti; thus, Ci(1≤i≤n) is an A-code.Lemma 2.
LetC=(S,ER,T,g); then the code is an A-code.Proof.
(
1
) For any s∈S, eR∈ER, from the definition of eR, we assume that ER={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}, g(s,eR)=sp1(α)+s2p2(α)+⋯+skpk(α)∈T=Fq; on the other hand, for any t∈T, choose eR={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}, g(s,eR)=sp1(α)+s2p2(α)+⋯+skpk(α)=t; it is equivalent to
(9)(αpn,αpn-1,⋯,αp)×(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn)(ss2⋮sk)=t,A=(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn);
that is, (αpn,αpn-1,…,αp)A(ss2⋮sk)=t. From Conclusion 3, we know that (αpn,αpn-1,…,αp) is linearly independent and the column vectors of A are  also linearly independent; therefore, the above linear equation has unique solution, so s is only defined; that is, g is a surjection.
(
2
) If s′ is another source state satisfying t=g(s′,eR), then
(10)(αpn,αpn-1,…,αp)A(s′s′2⋮s′k)=(αpn,αpn-1,…,αp)A(ss2⋮sk);
that is, (αpn,αpn-1,…,αp)A([s′s′2⋮s′k]-[ss2⋮sk])=0. Similar to (1), we get that the homogeneous linear equation (αpn,αpn-1,…,αp)A(S′-S)=0 has a unique solution; that is, there is only zero solution, so S=S′; that is, s=s′. So, s is the unique source state determined by eR and t; thus, C=(S,ER,T,g) is an A-code.
At the same time, for any validm=(s,t), we have known that α=x1+x2+⋯+xn, and it follows that t′=sp1(α)+s2p2(α)+⋯+skpk(α)=sp1(x1+x2+⋯+xn)+s2p2(x1+x2+⋯+xn)+⋯+skpk(x1+x2+⋯+xn). We also have known that pj(x)=aj1xpn+aj2xp(n-1)+⋯+ajnxp(1≤j≤k); from Conclusion 4, (x1+x2+⋯+xn)pm=(x1)pm+(x2)pm+⋯+(xn)pm, where m is a nonnegative power of character p of Fq, and we get pj(x1+x2+⋯+xn)=pj(x1)+pj(x2)+⋯+pj(xn); therefore, t′=sp1(α)+s2p2(α)+⋯+skpk(α)=(sp1(x1)+s2p2(x1)+⋯+skpk(x1))+(sp1(x2)+s2p2(x2)+⋯+skpk(x2))+⋯+(sp1(xn)+s2p2(xn)+⋯+skpk(xn))=t1+t2+⋯+tn=t, and the receiver R accepts m.From Lemmas1 and 2, we know that such construction of multisender authentication codes is reasonable and there are n senders in this system. Next, we compute the parameters of this code and the maximum probability of success in impersonation attack and substitution attack by the group of senders.Theorem 3.
Some parameters of this construction are|S|=q,|EUi|=[qk(k-1)/2∏i=n-k+1n(qi-1)](q-11)=[qk(k-1)/2∏i=n-k+1n(qi-1)](q-1)(1≤i≤n),|Ti|=q(1≤i≤n),|ER|=[qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1),|T|=q. Where φ(q-1) is the Euler  function of q-1, it represents the number of primitive element of Fq here.Proof.
For|S|=q,  |Ti|=q, and |T|=q, the results are straightforward. For EUi, because EUi={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}, where pj(x)=aj1xpn+aj2xp(n-1)+⋯+ajnxp(1≤j≤k), and these vectors by the composition of their coefficient are linearly independent, it is equivalent to the columns of A=(a11a21⋯ak1a12a22⋯ak2⋮⋮⋮⋮a1na2n⋯akn) is linear independent. From Conclusion 5, we can conclude that the number of A satisfying the condition is qk(k-1)/2∏i=n-k+1n(qi-1). On the other hand, the number of distinct nonzero elements xi(1≤i≤n) in Fq is (q-11)=q-1, so |EUi|=[qk(k-1)/2∏i=n-k+1n(qi-1)](q-1). For ER, ER={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}. For α, from Conclusion 1, a generator of Fq* is called a primitive element of Fq, |Fq*|=q-1; by the theory of the group, we know that the number of generator of Fq* is φ(q-1); that is, the number of α is φ(q-1). For p1(x),p2(x),…,pk(x). From above, we have confirmed that the number of these polynomials is qk(k-1)/2∏i=n-k+1n(qi-1); therefore, |ER|=[qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1).Lemma 4.
For anym∈M, the number of eR contained m is φ(q-1).Proof.
Letm=(s,t)∈M, eR={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}∈ER. If eR⊂m, then sp1(α)+s2p2(α)+⋯+skpk(α)=t⇔(αpn,αpn-1,…,αp)A(ss2⋮sk)=t. For any α, suppose that there is another A′ such that (αpn,αpn-1,…,αp)A′(ss2⋮sk)=t, then (αpn,αpn-1,…,αp)(A-A′)(ss2⋮sk)=0, because αpn,αpn-1,…,αp is linearly independent, so (A-A′)(ss2⋮sk)=0, but (ss2⋮sk) is arbitrarily; therefore, A-A′=0; that is, A=A′, and it follows that A is only determined by α. Therefore, as α∈ER, for any given s and t, the number of eR contained in m is φ(q-1).Lemma 5.
For anym=(s,t)∈M and m′=(s′,t′)∈M with s≠s′, the number of eR contained m and m′ is 1.Proof.
Assume thateR={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}∈ER. If eR⊂m and eR⊂m′, then sp1(α)+s2p2(α)+⋯+skpk(α)=t⇔(αpn,αpn-1,…,αp)A(ss2⋮sk)=t, s′p1(α)+s′2p2(α)+⋯+s′kpk(α)=t⇔(αpn,αpn-1,…,αp)A(s′s′2⋮s′k)=t. It is equivalent to (αpn,αpn-1,…,αp)A(s-s′s2-s′2⋮sk-s′k)=t-t′ because s≠s′, so t≠t′; otherwise, we assume that t=t′ and since αpn,αpn-1,…,αp and the column vectors of A both are linearly independent, it forces that s=s′; this is a contradiction. Therefore, we get
(*)(t-t′)-1[(αpn,αpn-1,…,αp)A(s-s′s2-s′2⋮sk-s′k)]=1,
since t,t′ is given, (t-t′)-1 is unique, by equation (*), for any given s,s′ and t,t′, we obtain that (αpn,αpn-1,…,αp)A is only determined; thus, the number of eR contained m and m′ is 1.Lemma 6.
For any fixedeU={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}(1≤i≤n) containing a given eL, then the number of eR which is incidence with eU is φ(q-1).Proof.
For any fixedeU={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}(1≤i≤n) containing a given eL, we assume that pj(xi)=aj1xipn+aj2xip(n-1)+⋯+ajnxip(1≤j≤k,1≤i≤n),  eR={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}. From the definitions of eR and eU and Conclusion 4, we can conclude that eR is incidence with eU if and only if x1+x2+⋯+xn=α. For any α, since Rank(1,1,…,1)=Rank(1,1,…,1,α)=1<n, so the equation x1+x2+⋯+xn=α always has a solution. From the proof of Theorem 3, we know the number of eR which is incident with eU (i.e., the number of all ER) is [qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1).Lemma 7.
For any fixedeU={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}(1≤i≤n) containing a given eL and m=(s,t), the number of eR which is incidence with eU and contained in m is 1.Proof.
For anys∈S,eR∈ER, we assume that eR={p1(α),p2(α),…,pk(α), where α is a primitive element of Fq}. Similar to Lemma 6, for any fixed eU={p1(xi),p2(xi),…,pk(xi),xi∈Fq*}, (1≤i≤n) containing a given eL, we have known that eR is incident with eU if and only if
(11)x1+x2+⋯+xn=α.
Again, with eR⊂m, we can get
(12)sp1(α)+s2p2(α)+⋯+skpk(α)=t.
By (11) and (12) and the property of pj(x)(1≤j≤k), we have the following conclusion:
(13)sp1(∑i=1n‍xi)+s2p2(∑i=1n‍xi)+⋯+skpk(∑i=1n‍xi)=t⟺(p1(∑i=1n‍xi),p2(∑i=1n‍xi),…,pk(∑i=1n‍xi))×(ss2⋮sk)=t⟺(∑i=1n‍p1(xi),∑i=1n‍p2(xi),…,∑i=1n‍pk(xi))(ss2⋮sk)=t⟺((∑i=1n‍xi)n,(∑i=1n‍xi)n-1,…,(∑i=1n‍xi))A(ss2⋮sk)=t⟺[(∑i=1n‍p1(xi),∑i=1n‍p2(xi),…,∑i=1n‍pk(xi))-((∑i=1n‍xi)n,(∑i=1n‍xi)n-1,…,(∑i=1n‍xi))A]×(ss2⋮sk)=0,
because s is any given. Similar to the proof of Lemma 4, we can get (∑i=1np1(xi),∑i=1np2(xi),…,∑i=1npk(xi))-((∑i=1nxi)n,(∑i=1nxi)n-1,…,(∑i=1nxi))A=0; that is, ((∑i=1nxi)n,(∑i=1nxi)n-1,…,(∑i=1nxi))A=(∑i=1np1(xi),∑i=1np2(xi),…,∑i=1npk(xi)), but p1(xi),p2(xi),…,pk(xi) and xi(1≤i≤n) also are fixed; thus, α and Aare only determined, so the number of eR which is incident with eU and contained in m is 1.Theorem 8.
In the constructed multisender authentication codes, if the senders’ encoding rules and the receiver’s decoding rules are chosen according to a uniform probability distribution, then the largest probabilities of success for different types of deceptions, respectively, are(14)PI=1qk(k-1)/2∏i=n-k+1n(qi-1),PS=1φ(q-1),PU(L)=1[qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1).Proof.
By  Theorem 3 and Lemma4, we get
(15)PI=maxm∈M{|{eR∈ER∣eR⊂m}||ER|}=φ(q-1)[qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1)=1qk(k-1)/2∏i=n-k+1n(qi-1).
By Lemmas4 and 5, we get
(16)PS=maxm∈M{maxm′≠m∈M|{eR∈ER∣eR⊂m,m′}||{eR∈ER∣eR⊂m}|}=1φ(q-1).
By Lemmas6 and 7, we get
(17)PU(L)=maxeL∈ELmaxeL∈eU{maxm∈M|{eR∈ER∣eR⊂m,p(eR,eP)≠0}||{eR∈ER∣p(eR,eP)≠0}|}=1[qk(k-1)/2∏i=n-k+1n(qi-1)]φ(q-1).



---

*Source: 320392-2013-05-09.xml*