# A New Construction of Multisender Authentication Codes from Pseudosymplectic Geometry 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 one receiver such that the receiver can verify authenticity of the received message. In this paper, we construct one multisender authentication code from pseudosymplectic geometry over finite fields. The 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. in [1] in 1974. Multisender authentication system refers to a group of senders that cooperatively send a message to the receiver, and then the receiver should be able to ascertain that the message is authentic. About this case, many scholars had also much researches and had made great contributions to multisender authentication codes [2–6].In the actual computer network communications, multisender authentication codes include sequential model and simultaneous model. Sequential model is that each sender uses its own encoding 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, and 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 sendersP={P1,P2,…,Pn}, the keys distribution center, he is responsible for the key distribution to senders and receiver, including solving the disputes between them, a receiver R, a synthesizer, 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 the synthesis algorithm. πi:E→Ei is 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 Pi(i=1,2,…,n) secretly, and 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, Pi 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 R, 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, 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 Kerckhoff's principle in which except for 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 cooperating to form a valid message; that is, all senders as a whole and receiver are reliable. But there are some malicious senders which they together cheat the receiver, the part of senders and receiver are not credible, they can take impersonation attack and substitution attack.  In the whole system, we assume that{P1,P2,…,Pn} are senders, R is a receiver, Ei is the encoding rules set of the sender Pi, and ER is the decoding rules set of receiver R. If the source state space S and the key space ER of receiver R are according to a uniform distribution, then the probability distribution of message space M and tag space T is determined by the probability distribution of S and ER. Consider L={i1,i2,…,il}⊂{1,2,…,n},l<n, PL={p1,p2,…,pl}, and EL={Ep1,Ep2,…,Epl}. Now, let us consider the attacks from malicious groups of senders. Here, there still are two kinds of attacks.(i)The Opponent's Impersonation Attack. PL sends a message m to receiver. PL is successful if the receiver accepts it as legitimate message. Denote PI(L) as the largest probability of some opponent's successful impersonation attack, and it can be expressed as
(1)PI(L)=maxeL∈ELmaxm∈MP(misacceptedbyReL).(ii)The Opponent's Substitution Attack. It is the largest probability of some opponent's successful substitution attack, and it can be expressed as
(2)PS(L)=maxeL∈ELmaxm∈Mmaxm′≠m∈MP(m′isacceptedbyRm,eL).
In this paper, we give a construction about multisender authentication code from pseudosymplectic geometry over finite fields.


## 2. Pseudosymplectic Geometry

LetFq be the finite field with q elements, where q is a power of 2, n=2ν+δ, and δ=1,2. Let
(3)K=(0I(ν)I(ν)0),S1=(K1),S2=(K0111),
and Sδ is a (2ν+δ)×(2ν+δ) nonalternate symmetric matrix.The pseudosymplectic group of degree(2ν+δ) over Fq is defined to be the set of matrices Ps2ν+δ(Fq)={T∣TSδTt=Sδ} denoted by Ps2ν+δ(Fq).LetFq(2ν+δ) be the (2ν+δ)-dimensional row vector space over Fq. Ps2ν+δ(Fq) has an action on Fq(2ν+δ) defined as follows:
(4)Fq(2ν+δ)×Ps2ν+δ(Fq)⟶Fq(2ν+δ),((x1,x2,…,x2ν+δ),T)⟶(x1,x2,…,x2ν+δ)T.
The vector space Fq(2ν+δ) together with this group action is called the pseudosymplectic space over the finite field Fq of characteristic 2.LetP be an m-dimensional subspace of Fq(2ν+δ); then, PSδPt is cogredient to one of the following three normal forms:
(5)M(m,2s,s)=(0I(s)I(s)00(m-2s)),M(m,2s+1,s)=(0I(s)I(s)010(m-2s-1)),M(m,2s+2,s)=(0I(s)I(s)001110(m-2s-2)),
for some s such that 0≤s≤[m/2]. We say that P is a subspace of type (m,2s+τ,s,ϵ), where τ=0,1, or 2 and ϵ=0 or 1, if (i)
PSδPt is cogredient to M(m,2s+τ,s);(ii)
e2ν+1∉P or e2ν+1∈P according to ϵ=0 or ϵ=1, respectively.LetP be an m-dimensional subspace of Fq(2ν+δ). Denote by P⊥ the set of vectors which are orthogonal to every vector of P; that is,
(6)P⊥={y∈Fq(2ν+δ)∣ySδxt=0∀x∈P}.
Obviously, P⊥ is a (2ν+δ-m)-dimensional subspace of Fq(2ν+δ).More properties of pseudosymplectic geometry over finite fields can be found in [7].In [2], Desmedt et al. gave two constructions for MRA-codes based on polynomials and finite geometries, respectively. There are other constructions of multisender authentication codes which are given in [3–6]. The construction of authentication codes is of combinational design in its nature. We know that the geometry of classical groups over finite fields, including symplectic geometry, pseudosymplectic geometry, unitary geometry, and orthogonal geometry, can provide a better combination of structure and can be easy to count. In this paper, we construct one multisender authentication code from pseudosymplectic geometry over finite fields. The parameters and the probabilities of deceptions of this code are also computed. We realize the generalization and application of the similar idea and method of article [8] from symplectic geometry to pseudosymplectic geometry over finite fields.


