# Some New Constructions of Authentication Codes with Arbitration and Multi-Receiver from Singular Symplectic Geometry

Authors: You Gao; Huafeng Yu
Journal: Journal of Applied Mathematics
 (2011)

---

## Abstract

A new construction of authentication codes with arbitration and multireceiver from singular symplectic geometry over finite fields is given. The parameters are computed. Assuming that the encoding rules are chosen according to a uniform probability distribution, the probabilities of success for different types of deception are also computed.


---

## Body

## 1. Introduction

LetS,ET,ER, and M be four nonempty finite sets, and let f:S×ET→M and g:M×ER→S∪{reject}be two maps. The six-tuple (S,ET,ER,M,f,g) is called an authentication code with arbitration (A2-code) if(1)
the mapsf and g are surjective;(2)
for anym∈M and eT∈ET, if there is a s∈S, satisfying f(s,eT)=m, then such an s is uniquely determined by the given m and eT;(3)
p(eT,eR)≠0 and f(s,eT)=m implies g(m,eR)=s, otherwise, g(m,eR)={reject}.S,ET,ER, and M are called the set of source states, the set of transmitter’s encoding rules, the set of receiver’s decoding rules, and the set of messages, respectively; f and g are called the encoding map and decoding map, respectively. The cardinals |S|,|ET|,|ER|, and |M| are called the size parameters of the code.In [1], Simmons introduced the A2-code model to solve the transmitter and the receiver’s distrust problem. In [2–4], some Cartesian authentication codes were constructed from symplectic and unitary geometry; in [5–7], authentication codes with arbitration based on symplectic and pseudosymplectic geometry were constructed.The following notations will be fixed throughout this paper:p is a fixed prime. Fq is a field with q elements. V=Fq(2ν+l) is a singular symplectic space over Fq with index ν. ei(1≤i≤2ν+l) is row vector in V whose ith coordinate is 1 and all other coordinates are 0. Denote by E the l-dimensional subspace of V generated by e2ν+1,e2ν+2,…,e2ν+l. Kl denotes the matrix(1.1)(0I(ν)0-I(ν)00000(l)).
For more concepts and notations used in this paper, refer to [8].In an authentication system that permits arbitration, the model includes four attendance: the transmitter, the receiver, the opponent, and the arbiter and includes five attacks.(1)
The opponent’s impersonation attack: the largest probability of an opponent’s successful impersonation attack isPI. Then,(1.2)PI=max⁡m∈M{|eR∈ER∣eR⊂m||ER|}.(2)
The opponent’s substitution attack: the largest probability of an opponent’s successful substitution attack isPS. Then,(1.3)PS=max⁡m∈M{max⁡m≠m′∈M|eR∈ER∣eR⊂m,eR⊂m′||eR∈ER∣eR⊂m|}.(3)
The transmitter’s impersonation attack: the largest probability of a transmitter’s successful impersonation attack isPT. Then,(1.4)PT=max⁡eT∈ET{max⁡m∈M,eT∉m|{eR∈ER∣eR⊂m,p(eR,eT)≠0}||{eR∈ER∣p(eR,eT)≠0}|}.(4)
The receiver’s impersonation attack: the largest probability of a receiver’s successful impersonation attack isPR0. Then,(1.5)PR0=max⁡eR∈ER{max⁡m∈M|{eT∈ET∣eT⊂m,p(eR,eT)≠0}||{eT∈ET∣p(eR,eT)≠0}|}.(5)
The receiver’s substitution attack: the largest probability of a receiver’s successful substitution attack isPR1. Then,(1.6)PR1=max⁡eR∈ER,m∈M{max⁡m′∈M|{eT∈ET∣eT⊂m,m′,p(eR,eT)≠0}||{eT∈ET∣p(eR,eT)≠0}|}.Notes
p(eR,eT)≠0 implies that any source s encoded by eT can be authenticated by eR.


## 2. The First Construction