## 3. Construction

Let𝔽q be a finite field with q elements and ei(1≤i≤2ν+2) the row vector in 𝔽q(2ν+2) whose ith coordinate is 1 and all other coordinates are 0. Assume that 2<n+1<r<ν. Let U=〈e1,e2,…,en〉; that is, U is an n-dimensional subspace of 𝔽q(2ν+2) generated by e1,e2,…,en, and then U⊥=〈e1,…,eν,eν+n+1,…,e2ν+2〉. Consider Wi=〈e1,…,ei-1,ei+1,…,en〉, 1≤i≤n; then, Wi⊥=〈e1,…,eν,eν+i,eν+n+1,…,e2ν+2〉. The set of source states S={s∣s  is  a  subspace  of  type (2r-n+1,2(r-n),r-n,1) and U⊂s⊂U⊥}; the set of ith sender's encoding rules EPi={ePi∣ePiisasubspaceoftype(n+1,0,0,0)andU⊂ePi,ePi⊥Wi}, 1≤i≤n; the set of receiver's decoding rules ER={eR∣eR is a subspace of type (2n,2n,n,0) andU⊂eR}; the set of ith sender's tags Ti={ti∣ti is  a  subspace of  type (2r-n+2,2(r-n+1),r-n+1,1) and U⊂ti⊂Wi⊥,ti⊄U⊥}; the set of receiver's tags T={t∣t  is  a  subspace  of  type  (2r+1,2r,r,1) and U⊂t}.Define the encoding mapfi:S×EPi→Ti,fi(s,ePi)=s+ePi, 1≤i≤n.The decoding mapf:S×ER→T,f(s,eR)=s+eR.The synthesizing maph:T1×T2×⋯×Tn→T,h(t1,t2,…,tn)=A(t1+t2+⋯+tn), where A is a nonsingular matrix and A(t1+t2+⋯+tn) is a subspace of type (2r+1,2r,r,1).The code works as follows.(1)Key Distribution. The key distribution center randomly chooses an eR∈ER and selects a (2n,n) subspace e such that U⊂e, and it selects ePi∈EPi so that eP1+eP2+⋯+ePn=e, and A is a nonsingular matrix satisfying eR=〈e,A〉. The key distribution center randomly secretly sends eR,ePi to the receiver and the senders, respectively, and sends A to the synthesizer.(2)Broadcast. If the senders want to send a source state s∈S to the receiver R, the sender Pi calculates ti=fi(s,ePi)=s+ePi then sends ti(1≤i≤n) to the synthesizer.(3)Synthesis. After the synthesizer receives t1,t2,…,tn, he calculates h=(t1,t2,…,tn)=A(t1+t2+⋯+tn) and then sends m=(s,t) to the receiver R.(4)Verification. When the receiver R receives m=(s,t), he calculates t′=g(s,eR)=s+eR. If t=t′, he accepts t; otherwise, he rejects it.Let(7)U=(I(l)00I(n-l)0000000000000000)ln-lν-nli-l-11n-iν-n11;then,(8)U⊥=(I(l)000000I(n-l)000000I(ν-n)000000000000000000000000000000I(ν-n)00000010000001)ln-lν-nli-l-11n-iν-n11,Wi⊥=(I(l)0000000I(n-l)0000000I(ν-n)000000000000000000000100000000000000I(ν-n)0000000100000001)ln-lν-nli-l-11n-iν-n11.Lemma 1.
LetCi=(S,EPi,Ti;fi); the code is a cartesian authentication code, 1≤i≤n.Proof.
For anyepi∈Epi,s∈S. Because epi is a subspace of type (n+1,0,0,0)  and U⊂epi⊂U⊥, we can assume that(9)epi=(I(l)000I(n-l)000000000000100000R800R9000)ln-lν-nli-l-11n-iν-n11.Obviously, epi∩U⊥=U. Let s∈S; since U⊂s⊂U⊥, s has the form as follows:
(10)s=(I(n)000000B20B400000010),
where B2,B4 is a subspace of type (2(r-n),2(r-n),r-n,0) in the pseudosymplectic space Fq(2ν+2). Let ti=s+epi; then,(11)ti=(I(l)00000I(n-l)00000B2000000000000000100000000B4R800000100000)ln-lν-nli-l-11n-iν-n11,tiS2tit~(I(r-n)0000I(r-n)0000100001).Obviously, ti⊄U⊥. So, ti is a subspace of type (2r-n+2,2(r-n+1),r-n+1,1) satisfying U⊂ti⊂Wi⊥; that is, ti∈Ti. Furthermore, we know that ti∩U⊥=(s+epi)∩U⊥=s+(epi∩U⊥)=s+U=s.
Conversely, for anyti∈Ti, let s=ti∩U⊥,L⊂ti, satisfying ti=s⊕L. Obviously, U⊂s⊂U⊥. For U⊂ti⊂Wi⊥, let(12)ti=(I(l)00000I(n-l)00000B2000000000000000100000000B4R800000100000)ln-lν-nli-l-11n-iν-n11.Obviously,(13)ti∩U⊥=(I(l)0000I(n-l)0000C20000000000000000000C4000010000)ln-lν-nli-l-11n-iν-n11.For ti being a subspace of type (2r-n+2,2(r-n+1),r-n+1,1), then ti∩U⊥ is a subspace of type (2r-n+1,2(r-n),r-n,1); that is, s∈S. Choose
(14)L=(00B20010B400).
Let ePi=U+L; then, ePi∈EPi, and s⊕L=s⊕ePi. Therefore, fi is a surjection. For any ti∈Ti,ePi∈EPi, if there exist s∈S so that ti=s+ePi; then, s∈ti∩U⊥. However, dims=2r-n+1=dim(ti∩U⊥), and so s=ti∩U⊥; that is, s is determined by ti and ePi.Lemma 2.
LetC=(S,ER,T;g); the code is a cartesian authentication code.Proof.
(1)  For anys∈S, eR∈ER. From the definition of s and eR, we assume that
(15)s=(UQe2ν+1)n2(r-n)1,(UQe2ν+1)S2(UQe2ν+1)t=(0(n)00000I(r-n)00I(r-n)000000),eR=(UV)nn,(UV)S2(UV)tS2(UV)t=(0I(n)I(n)0).
Obviously, for any v∈V and v≠0, v∉s; therefore,
(16)t=s+eR=(UVQe2ν+1),(17)(UVQe2ν+1)S2(UVQe2ν+1)t=(0I(n)000I(n)0000000I(r-n)000I(r-n)0000000).
From the above mentioned, t is a subspace of type (2r+1,2r,r,1) and U⊂t; that is, t∈T.
(2)   Fort∈T, t is a subspace of type (2r+1,2r,r,1) and U⊂t; so, there is a subspace V⊂t, satisfying
(18)(UV)S2(UV)t=(0I(n)I(n)0).
Then, we can assume that
(19)t=(UVQe2ν+1)
satisfying
(20)(UVQe2ν+1)S2(UVQe2ν+1)t=(0I(n)000I(n)0000000I(r-n)000I(r-n)0000000).
Let
(21)s=(UQe2ν+1),
for s  is  a  subspace  of  type  (2r-n+1,2(r-n),r-n,1)  and  U⊂s⊂U⊥; that is, s∈S is a source state. For any v∈V and v≠0, v∉s is obvious; that is, V∩U⊥={0}. Therefore, t∩U⊥=(UQe2ν+1)=s. Let eR=(UV); then, eR is receiver's decoding rule satisfying t=s+eR.
Ifs′ is another source state contained in t, then U⊂s′⊂U⊥. Therefore, s′⊂t∩U⊥=s, while dim s′=dims, and so s′=s; that is, s is the uniquely source state contained in t.
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 group of senders.Lemma 3.
Some parameters of this code are(22)|S|=N(2(r-n),2(r-n),r-n,0;2ν+2);|EPi|=qν-n+1(1≤i≤n).Proof.
SinceU⊂s⊂U⊥, s has the following form:
(23)s=(I(n)000000B20B400000010),
where B2,B4 is a subspace of type (2(r-n),2(r-n),r-n,0) in the pseudosymplectic space Fq(2ν+2). So, |S|=N(2(r-n),2(r-n),r-n,0;2ν+2).
For anyepi∈Epi, we can assume that ePi has the following form:(24)ePi=(I(l)000I(n-l)000R300000000100000R800R900R10)ln-lν-nli-l-11n-iν-n11.Since epi is a subspace of type (n+1,0,0,0), so R3=0 and R10=0, R8,R9 arbitrarily. Therefore, |EPi|=qν-n+1.Lemma 4.
(1) For anyti∈Ti, the number of ti containing ePi is qr-n+1(1≤i≤n);
(2) The number of theith sender's tag is |Ti|=qν-rN(2(r-n),2(r-n),r-n,0;2ν+2)(1≤i≤n).Proof.
(1)  Considering the transitivity properties of the same subspaces under the pseudosymplectic groups, we may taketi as follows:(25)ti=(I(l)000000I(n-l)000000I(r-n)0000000000000000000000001000000000000I(r-n)0000000000001000000)ln-lr-nν-rli-l-11n-ir-nν-r11.If ePi⊂ti, then we assume that(26)ePi=(I(l)000I(n-l)000000000000000R700000R900000R11000)ln-lr-nν-rli-l-11n-ir-nν-r11;from ePi⊥Wi, we know that R7=1, where R9,R11 arbitrarily, and therefore the number of ti containing ePi is qr-n+1 (1≤i≤n).
(2)  We know that everyti contains only one source state ti∩U⊥and the number of ti containing ePi. Therefore, we have |ti|=|S||EPi|/qr-n+1=|S|qν-n+1/qr-n+1=qν-rN(2(r-n),2(r-n),r-n,0;2ν+2).Lemma 5.
(1) The number of the receiver's decoding rules is|ER|=qn(ν-n+1).
(2)  For anyt∈T, the number of eR which contained t is qn(r-n+1)(1≤i≤n).
(3) The number of the receiver's tag is|T|=qn(ν-r)N(2(r-n),2(r-n),r-n,0;2ν+2).Proof.
(1) LeteR∈ER; eR has the following form:(27)eR=(I(n)00R20I(n)0R40R50R6)nν-nnν-n11.For eR being a subspace of type (2n,2n,n,0), so R2 and R6=0;R4,R5 arbitrarily. Therefore,|ER|=qn(ν-n+1).
(2)  Considering the transitivity properties of the same subspaces under the pseudosymplectic groups, we may chooset as follows:(28)t=(I(n)00000I(r-n)0000000000I(n)00000I(r-n)0000000000100000)nr-nν-rnr-nν-r11.If eR⊂t, then(29)eR=(I(n)000000I(n)0R5000R700)nr-nν-rnr-nν-r11,where R5 and R7 arbitrarily. Therefore, the number of eR which contained t is qn(r-n+1).
(3) Similar to Lemma4(2), |T|=|S||ER|/qr-n+1=|S|qn(ν-n+1)/qr-n+1=qn(ν-r)N(2(r-n), 2(r-n), r-n,0; 2ν+2).
Without loss of generality, we assume thatL={i1,i2,…,il}⊂{1,2,…,n},l<n, PL={p1,p2,…,pl}, and EL={Ep1,Ep2,…,Epl}. Now, let us consider the attacks on R from malicious groups of senders.Lemma 6.
For anyeL={Ep1,Ep2,…,Epl}∈EL, the number of eR containing eL is q(ν-n+1)(n-l).Proof.
For anyeL={Ep1,Ep2,…,Epl}∈EL, we assume eL to be as follows:(30)eL=(I(l)000I(n-l)000000I(l)00000R600R7000)ln-lν-nln-lν-n11.If eR⊃eL, then eR has the following form:(31)eR=(I(l)0000I(n-l)00000000I(l)0000I(n-l)00R6R6′00R7R7′0000)ln-lν-nln-lν-n11,where R6′,R7′ arbitrarily. Therefore, the number of eR containing eL is q(ν-n+1)(n-l).Lemma 7.
For anyt∈T and eL={Ep1,Ep2,…,Epl}∈EL, the number of eRwhich contained in t and containing eL is q(r-n+1)(n-l).Proof.
For anyt∈T, we assume t to be as follows:(32)t=(I(l)0000000I(n-l)0000000I(r-n)00000000000000I(l)0000000I(n-l)0000000I(r-n)0000000000000010000000)ln-lr-nν-rln-lr-nν-r11.If eL⊂t, then eL has the following form:(33)eL=(I(l)000I(n-l)000000000I(l)00000R700000R9000)ln-lr-nν-rln-lr-nν-r11.Since eL⊂eR⊂t, then we assume eR to be as follows:(34)eR=(I(l)00000I(n-l)0000000000000000I(l)00000I(n-l)000R7H700000000R9H900000)ln-lr-nν-rln-lr-nν-r11,where H7 and H9 arbitrarily. Therefore, the number of eRwhich contained in t and containing eL is q(r-n+1)(n-l).Lemma 8.
Assume thatt1 and t2 are two distinct tags (t1,t2∈T) decoded by receiver's key eR, and s1 and s2 contained in t1 and t2 are two source states, respectively. Let s0=s1∩s2, dims0=k; then, n≤k≤2r-n, and the number of eR which contained in t1∩t2 and containing eL is q(k-r)(n-1).Proof.
Sincet1=s1+eR,t2=s2+eR, and t1≠t2, then s1≠s2. For any s∈S, U∈s, obviously n≤k≤2r-n. Assume that si′ is the complementary subspace of s0 in the si; then, si=s0+si′(i=1,2). From ti=si+eR=s0+si′+eR and si=ti∩U⊥, we know that s0=(t1∩U⊥)∩(t2∩U⊥)=t1∩t2∩U⊥=s1∩t2=s2∩t1, and t1∩t2=(s1+eR)∩t2=(s0+s1′+eR)∩t2=((s0+eR)+s1′)∩t2, since s0+eR⊆t2; then, t1∩t2=(s0+eR)+(s1′∩t2), while s1′∩t2⊆s1∩t2=s0, and so we have t1∩t2=s0+eR.
From the definition oft, we may take ti,i=1,2, as follows:(35)ti=(I(l)0000000I(n-l)0000000I(r-n)00000000000000I(l)0000000I(n-l)0000000Pi70000000000000010000000)ln-lr-nln-lr-n1ln-lr-nν-rln-lr-nν-r11.Let(36)t1∩t2=(I(l)0000000I(n-l)0000000I(r-n)00000000000000I(l)0000000I(n-l)0000000P70000000000000010000000)ln-lr-nln-lr-n1ln-lr-nν-rln-lr-nν-r11.From the above mentioned, we know that t1∩t2=s0+eR, and then dim(t1∩t2)=k+2n-n=k+n; therefore,(37)dim(0P700000010)=k+n-(2n+r-n)=k-r.For any eL,eR⊂t1∩t2, we can assume that(38)eL=(I(l)000I(n-l)000000000I(l)00000R700000R9000)ln-llln-lr-nν-rln-lr-nν-r11,eR=(I(l)0000I(n-l)000000000000I(l)0000I(n-l)00R7H7000000R9H90000)ln-lln-lln-lr-nν-rln-lr-nν-r11,where every row of
(39)(0H70H90)
is the linear combination of the base of
(40)(0P700000010).
Therefore, the number of eR⊂t1∩t2and containing eL is q(k-r)(n-l).Theorem 9.
In the constructed multisender authentication codes, the largest probabilities of success forimpersonation attack and substitution  attack from PL on a receiver R are
(41)PI(L)=1q(ν-r)(n-l),PS(L)=1q2(n-l),
respectively.Proof.
Impersonation  Attack. PL, after receiving his secret keys, encodes a message and sends it to receiver. PL is successful if the receiver accepts it as legitimate message. So,
(42)PI(L)=maxeL∈ELmaxm∈M{|{eR∈ER∣eL⊂eRandeR⊂t}||{eR∈ER∣eL⊂eR}|}=q(n-l)(r-n+1)q(n-l)(ν-n+1)=1q(ν-r)(n-l).Substitution  Attack. PL replaces t with another message t′, after it observes a legitimate message t. PL is successful if the receiver accepts it as legitimate message. So,
(43)PS(L)=maxeL∈ELmaxm∈Mmaxm′≠m∈M{|{eR∈ER∣eR⊂t,t′andeL⊂eR}||{eR∈ER∣eR⊂tandeL⊂eR}|}=maxn≤k≤2r-nq(n-l)(k-r)q(n-l)(r-n+1)=maxn≤k≤2r-n1q(2r-n+1-k)(n-l)=1q(n-l).



---

*Source: 602539-2013-06-04.xml*