In this section, we will construct an authentication code with arbitration from singular symplectic geometry over finite fields.Assume that2s≤2s0<m0≤ν+m0, m0<2ν-1 and 1≤k<l. Let P be a subspace 〈v1,v2,e2ν+1〉 of type (3,0,1) in Fq(2ν+1), and let P0 be a fixed subspace of type (m0+l,s0,l) which contains P and orthogonal to v2, but not orthogonal to v1.Our authentication code is a six-tuple(2.1)(S,ET,ER,M;f,g),
where the set of source states(2.2)S={s∣sisasubspaceoftype(2s+1+k,s,k),p⊂s⊂P0},
the set of transmitter’s encoding rules:(2.3)ET={eT∣eTisasubspaceoftype(5,2,1),eT∩P0=P},
the set of receiver’s decoding rules:(2.4)ER={eR∣eRisasubspaceoftype(2,1,0),eR∩P0=〈v2〉},
the set of messages:(2.5)M={m⊥m∣misasubspaceoftype(2s+3+k,s+1,k),P⊂m,v2∉m⊥,m∩P0isasubspaceoftype(2s+1+k,s,k)},
the encoding function:(2.6)f:S×ET⟶M,(s,eT)⟼m=s+eT
and the decoding function: g:M×ER→S∪{reject},(2.7)(m,eR)⟼{sifeR⊂m,wheres=m∩P0,{reject}ifeR⊄m.Assuming that the transmitter’s encoding rules and the receiver’s decoding rules are chosen according to a uniform probability distribution, we can prove that the construction given above results in anA2-code.Lemma 2.1.
The six-tuple(S,ET,ER,M,f,g) is an authentication code with arbitration; that is (1)
s+eT=m∈M, for all s∈S and eT∈ET;(2)
for anym∈M, s=m∩P0 is uniquely information source contained in m and there is eT∈ET, such that m=s+eT.Proof.
(1) Lets be a source state, that is, a subspace Q of type (2s+1+k,s,k) containing p and contained in p0. Write Ek,Q as
(2.8)Ek=(e2v+1e2v+i2⋮2v+ik),Q=(Q0v1v2Ek),
which satisfies
(2.9)QKlQT=(00-I(s-1)I(s-1)00-11000).s-1s-1111k
LeteT be a transmitter’s rule, that is, a subspace R of type (5,2,1) containing P and R∩P0=P. So, there exists u1,u2∈R, such that R=〈v1,v2,u1,u2,e2ν+1〉 and(2.10)QKlQT=(00-I(s-1)I(s-1)00-10**100-100000-1*1000*01000).s-1s-111111k
Therefore, M=Q+〈u1,u2〉 is a subspace of type (2s+3+k,s+1,k) which contains P and M∩P0=Q is a subspace of type (2s+1+k,s,k), and is not orthogonal to v2, hence a message.
(2) Now, letm be a message; that is, m is a subspace M of type (2s+3+k,s+1,k) which contains P and intersects P0 at a subspace of type (2s+1+k,s,k), and is not orthogonal to v2. By definition, P0 contains 〈v1,v2,e2ν+1〉, so P⊂M∩P0=Q, so Q is a source state. Since M≠P0, there exists u1,u2∈M but u1,u2∉P0 such that M=Q+〈u1,u2〉. We have to show that there exists u1,u2∈M such that R=〈v1,v2,u1,u2,e2ν+1〉 is a subspace of type (5,2,1), hence a transmitter’s encoding rule.
Assume thatR=〈v1,v2,u1,u2,e2ν+1〉 has been set; if R is a subspace of type (5,2,1), then we are done. So, suppose that R is not a subspace of type (5,2,1). Since v2∈Q⊥ and v2∉M⊥, we must have that v2Klu1T≠0 or v2Klu2T≠0. Without loss of generality, let v2Klu2T=1. If we also have v2Klu1T=1, replacing u1 by u1-u2, we get v2Klu2T=1 and v2Klu1T=0. Since R is not a subspace of type (5,2,1), certainly v1Klu1T=0. Note that Q is a subspace of type (2s+1+k,s,k), v1∉Q⊥, so there exists a vector w∈Q such that v1KlwT=1. Replacing u1 by w+u1, we have v1Klu1T=1, v2Klu1T=0(v2∈Q⊥). Then, R=〈v1,v2,u1,u2,e2ν+1〉 is a subspace of type (5,2,1), and M=Q+R, hence R is a transmitter's encoding rule.
If there is another source stateQ′ such that M=Q′+R′, we have that Q′⊂M∩P0=Q. by Q′⊂M,Q′⊂P0. Since dimQ′=dimQ=2s+1+k, so Q′=Q. This implies that the source state Q is uniquely determined by M.Letn1 denote the number of subspaces of type (2s+1+k,s,k) contained in 〈v2〉⊥ and containing P, n2, the number of subspaces of type (m0+l,s0,l) contained in 〈v2〉⊥ and containing a fixed subspace of type (2s+1+k,s,k) as above, and n3, the number of subspaces of type (m0+l,s0,l) contained in 〈v2〉⊥ and containing P and not contained in 〈v1〉⊥.Lemma 2.2.
One has(2.11)n1=q2(ν-s-1)⋅q(2s-1)(l-k)⋅N(2(s-1),s-1;2(ν-2))⋅N(k-1,l-1),n2=N(m0-(2s+1),s0-s;2(ν-s-1)),n3=q2(ν-s-1)⋅q(2ν-m0-1)⋅N(m0-3,s0-1;2(ν-2)).Proof.
(1) Computation ofn1.
By the transitivity ofSp2v+l(Fq) on the set of subspaces of the same type, we can assume that
(2.12)(v1v2)=(10010000000000).11v-211v-2l
LetQ be a subspace of type (2s+1+k,s,k) contained in 〈v2〉⊥ and containing P. There exists a u∈Q such that v1KluT=1. We may assume that u=(0,0,R1,1,0,R2,0,0,R3). So, Q has a matrix representation of the form(2.13)Q=(10000001000000R1Q10000100000000000R2Q20000001000000I(k-1)00R3Q300)11v-211v-21k-1l-k1112s-21k-1.
It is easy to verify thatQ1,Q2 is a subspace of type (2(s-1),s-1) in the 2(v-2)-dimensional symplectic space. The number of this kind of subspace is denoted by N(2(s-1),s-1;2(ν-2)), Q3 arbitrarily. Furthermore, we may take (Q1,Q2,Q3) as(2.14)(I(s-1)0000I(s-1)0000)s-1bs-1bl-k
to compute n1, where b=(ν-2)-(s-1). Since Q has a matrix representation of the form
(2.15)Q=(10000000100000000I(s-1)00000a40000001000000000000000I(s-1)0000b400000000010000000I(k-1)00c30000),11ab11ab1k-1l-k
where a=s-1andb=ν-s-1, we have that
(2.16)n1=q2(ν-s-1)⋅q(2s-1)(l-k)⋅N(2(s-1),s-1;2(ν-2))⋅N(k-1,l-1).(2) Computation ofn2.
LetU be a subspaces of type (m0+l,s0,l) contained in 〈v2〉⊥ and containing a fixed subspace of type (2s+1+k,s,k) which contains P, similar to (1), we may assume that U has a matrix representation of the form(2.17)U=(10000000100000000I(s-1)00000000P10001000000000000000I(s-1)0000000P20000000I(l)),11ab11abl
where a=s-1,b=ν-s-1, so (P1,P2) is a subspace of type (m0-(2s+1),s0-s) in the 2(v-s-1)-dimensional symplectic space. We have that
(2.18)n2=N(m0-(2s+1),s0-s;2(ν-s-1)).(3) Computation ofn3.
By the same method as that of (1) and (2), letU0 be a subspaces of type (m0+l,s0,l) contained in 〈v2〉⊥, containing P and not contained in 〈v1〉⊥. We may assume that the subspace has a matrix representation of the form(2.19)U0=(100000100000A1Q10001000000000A2Q200000I(l)).11v-211v-2l
So, the number of the subspaces(Q1,Q2) is denoted by N(m0-3,s0-1;2(ν-2)). Then, by the transitivity of Sp2ν+l(Fq) on the set of subspaces of the same type, we can assume that(2.20)U0=(10000000100000000I(s0-1)00000000I(a)000a50000001000000000000000I(s0-1)0000b4000000b50000000000I(l)),11cab11cabl
where c=s0-1,a=m0-2s0-1,b=ν-m0+s0,a5,b4,b5 arbitrarily. We may get
(2.21)n3=q2(ν-s-1)⋅q(2ν-m0-1)⋅N(m0-3,s0-1;2(ν-2)).Lemma 2.3.
The number of the source states is(2.22)|S|=q(m0-2s-1)+(2s-1)(l-k)⋅N(2(s-1),s-1;2(ν-2))⋅N(m0-(2s+1),s0-s;2(ν-s-1))⋅N(k-1,l-1)N(m0-3,s0-1;2(ν-2)).Proof.
Since|S| is the number of subspaces of type (2s+1+k,s,k) contained in P0 and containing P, we have |S|·n3=n1·n2.Lemma 2.4.
The number of the encoding rules of transmitter is(2.23)|ET|=q(m0-3)+2(ν-2)+2(l-1)⋅(q2ν-m0-1-1).Proof.
Since|ET| is the number of subspaces of type (5,2,1) contained in P0 and containing P, let R=〈v1,v2,u1,u2,e2ν+1〉, where v1Klu1T=1,v2Klu2T=1, and 〈v1,u1〉⊥〈v2,u2〉. By the transitivity of Sp2ν+1(Fq) on the set of subspaces of the same type, we can assume that
(2.24)v1=(1,0,0,0,0,0,0,0,0,0,0,0),v2=(0,1,0,0,0,0,0,0,0,0,0,0),e2ν+1=(0,0,0,0,0,0,0,0,0,0,1,0),P0=(10000000100000000I(s0-1)00000000I(a)00000000001000000000000000I(s0-1)0000000000000000000000I(l)),11cab11cabl
where c=s0-1,a=m0-2s0-1,andb=ν-m0+s0. Therefore, u1 and u2 have the respective forms:
(2.25)u1=(0,0,a3,a4,a5,1,0,b3,b4,b5,0,f2),u2=(0,0,c3,c4,c5,0,1,d3,d4,d5,0,g2).
Note that u2∉P0 and dim(R∩p0)=3, so the vector u1 cannot lie in P0. Then, a5,b4,b5 cannot equal zero at the same time. Thus, the number of u1 is q(m0-3)+(l-1)(q2ν-m0-1-1) and that for u2 is q2(ν-2)+(l-1); we may get
(2.26)|ET|=q(m0-3)+2(ν-2)+2(l-1)⋅(q2ν-m0-1-1).Lemma 2.5.
The number of the encoding rules of receiver is(2.27)|ER|=q2ν-2⋅ql.Proof.
|ER| is the number of type (2,1,0) intersecting P0 at 〈v2〉. Let H=〈v2,u〉, where v2KluT=1. Following the notion of Lemma 2.4, hence u has the form
(2.28)u=(a1,0,a3,a4,a5,b1,1,b3,b4,b5,c1).
Clearly, u∉P0. The number of u is q2ν-2·ql, that is,
(2.29)|ER|=q2ν-2⋅ql.Lemma 2.6.
For anym∈M, let the number of  eT and  eR contained in  m be  a and  b, respectively. Then,
(2.30)a=q4s-3+2(k-1)⋅(q-1),b=q2s+1⋅qk.Proof.
LetM be a message, and Q=M∩P0, then Q is a source state contained in M. By Lemma 2.1, we may get a transmitter’s encoding rule R contained in M. Let R=〈v1,v2,u1,u2,e2ν+1〉. Here, M=Q+〈u1,u2〉,v2Klu2T=1. Following the notation of Lemma 2.4, we can assume that Q has a matrix representation of the form
(2.31)Q=(10000000100000000I(s-1)000000000000000000000000001000000000000000I(s-1)000000000000000000000000000010000000I(k-1)0000000),11dcab11dcab1k-1l-k
where a=m0-2s0-1,b=ν+s0-m,c=s0-s,andd=s-1. By v2Klu2T=1 and R being the subspace of type (5,2,1), we can assume
(2.32)u1=(0,0,a3,a4,a5,a6,b1,0,b3,b4,b5,b6,0,f2,f3),u2=(0,0,c3,c4,c5,c6,d1,1,d3,d4,d5,d6,0,g2,g3),
where b1≠0. Then,
(2.33)M=(100000000010000000000I(s-1)000a3c30000000a4c40000000a5c50000000a6c60010000b1d10000000010000I(s-1)00b3d30000000b4d40000000b5d50000000b6d6000001000000000I(k-1)f2g20000000f3g3),11dcab11dcab1k-1l-k
where a=m0-2s0-1,b=ν+s0-m,c=s0-s,andd=s-1.(1)
Note thatM is fixed, so, for u1, the a4,a5,a6,b4,b5,b6, and f3 are fixed and, for u2, the c4,c5,c6,d4,d5,d6, and g3 are fixed. Therefore, the number of u1 is q2(s-1)+(k-1)·(q-1) and the number of u2 is q2(s-1)+(k-1)+1. Then, the number of eT contained in m is
(2.34)a=q4s-3+2(k-1)⋅(q-1).(2)
LetH=〈v2,u〉 be a receiver’s encoding rule contained in M, where v2KluT=1. Clearly, u∉Q, then we can assume that u has the form
(2.35)u=(h1,0,h3,h4,h5,h6,i1,1,i3,i4,i5,i6,j1,j2,j3). Note that
(2.36)(h4,h5,h6,i4,i5,i6,j3)=k(a4,a5,a6,b4,b5,b6,f3)+(c4,c5,c6,d4,d5,d6,g3),
where k∈Fq. Therefore, the number of (h4,h5,h6,i4,i5,i6,j3) is q. Then, the number of eR contained in m is
(2.37)b=q⋅q2⋅q2(s-1)⋅qk=q2s+1+k.Lemma 2.7.
The number of the messages is(2.38)|M|=|S||ET|q4s-k+2(k-1)(q-1).Proof.
For anym∈M, there is uniquely s∈S and eT∈ET satisfying m=s+eT; the number of eT is a. Thus,
(2.39)|M|=|S||ET|a=|S||ET|q4s-k+2(k-1)(q-1).Lemma 2.8.
(1) For anyeT∈ET, the number of  eR contained in  eT is  q3.
(2) For anyeR∈ER, the number of eT containing eR is (q2ν-4-qm0-3)·ql-1.Proof.
(1) LetR be a transmitter’s encoding rule; we can assume that R=〈v1,v2,u1,u2,e2ν+1〉. Here, v2Klu2T=1,v1Klu1T=1, and 〈v1,u1〉⊥〈v2,u2〉. Then, the receiver’s encoding rule H contained in R should have the form H=〈v2,k1v1+k2u1+u2+k3e2ν+1〉, where k1,k2,k3∈Fq. So, the number of H is q3.
(2) LetH be a receiver’s encoding rule, and H=〈v2,u〉, where v2KluT=1. Therefore, 〈v1,v2,u,e2ν+1〉 is a subspace of type (4,1,1). The number of subspace 〈v1,v2,u,u1,e2ν+1〉 of type (5,2,1) is q2ν-4·ql-1. Here, v1Klu1T≠0. Note that v2∈P0⊥ and v1∉p0⊥. It is easy to see that the number of u1∈P0 such that 〈v1,v2,u1,e2ν+1〉 is a subspace of type (4,1,1) is qm0-3·ql-1. So, the number of transmitter’s encoding rules eT containing H is (q2ν-4-qm0-3)·ql-1.Lemma 2.9.
For anym∈M and  eR⊂m, the number of  eT contained in  m and containing  eR is
(2.40)q2(s-1)+(k-1)⋅(q-1).Proof.
LetM be a message, and let H=〈v2,u〉 be a receiver’s encoding rule contained in M; we can assume that u=(0,0,0,0,0,1,0,0,0,0,0,0), and M has a matrix representation of the form
(2.41)M=(100000000010000000000I(s-1)0a300000000a400000100b10000000001000000I(s-1)b300000000b400000000001000000f200I(k-1)00000f3000),11ab11ab1k-1l-k
where b1≠0,a=s-1,andb=ν-s-1.
Note thatM is fixed, so a4,b4,f3 are fixed. Assume that R is a transmitter’s encoding rule contained in M and containing H. Let R=〈v1,v2,u,u1,e2ν+1〉, where v1Klu1T≠0. Thus, u1 has the form
(2.42)u1=(0,0,c3,c4,d1,0,d3,d4,0,g2,g3),
where d1≠0. Note that (c4,d4,g3)=k(a4,b4,f3) and u1∉P0, so k≠0. Hence, u1, c4,d4, and g3 are fixed. Then, the number of u1 is q2(s-1)+(k-1)·(q-1); that is, the number of R is q2(s-1)+(k-1)·(q-1).Lemma 2.10.
Assume thatm1 and  m2 are two distinct messages which commonly contain a transmitter’s encoding rule  eT′.  s1 and  s2 contained in  m1 and  m2 are two source states, respectively. Assume that  s0=s1⋂s2,  dims0=k1,  then 3≤k1≤2s+k,  and(1)
the number ofeR contained in m1⋂m2 isqk1;(2)
for anyeR⊂m1⋂m2, the number of eT containingeR is qk1-4.Proof.
Sincem1=s1+eT′, m2=s2+eT′, and m1≠m2, then s1≠s2. Again because of s1⊃P0 and s2⊃P0, 3≤k1≤2s+k. From mi=si+eT′=s0+si′+eT′, it is easy to know that m1⋂m2=s0+eT′. Therefore,
(2.43)dim⁡(m1⋂m2)=dim⁡s0+dim⁡eT′-dim⁡(s0⋂eT′)=k1+5-3=k1+2.(1)
By the definition of the message, we can assume thatm1 and m2 have the form as follows, respectively:(2.44)m1=(10000000100000000A1a3b3000100b400000100000A2a6b60000000A3)11v-211v-2l1112(s-1)11l,
where b4≠0,
(2.45)m2=(10000000100000000B1c3d3000100d400000100000B2c6d60000000B3)11v-211v-2l1112(s-1)11l,
where d4≠0. Thus,
(2.46)m1⋂m2=(10000000100000000D1f3g3000100g400000100000D2f6g60000000D3)11v-211v-2l1112(s-1)11l,
where g4≠0. Since dim(m1∩m2)=k1+2, therefore
(2.47)dim⁡(00D100D2000f301f6000g3g40g60000000D3)=k1+2-3=k1-1.
If eR⊂m1∩m2, then
(2.48)eR=(0R1100R30R4010R60R7).11v-211v-2l
SinceR1,R4 are arbitrary, every row of (00R301R6R7) is the linear combination of the base
(2.49)(00D100D2000f301f6000g3g40g60000000D3),
thus the number of it is qk1-2. So, it is easy to know that the number of eR contained in m1⋂m2 is
(2.50)qk1-2⋅q2=qk1.
(2)
Assume thatm1⋂m2 has the form of (2.46), then, for any eR⊂m1⋂m2, we can assume that
(2.51)eR=(0R1100R30R4010R60R7).11v-211v-2l If eR⊂eT and eT⊂m1⋂m2, then
(2.52)eT=(100000100000R3R3′000R4100010000R6R6′00000100R7R7′0)11111,11v-211v-21l-1
where
(2.53)(00R3′00R6′0R7′00000010)
is the linear combination on the basis of
(2.54)(00D100D2000f301f6000g3g40g60000000D3),
then the number of eT containing eR is qk1-4.Theorem 2.11.
The above construction yields anA2-code with the following size parameters:
(2.55)|S|=q(m0-2s-1)+(2s-1)(l-k)⋅N(2(s-1),s-1;2(ν-2))⋅N(m0-(2s+1),s0-s;2(ν-s-1))⋅N(k-1,l-1)N(m0-3,s0-1;2(ν-2)),|ET|=q(m0-3)+2(ν-2)+2(l-1)⋅(q2ν-m0-1-1),|ER|=q2ν-2+l,|M|=|S||ET|q4s-3+2(k-1)⋅(q-1).
Moreover, assume that the encoding rules eT and eR are chosen according to a uniform probability distribution, the largest probabilities of success for different types of deceptions:
(2.56)PI=1q2ν-2s-3⋅ql-k,PS=1q,PT=1q2;PR0=q-1qm0-2s-1⋅ql-k(q2ν-m0-1-1),PR1=1q⋅(q-1).Proof.
(1) The number ofm containing eR is b,then(2.57)PI=q2s+1⋅qkq2ν-2⋅ql=1q2ν-2s-3⋅ql-k.(2)
Assume that opponent getsm1, which is from transmitter, and sends m2 instead of m1, when s1 contained in m1 is different from s2 contained in m2; the opponent’s substitution attack can be successful. Because eR⊂eT⊂m1, the opponent selects eT′⊂m1 satisfying m2=s2+eT′ and dim(s1⋂s2)=k1, then(2.58)PS=qk1q2s+1⋅qk=1q,
where k1=2s+k.(3)
Assume thatR is transmitter’s encoding rules, Q is a source state, and M=R+Q. Therefore, the number of receiver’s encoding rules contained in R is q3. Let M′ be another message, such that M′=R′+Q and R≠R′. Then, eR contained R⋂M′ is at most q. So,(2.59)PT=qq3=1q2.(4)
From Lemmas2.8 and 2.9, thus(2.60)PR0=q2(s-1)⋅(q-1)⋅qk-1(q2ν-4-qm0-3)⋅ql-1=q-1qm0-2s-1⋅ql-k(q2ν-m0-1-1).(5)
Assume that the receiver declares to receive a messagem2 instead of m1,when s2 contained in m1 is different from s2 contained in m2; the receiver’s substitution attack can be successful. Since eR⊂eT⊂m1, receiver is superior to select eT′, satisfying eR⊂eT′⊂m1, thus m2=s2+eT′, and dim(s1∩s2)=k1 as large as possible. Therefore, the probability of a receiver’s successful substitution attack is(2.61)PR1=qk1-4q2(s-1)+(k-1)⋅(q-1)=1q(q-1),
where k1=2s+k.


## 3. The Second Construction

In this section, from singular symplectic geometry and the first construction, we construct an authentication code with a transmitter and multi-receivers and compute the probabilities of success for different types of deceptions. For the definition of multi-receiver authentication codes, refer to [9].Let2s≤2s0<m0≤ν+m0, m0<2ν-1, and 1≤k<l. Let p be a subspace 〈v1,v2,e2ν+1〉 of type (3,0,1) in Fq(2ν+l), and let P0 be a fixed subspace of type (m0+l,s0,l) which contains P and orthogonal to v2, but not orthogonal to v1. Let S={s∣sisasubspaceoftype(2s+1+k,s,k),P⊂s⊂P0}, Let E={e∣eisasubspaceoftype(5,2,1),eT⋂P0=P}, Let M={m∣misasubspaceoftype(2s+3+k,s+1,k),P⊂m,v2∉m⊥,m⋂P0isasubspaceoftype(2s+1+k,s,k)}, and let M*={(m1,m2,…,mλ)|m1⋂U⊥=m2⋂U⊥=…=mλ⋂U⊥}.First, we construct(λ+1)A-codes. Let C=(S,Eλ,M*,f), where S,Eλ,andM* are the sets of source states, keys, and authenticators of C, respectively, and f:S×Eλ→M*,f(s,e)=(s+e1,s+e2,…,s+eλ) for e=(e1,e2,…,eλ)∈Eλ is the authentication mapping of C. Let Ci=(S,Ei,Mi;fi), where S,Ei=E and Mi=M are the sets of source states, keys, and authenticators of Ci, respectively, and fi:S×Ei→Mi,fi(s,ei)=s+ei for ei∈Ei, is the authentication mapping of Ci. It is easy to know that C and Ci are well-defined A-codes.Our authentication scheme is a(λ+1)-tupleC;C1,C2,…,Cλ. Let τi:Eλ→Ei,τi(e)=ei for e=(e1,e2,…,eλ)∈Eλ, and let πi:M*→Mi,πi(m)=mi for m=(m1,m2,…,mλ). Then,(3.1)πi(f(s,e))=π(s+e1,s+e2,…,s+eλ)=s+ei,fi((Is×τi)(s,e))=fi(Is(s),τi(e))=fi(s,ei)=s+ei.Therefore,πi(f(s,e))=fi((Is×πi)(s,e)). Thus, our scheme is indeed a well-defined authentication code with a transmitter and multi-receivers.Theorem 3.1.
In the construction of multi-receiver authentication codes, if the encoding rules are chosen according to a uniform probability distribution, then the probabilities of impersonation attack and substitution attack are, respectively,(3.2)PI[i,J]=1qm0+2ν+2l-4s-2k-4⋅(q2ν-m0-1-1),PS[i,J]=1qm0+2ν+2l-2s-k-5⋅(q2ν-m0-1-1),
where J={i1,i2,…,ij},i∉J.Proof.
LeteJ=(ei1,ei2,…,eij), then
(3.3)τJ(e)=eJ⟺e=(…,ei1,…,eij,…).
It is easy to know that |e∈Eλ∣τJ(e)=eJ|=|E|λ-j, and
(3.4)fi(s,ei)=πi(m),s+ei=mi=πi(m).
From Lemma 2.6, we know that the number of ei satisfying (3.4) is a. For any ei satisfying (3.4), the number of e satisfying τJ(e),τi(e)=ei is |E|λ-J-1. So,
(3.5)|{e∈Eλ∣τJ(e)=eJ,τi(e)=ei,fi(s,ei)=πi(m)}|=|E|λ-j-1
and a=q4s+2k-5, thus
(3.6)PI[i,J]=max⁡eJ∈EJmax⁡s∈Smax⁡m∈M|{e∈Eλ∣τJ(e)=eJ,τi(e)=ei,fi(s,ei)=πi(m)}||{e∈Eλ∣τJ(e)=eJ}|=max⁡eJ∈EJmax⁡s∈Smax⁡m∈Ma|E|=q4s+2k-5q(m0-3)+2(ν-2)+2(l-1)⋅(q2ν-m0-1-1)=1qm0+2ν+2l-4s-2k-4⋅(q2ν-m0-1-1).
Now, we compute the probability of substitution attack: we know that
(3.7)m=f(s,e)=(s+e1,s+e2,…,s+eλ)=(m1,m2,…,mλ)
and τJ(e)=(ei1,ei2,…,eij), whenever e=(e1,e2,…,ei1,…,eij︸,ek,…,eλ), while
(3.8)|{e∈Eλ∣m=f(s,e),τJ(e)=eJ}|=|E|λ-j,|{e∈Eλ∣m=f(s,e),τJ(e)=eJ,τi(e)=ei∈Ei,fi(s′,ei)=πi(m)}|=|E|λ-j-1⋅d
and d=qk1-4, therefore
(3.9)PS[i,J]=max⁡ej∈EJmax⁡s∈S,m∈Mmax⁡s≠s′∈S,m∈M|{e∈Eλ∣m=f(s,e),τJ(e)=eJ,τi(e)=ei∈Ei,fi(s′,ei)=πi(m′)}||{e∈Eλ∣m=f(s,e),τJ(e)=eJ}|=max⁡ej∈EJmax⁡s∈S,m∈Mmax⁡s≠s′∈S,m∈Md|E|=max⁡ej∈EJmax⁡s∈S,m∈Mmax⁡s≠s′∈S,m∈Mqk1-4q(m0-3)+2(ν-2)+2(l-1)⋅(q2ν-m0-1-1)=1qm0+2ν+2l-2s-k-5⋅(q2ν-m0-1-1),
where k1=2s+k.Two types of construction of authentication codes from singular symplectic geometry over finite fields are given. Among them, in the first construction, based on singular symplectic geometry structure of the authentication code with arbitration, the greatest probabilities of success for different types of deceptions are relatively lower, therefore there are some advantages. In addition, the second construction is based on singular symplectic geometry and is a multi-receiver authentication code. The probabilities of success for different types of deceptions are also computed. The results about multi-receiver authentication codes based on singular symplectic geometry are fewer. Thus, the structure of authentication code and the theory for further discussion are very meaningful.



---

*Source: 675484-2011-12-22.xml*