# A Construction of Multisender Authentication Codes with Sequential Model from Symplectic Geometry over Finite Fields

Authors: Shangdi Chen; Chunli Yang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Multisender authentication codes allow a group of senders to construct an authenticated message for a receiver such that the receiver can verify authenticity of the received message. In this paper, we construct  multisender authentication codes with sequential model from symplectic geometry over finite fields, and the parameters and the maximum probabilities of deceptions are also calculated.


---

## Body

## 1. Introduction

Information security consists of confidentiality and authentication. Confidentiality is to prevent the confidential information from decrypting by adversary. The purpose of authentication is to ensure the sender is real and to verify that the information is integrated. Digital signature and authentication codes are two important means of authenticating the information and provide good service in the network. In practical, digital signature is computationally secure assuming that the computing power of adversary is limited and a mathematical problem is intractable and complex. However, authentication codes are generally safe (unconditional secure) and relatively simple. In the 1940s, C. E. Shannon first put forward the concept of perfect secrecy authentication system using the information theory. In the 1980s, information theory method had been applied to the problem of authentication by G. J. Simmons; then authentication codes became the foundation for constructing unconditionally secure authentication system. In 1974, Gilbert et al. constructed the first authentication code [1], which is a landmark in the development of authentication theory. During the same period, Simmons independently studied the authentication theory and established three participants and four participants certification models [2]. The famous mathematician Wan Zhexian constructed an authentication code without arbitration from the subspace of the classical geometry [3]. In the case of transmitter and receiver being not honest, Ma et al. constructed a series of authentication codes with arbitration [4–9]. Xing et al. constructed authentication codes using algebraic curve and nonlinear functions, respectively [10, 11]. Safavi-Naini and Wang gave some results on multireceiver authentication codes [12]. Chen et al. made great contributions on multisender authentication codes from polynomials and matrices [13–19].With the rapid development of information science, the traditional one-to-one authentication codes have been unable to meet the requirements of network communication, thus making the study of multiuser authentication codes particularly important. Multiuser authentication code is a generalization of traditional two-user authentication code. It can be divided into two cases: one is a sender and many receivers authentication codes; the other one is many senders and a receiver authentication codes. We call the former as multireceiver authentication codes and the latter as multisender authentication codes. Safavi-Naini R gave some results on multireceiver authentication codes using the subspace of the classical geometry, while there are only some multisender authentication codes using polynomials and matrices to construct. We present the first construction multisender authentication code using the subspace of the classical geometry, specifically symplectic geometry.The main contribution of our paper is constructing a multi-sender authentication code using symplectic geometry. Furthermore, we calculate the corresponding parameters and the maximum probabilities of deceptions.The paper is organised as follows. Section2 gives the models of multisender authentication codes. In Section 3, we provide the calculation formulas on probability of success in attacks by malicious groups of senders. In Section 4, we give some definitions and properties on geometry of symplectic groups over finite fields. In Section 5, a construction of multisender authentication codes with sequential model from symplectic geometry over finite fields is given; then the parameters and the maximum probabilities of deceptions are also calculated. We give a comparison with the other construction of multisender authentication [19] in Section 6.


## 2. Models of Multisender Authentication Codes

We review the concepts of authentication codes which can be extracted from [20].Definition 1 (see [20]).
A systematic Cartesian authentication codeC is a 4-tuple (
S
,
E
,
T
;
f
), where S is the set of source states, E is the set of keys, T is the set of authenticators, and f
:
S
×
E
→
T is the authentication mapping. The message space M
=
S
×
T is the set of all possible messages.In the actual computer network communications, multisender authentication codes include sequential models and simultaneous models. Sequential models are that each sender uses his own encoding rules to encode a source state orderly, and the last sender sends the encoded message to the receiver; then the receiver receives the message and verifies whether the message is legal or not. Simultaneous models are that all senders use their own encoding rules to encode a source state simultaneously; then the synthesizer forms an authenticated message and sends it to the receiver; the receiver receives the message and verifies whether the message is legal or not.In the following we will give out the working principles of two modes of multisender authentication codes and the protocols that the participants should follow.Definition 2 (see [17]).
In sequential model, there are three participants: a group of sendersU
=
{
U
1
,
U
2
,
…
,
U
n
}; a Key Distribution Center (KDC), for the distribution keys to senders and receiver; a receiver who receives the authenticated message and verifies the message true or not. The code works as follows: each sender and receiver has their own Cartesian authentication code, respectively. It is used to generate part of the message and verify authenticity of the received message. Sender’s authentication codes are called branch authentication codes, and receiver’s authentication code is called channel authentication code. Let (
S
i
,
E
i
,
T
i
;
f
i
), i
=
1,2
,
…
,
n, be the ith sender’s Cartesian authentication codes, and let T
i
-
1
⊂
S
i, 1
≤
i
≤
n, (
S
,
E
,
T
;
f
) be the receiver’s Cartesian authentication code, and let S
=
S
1, T
=
T
i
,
π
i
:
E
→
E
i be a subkey generation algorithm. For authenticating a message, the senders and the receiver should comply with protocols:(1)
KDC randomly selects ane
∈
E and secretly sends it to the receiver R and sends e
i
=
π
i
(
e
) to the ith sender U
i, i
=
1,2
,
…
,
n;
(2)
if the senders would like to send a source states to the receiver R, U
1 calculates t
1
=
f
1
(
s
,
e
1
) and then sends t
1 to U
2 through an open channel; U
2 receives t
1 and calculates t
2
=
f
2
(
t
1
,
e
2
) and then sends t
2 to U
3 through an open channel. In general, U
i receives t
i
-
1 and calculates t
i
=
f
i
(
t
i
-
1
,
e
i
) and then sends t
i to U
i
+
1 through an open channel, 1
<
i
<
n. U
n receives t
n
-
1 and calculates t
n
=
f
n
(
t
n
-
1
,
e
n
) and then sends m
=
(
s
,
t
n
) through an open channel to the receiver R;
(3)
when the receiver receives the messagem
=
(
s
,
t
n
), he checks the authenticity by verifying whether t
n
=
f
(
s
,
e
) or not. If the equality holds, the message is regarded as authentic and is accepted. Otherwise, the message is rejected.Definition 3 (see [17]).
In simultaneous model of a multisender authentication code, there are four participants: a group of sendersU
=
{
U
1
,
U
2
,
…
,
U
n
}; a Key Distribution Center (KDC), for the distribution keys to senders and receiver; a synthesizer C who only runs the trusted synthesis algorithm; a receiver who receives the authenticated message and verifies the message true or not. The code works as follows: each sender and receiver has their own Cartesian authentication code, respectively. It is used to generate part of the message and verify the received message. Sender’s authentication codes are called branch authentication codes, and receiver’s authentication code is called channel authentication code. Let (
S
i
,
E
i
,
T
i
;
f
i
), i
=
1,2
,
…
,
n, be the sender’s Cartesian authentication codes, let (
S
,
E
,
T
;
f
) be the receiver’s Cartesian authentication code, let g
:
T
1
×
T
2
×
⋯
×
T
n
→
T be the synthesis algorithm, and let π
i
:
E
→
E
i be a subkey generation algorithm. For authenticating a message, the senders and the receiver should comply with protocols:(1)
KDC randomly selects a encoding rulee
∈
E and secretly sends it to the receiver R and sends e
i
=
π
i
(
e
) to the ith sender U
i
,
i
=
1,2
,
…
,
n;
(2)
if the senders would like to send a source states to the receiver R, U
i computes t
i
=
f
i
(
s
,
e
i
), i
=
1,2
,
…
,
n, and sends m
i
=
(
s
,
t
i
)
(
i
=
1,2
,
…
,
n
) to the synthesizer C through an open channel;
(3)
the synthesizerC receives the messages m
i
=
(
s
,
t
i
), i
=
1,2
,
…
,
n, and calculates t
=
g
(
t
1
,
t
2
,
…
,
t
n
) using the synthesis algorithm g; then sends message m
=
(
s
,
t
) to the receiver R;
(4)
when the receiver receives the messagem
=
(
s
,
t
), he checks the authenticity by verifying whether t
=
f
(
s
,
e
) or not. If the equality holds, the message is regarded as authentic and is accepted. Otherwise, the message is rejected.


## 3. Probabilities of Deceptions

We assume that the arbitrator (KDC) and the synthesizer (C) are credible; though they know the senders’ and receiver’s encoding rules, they do not participate in any communication activities. When transmitter and receiver are disputing, the arbitrator settles it. At the same time, assume that the system follows Kerckhoff’s principle which the other information of the whole system is public except the actual used keys. Assume that the source state spaceS and the receiver’s decoding rules space E
R are according to a uniform probability distribution; then the probability distribution of message space M and tag space T is determined by the probability distribution of S and E
R. In a multisender authentication system, assume that the whole senders cooperate 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.Assume thatU
1
,
U
2
,
…
,
U
n are senders, R is a receiver, and E
i is the encoding rules of U
i, 1
≤
i
≤
n. E
R is the decoding rules of receiver R. L
=
{
i
1
,
i
2
,
…
,
i
l
}
⊂
{
1,2
,
…
,
n
}, l
<
n, U
L
=
{
U
i
1
,
U
i
2
,
…
,
U
i
l
}, E
L
=
{
E
i
1
,
E
i
2
,
…
,
E
i
l
}.Impersonation Attack. U
L, after receiving their secret keys, sends a message m to receiver. U
L is successful if the receiver accepts it as legitimate message. Denote P
I
[
L
] as the maximum probability of success of the impersonation attack. It can be expressed as
(1)
P
I
[
L
]
=
max
⁡
e
L
∈
E
L
max
⁡
m
∈
M
P
(
m
is
accepted
by
R
∣
e
L
)
.Substitution Attack. U
L, after observing a legitimate message, substitutes it with another message m
′. U
L is successful if m
′ is accepted by receiver as authentic. Denote P
S
[
L
] as the maximum probability of success of the substitution attack. It can be expressed as
(2)
P
S
[
L
]
=
max
⁡
e
L
∈
E
L
max
⁡
m
∈
M
max
⁡
m
′
≠
m
∈
M
P
(
m
′
is
accepted
by
R
∣
m
,
e
L
)
.


## 4. Symplectic Geometry

In this section, we give some definitions and properties on geometry of symplectic groups over finite fields, which can be extracted from [20].Let𝔽
q be a finite field with q elements, n
=
2
ν and define the 2
ν
×
2
ν alternate matrix
(3)
K
=
(
0
I
(
ν
)
-
I
(
ν
)
0
)
.
The symplectic group of degree 2
ν over 𝔽
q, denoted by S
p
2
ν
(
𝔽
q
), is defined to be the set of matrices
(4)
S
p
2
ν
(
𝔽
q
)
=
{
T
∣
T
K
T
t
=
K
}
,
with matrix multiplication as its group operation. Let 𝔽
q
(
2
ν
) be the 2
ν-dimensional row vector space over 𝔽
q. S
p
2
ν
(
𝔽
q
) has an action on 𝔽
q
(
2
ν
) defined as follows:
(5)
𝔽
q
(
2
ν
)
×
S
p
2
ν
(
𝔽
q
)
⟶
𝔽
q
(
2
ν
)
,
(
(
x
1
,
x
2
,
…
,
x
2
ν
)
,
T
)
⟶
(
x
1
,
x
2
,
…
,
x
2
ν
)
T
.
The vector space 𝔽
q
(
2
ν
) together with this action of S
p
2
ν
(
𝔽
q
) is called the symplectic space over 𝔽
q.LetP be an m-dimensional subspace of 𝔽
q
(
2
ν
). We use the same latter P to denote a matrix representation of P; that is, P is an m
×
2
ν matrix of rank m such that its rows form a basis of P. The P
K
P
t is alternate. Assume that it is of rank 2
s; then P is called a subspace of type (
m
,
s
). It is known that subspaces of type (
m
,
s
) exist in 𝔽
q
(
2
ν
) if and only if
(6)
2
s
≤
m
≤
ν
-
s
.
It is also known that subspaces of the same type form an orbit under S
p
2
ν
(
𝔽
q
). Denote by N
(
m
,
s
;
2
ν
) the number of subspaces of type (
m
,
s
) in 𝔽
q
(
2
ν
).Denote byP
⊥ the set of vectors which are orthogonal to every vector of P; that is,
(7)
P
⊥
=
{
y
∈
𝔽
q
(
2
ν
)
∣
y
K
x
t
=
0
for
all
x
∈
P
}
.
Obviously, P
⊥ is a (
2
ν
-
m
)-dimensional subspace of 𝔽
q
(
2
ν
).Readers can refer to [15] for notations and terminology, which are not explained, on symplectic geometry of classical groups over finite fields.


## 5. Construction

Let𝔽
q be a finite field with q elements. Assume that 1
<
n
<
r
<
ν. U
=
〈
e
1
,
e
2
,
…
,
e
n
〉; then U
⊥
=
〈
e
1
,
…
,
e
ν
,
e
ν
+
n
+
1
,
…
,
e
2
ν
〉. Let W
i
=
〈
e
1
,
…
,
e
i
-
1
,
e
i
+
1
,
…
,
e
n
〉; then W
i
⊥
=
〈
e
1
,
…
,
e
ν
,
e
ν
+
i
,
e
ν
+
n
+
1
,
…
,
e
2
ν
〉. The set of source states S
=
{
s
∣
s is a subspace of type (
2
r
-
n
,
r
-
n
) and U
⊂
s
⊂
U
⊥
}; the set of ith sender’s encoding rules E
i
=
{
e
i
∣
e
i is a subspace of type (
n
+
1,1
), U
⊂
e
i and e
i
⊥
W
i
}, 1
≤
i
≤
n; the set of receiver’s decoding rules E
R
=
{
e
R
∣
e
R is a subspace of type (
2
n
,
n
) and U
⊂
e
R
}; the set of tags T
i
=
{
t
i
∣
t
i is a subspace of type (
2
r
-
n
+
i
,
r
-
n
+
i
) and U
⊂
t
i
}, 1
≤
i
≤
n.Define the encoding maps:(8)
f
1
:
S
×
E
1
⟶
T
1
,
f
1
(
s
,
e
1
)
=
s
+
e
1
,
f
i
:
T
i
-
1
×
E
i
⟶
T
i
,
f
i
(
t
i
-
1
,
e
i
)
=
t
i
-
1
+
e
i
,
2
≤
i
≤
n
.Define the decoding map:(9)
f
:
S
×
E
R
⟶
T
n
,
f
(
s
,
e
R
)
=
s
+
e
R
.This code works as follows.(1)
Key Distribution. First, the KDC does a list L of senders; assume that L
=
{
1,2
,
…
,
n
}. Then, the KDC randomly chooses a subspace e
R
∈
E
R and privately sends e
R to the receiver R. Last, the KDC randomly chooses a subspace e
i
∈
E
i and e
i
⊂
e
R, then privately sends e
i to the ith sender, 1
≤
i
≤
n.
(2)
Broadcast. For a source state s
∈
S, the sender U
1 calculates t
1
=
s
+
e
1 and sends (
s
,
t
1
) to U
2. The sender U
2 calculates t
2
=
t
1
+
e
2 and sends (
s
,
t
2
) to U
3. Finally, the sender U
n calculates t
n
=
t
n
-
1
+
e
n and sends m
=
(
s
,
t
n
) to the receiver R.
(3)
Verification. Since the receiver R holds the decoding rule e
R, R accepts m as authentic if t
n
=
s
+
e
R. Otherwise, it is rejected by R.Lemma 4.
LetC
=
(
S
,
E
R
,
T
n
;
f
), C
1
=
(
S
,
E
1
,
T
1
;
f
1
), C
i
=
(
T
i
-
1
,
E
i
,
T
i
;
f
i
)
(
2
≤
i
≤
n
); then C, C
1, C
i are all Cartesian authentication codes.Proof.
First, we show thatC is a Cartesian authentication code.
(1)   Fors
∈
S
,
e
R
∈
E
R. Let
(10)
s
=
(
U
Q
)
n
2
(
r
-
n
)
,
e
R
=
(
U
V
)
n
n
.
From the definition of s and e
R, we can assume that
(11)
(
U
Q
)
K
(
U
Q
)
t
=
(
0
(
n
)
0
0
0
0
I
(
r
-
n
)
0
-
I
(
r
-
n
)
0
)
,
(
U
V
)
K
(
U
V
)
t
=
(
0
I
(
n
)
-
I
(
n
)
0
)
.
Obviously, we have v
∉
s for any v
∈
V and v
≠
0. Therefore,
(12)
t
n
=
s
+
e
R
=
(
U
V
Q
)
,
(
U
V
Q
)
K
(
U
V
Q
)
t
=
(
0
I
(
n
)
0
0
-
I
(
n
)
0
*
*
0
*
0
I
(
r
-
n
)
0
*
-
I
(
r
-
n
)
0
)
.
From above, t
n is a subspace of type (
2
r
,
r
) and U
⊂
t
n; that is, t
n
∈
T
n.
(2) Fort
n
∈
T
n, t
n is a subspace of type (
2
r
,
r
) containing U. So there is subspace V
⊂
t
n, satisfying
(13)
(
U
V
)
K
(
U
V
)
t
=
(
0
I
(
n
)
-
I
(
n
)
0
)
.
Then, we can assume that t
n
=
(
U
V
Q
), satisfying
(14)
(
U
V
Q
)
K
(
U
V
Q
)
t
=
(
0
I
(
n
)
0
0
-
I
(
n
)
0
0
0
0
0
0
I
(
r
-
n
)
0
0
-
I
(
r
-
n
)
0
)
.
Let s
=
(
U
Q
); then s is a subspace of type (
2
r
-
n
,
r
-
n
) and U
⊂
s
⊂
U
⊥; that is, s
∈
S is a source state. For any v
∈
V and v
≠
0, we have v
∉
s and V
∩
U
⊥
=
{
0
}. Therefore, t
n
∩
U
⊥
=
(
U
Q
)
=
s. Let e
R
=
(
U
V
); then e
R is a transmitter’s encoding rule satisfying t
n
=
s
+
e
R.
Ifs
′ is another source state contained in t
n, then U
⊂
s
′
⊂
U
⊥. Therefore, s
′
⊂
t
n
∩
U
⊥
=
s, while dim
⁡
s
′
=
dim
⁡
s, so s
′
=
s. That is, s is the uniquely source state contained in t
n.
Similarly, we can show thatC
1 and C
i
(
2
≤
i
≤
n
) are also Cartesian authentication code.From Lemma4, we know that such construction of multisender authentication codes is reasonable. Next we compute the parameters of this code.Lemma 5.
The number of the source states is|
S
|
=
N
(
2
(
r
-
n
)
,
r
-
n
;
2
(
ν
-
n
)
).Proof.
For anys
∈
S, since U
⊂
s
⊂
U
⊥, s has the form
(15)
s
=
(
I
(
n
)
0
0
0
0
P
2
0
P
4
)
n
2
(
r
-
n
)
=
h
n
ν
-
n
n
ν
-
n
,
where (
P
2
,
P
4
) is a subspace of type (
2
(
r
-
n
)
,
r
-
n
) in the symplectic space F
q
2
(
ν
-
n
). Therefore, the number of the source states is |
S
|
=
N
(
2
(
r
-
n
)
,
r
-
n
;
2
(
ν
-
n
)
).Lemma 6.
The number of theith sender’s encoding rules is |
E
i
|
=
q
2
(
ν
-
n
).Proof.
For anye
i
∈
E
i, e
i is a subspace of type (
n
+
1,1
) containing U and e
i is orthogonal to W
i. So we can assume that e
i
=
t
(
e
1
,
…
,
e
n
,
u
), where u
=
(
x
1
x
2
⋯
x
2
ν
). Obviously, x
1
=
⋯
=
x
n
=
x
ν
+
1
=
⋯
=
x
ν
+
i
-
1
=
x
ν
+
i
+
1
=
⋯
=
x
ν
+
n
=
0, x
ν
+
i
=
1, and x
n
+
1
,
…
,
x
ν
,
x
ν
+
n
+
1
,
…
,
x
2
ν arbitrarily. Therefore, |
E
i
|
=
q
2
(
ν
-
n
).Lemma 7.
The number of the receiver’s decoding rules is|
E
R
|
=
q
2
n
(
ν
-
n
).Proof.
For anye
R
∈
E
R, since e
R is a subspace of type (
2
n
,
n
) containing U, e
R has the form
(16)
e
R
=
(
I
(
n
)
0
0
0
0
Q
2
I
(
n
)
Q
4
)
n
n
n
ν
-
n
n
ν
-
n
,
where Q
2, Q
4 are arbitrary matrices. Therefore, |
E
R
|
=
q
2
n
(
ν
-
n
).Lemma 8.
(1) The number of decoding rulese
R contained in t
n is q
2
n
(
r
-
n
);
(2) the number of the tags is|
T
n
|
=
q
2
n
(
ν
-
r
)
N
(
2
(
r
-
n
)
,
r
-
n
;
2
(
ν
-
n
)
).Proof.
(1)   For anyt
n
∈
T
n, t
n is a subspace of type (
2
r
,
r
) and U
⊂
t
n. We assume that t
n has the form
(17)
t
n
=
(
I
(
n
)
0
0
0
0
0
0
I
(
r
-
n
)
0
0
0
0
0
0
0
I
(
n
)
0
0
0
0
0
0
I
(
r
-
n
)
0
)
n
r
-
n
n
r
-
n
n
r
-
n
ν
-
r
n
r
-
n
ν
-
r
.
If e
R
⊂
t
n, then we can assume that
(18)
e
R
=
(
I
(
n
)
0
0
0
0
0
0
R
2
0
I
(
n
)
R
5
0
)
n
n
n
r
-
n
ν
-
r
n
r
-
n
ν
-
r
,
where R
2
,
R
5 are arbitrary matrices. Therefore, the number of e
R contained in t
n is q
2
n
(
r
-
n
).
(2) We know that a tag contains only one source state and the number of decoding rulese
R contained in t
n is q
2
n
(
r
-
n
). Therefore, we have |
T
n
|
=
|
S
|
|
E
R
|
/
q
2
n
(
r
-
n
)
=
q
2
n
(
ν
-
r
)
N
(
2
(
r
-
n
)
,
r
-
n
;
2
(
ν
-
n
)
).Theorem 9.
The parameters of the above constructed multisender authentication code are(19)
|
S
|
=
N
(
2
(
r
-
n
)
,
r
-
n
;
2
(
ν
-
n
)
)
;
|
E
i
|
=
q
2
(
ν
-
n
)
;
|
E
R
|
=
q
2
n
(
ν
-
n
)
;
|
T
n
|
=
q
2
n
(
ν
-
r
)
N
(
2
(
r
-
n
)
,
r
-
n
;
2
(
ν
-
n
)
)
.Without loss of generality, we can assume thatU
L
=
{
U
1
,
U
2
,
…
,
U
l
}, E
L
=
{
E
1
×
⋯
×
E
l
}, where l
<
n.Lemma 10.
For anye
L
=
(
e
1
,
e
2
,
…
,
e
l
)
∈
E
L, the number of e
R containing e
L is q
2
(
n
-
l
)
(
ν
-
n
).Proof.
For anye
L
=
(
e
1
,
e
2
,
…
,
e
l
)
∈
E
L, we can assume that
(20)
e
L
=
(
I
(
l
)
0
0
0
0
0
0
I
(
n
-
l
)
0
0
0
0
0
0
P
3
I
(
l
)
0
P
6
)
l
n
-
l
l
l
n
-
l
ν
-
n
l
n
-
l
ν
-
n
.
If e
L
⊂
e
R, then e
R has the form
(21)
e
R
=
(
I
(
l
)
0
0
0
0
0
0
I
(
n
-
l
)
0
0
0
0
0
0
P
3
I
(
l
)
0
P
6
0
0
P
3
′
0
I
(
n
-
l
)
P
6
′
)
l
n
-
l
l
n
-
l
l
n
-
l
ν
-
n
l
n
-
l
ν
-
n
,
where P
3
′, P
6
′ are arbitrary matrices. Therefore, the number of e
R containing e
L is q
2
(
n
-
l
)
(
ν
-
n
).Lemma 11.
For anyt
n
∈
T
n and e
L
=
(
e
1
,
e
2
,
…
,
e
l
)
∈
E
L, the number of e
R contained in t
n and containing e
L is q
2
(
n
-
l
)
(
r
-
n
).Proof.
For anyt
n
∈
T
n, t
n is a subspace of type (
2
r
,
r
) and U
⊂
t
n. We assume that t
n has the form
(22)
t
n
=
(
I
(
n
)
0
0
0
0
0
0
I
(
r
-
n
)
0
0
0
0
0
0
0
I
(
n
)
0
0
0
0
0
0
I
(
r
-
n
)
0
)
n
r
-
n
n
r
-
n
n
r
-
n
ν
-
r
n
r
-
n
ν
-
r
.
If e
L
⊂
t
n, assume that e
L has the form(23)
e
L
=
(
I
(
l
)
0
0
0
0
0
0
0
0
I
(
n
-
l
)
0
0
0
0
0
0
0
0
R
3
0
I
(
l
)
0
R
7
0
)
l
n
-
l
l
l
n
-
l
r
-
n
v
-
r
l
n
-
l
r
-
n
ν
-
r
.If e
R
⊂
t
n and e
L
⊂
e
R, then(24)
e
R
=
(
I
(
l
)
0
0
0
0
0
0
0
0
I
(
n
-
l
)
0
0
0
0
0
0
0
0
R
3
0
I
(
l
)
0
R
7
0
0
0
R
3
′
0
0
I
(
n
-
l
)
R
7
′
0
)
l
n
-
l
l
n
-
l
l
n
-
l
r
-
n
v
-
r
l
n
-
l
r
-
n
ν
-
r
,where R
3
′, R
7
′ are arbitrary matrices. Therefore, the number of e
R contained in t
n and containing e
L is q
2
(
n
-
l
)
(
r
-
n
).Lemma 12.
Assume thatt
n
∈
T
n and t
n
′
∈
T
n are two distinct tags which are decoded by receiver’s decoding rule e
R. s
1 and s
2 contained in t
n and t
n
′, respectively. Let s
0
=
s
1
∩
s
2, dim
⁡
s
0
=
k; then n
≤
k
≤
2
r
-
n
-
1; the number of e
R contained in t
n
∩
t
n
′ and containing e
L is q
(
n
-
l
)
(
k
-
n
).Proof.
Sincet
n
=
s
1
+
e
R, t
n
′
=
s
2
+
e
R and t
n
≠
t
n
′, then s
1
≠
s
2. And for any s
∈
S, U
⊂
s, therefore, n
≤
k
≤
2
r
-
n
-
1. Assume that s
i
′ is the complementary subspace of s
0 in the s
i; then s
i
=
s
0
+
s
i
′
(
i
=
1,2
). Because of t
n
=
s
1
+
e
R
=
s
0
+
s
1
′
+
e
R, t
n
′
=
s
2
+
e
R
=
s
0
+
s
2
′
+
e
R and s
1
=
t
n
∩
U
⊥, s
2
=
t
n
′
∩
U
⊥, we know s
0
=
(
t
n
∩
U
⊥
)
∩
(
t
n
′
∩
U
⊥
)
=
t
n
∩
t
n
′
∩
U
⊥
=
s
1
∩
t
n
′
=
s
2
∩
t
n, and t
n
∩
t
n
′
=
(
s
1
+
e
R
)
∩
t
n
′
=
(
s
0
+
s
1
′
+
e
R
)
∩
t
n
′
=
(
(
s
0
+
e
R
)
+
s
1
′
)
∩
t
n
′. Since s
0
+
e
R
⊆
t
n
′, then t
n
∩
t
n
′
=
(
s
0
+
e
R
)
+
(
s
1
′
∩
t
n
′
), while s
1
′
∩
t
n
′
⊆
s
1
∩
t
n
′
=
s
0, so t
n
∩
t
n
′
=
s
0
+
e
R.
From the definition of thet
n and t
n
′, we assume that
(25)
t
n
=
(
I
(
n
)
0
0
0
0
P
22
0
0
0
0
I
(
n
)
0
0
0
0
P
44
)
n
r
-
n
n
r
-
n
n
ν
-
n
n
ν
-
n
,
t
n
′
=
(
I
(
n
)
0
0
0
0
P
22
′
0
0
0
0
I
(
n
)
0
0
0
0
P
44
′
)
n
r
-
n
n
r
-
n
n
ν
-
n
n
ν
-
n
.
Let(26)
t
n
∩
t
n
′
=
(
I
(
n
)
0
0
0
0
P
2
0
0
0
0
I
(
n
)
0
0
0
0
P
4
)
n
r
-
n
n
r
-
n
n
ν
-
n
n
ν
-
n
.
And from above we know that t
n
∩
t
n
′
=
s
0
+
e
R; then dim
⁡
(
t
n
∩
t
n
′
)
=
k
+
n; therefore,
(27)
dim
⁡
(
0
P
2
0
0
0
0
0
P
4
)
=
k
-
n
.
For any e
L
⊂
t
n
∩
t
n
′, we assume that
(28)
e
L
=
(
I
(
l
)
0
0
0
0
0
0
I
(
n
-
l
)
0
0
0
0
0
0
R
3
I
(
l
)
0
R
6
)
l
n
-
l
l
l
n
-
l
ν
-
n
l
n
-
l
ν
-
n
.
If e
R
⊂
t
n
∩
t
n
′ and e
L
⊂
e
R, then e
R has the form
(29)
e
R
=
(
I
(
l
)
0
0
0
0
0
0
I
(
n
-
l
)
0
0
0
0
0
0
R
3
I
(
l
)
0
R
6
0
0
R
3
′
0
I
(
n
-
l
)
R
6
′
)
l
n
-
l
l
n
-
l
l
n
-
l
ν
-
n
l
n
-
l
ν
-
n
.
So, every row of (
0
R
3
′
0
R
6
′
) is the linear combination of (
0
P
2
0
0
0
0
0
P
4
). Therefore, the number of e
R contained in t
n
∩
t
n
′ and containing e
L is q
(
n
-
l
)
(
k
-
n
).Theorem 13.
In the constructed multi-sender authentication codes, the maximum probabilities of success for impersonation attack and substitution attack fromU
L on the receiver R are
(30)
P
I
(
L
)
=
1
q
2
(
n
-
l
)
(
ν
-
r
)
,
P
S
(
L
)
=
1
q
(
n
-
l
)
.Proof.
(1)Impersonation Attack. U
L, after receiving their secret keys, sends a message m to R. U
L is successful if the receiver accepts it as authentic. Therefore,
(31)
P
I
(
L
)
=
max
⁡
e
L
∈
E
L
max
⁡
m
∈
M
{
|
{
e
R
∈
E
R
∣
e
L
⊂
e
R
,
e
R
⊂
t
}
|
|
{
e
R
∈
E
R
∣
e
L
⊂
e
R
}
|
}
=
q
2
(
n
-
l
)
(
r
-
n
)
q
2
(
n
-
l
)
(
ν
-
n
)
=
1
q
2
(
n
-
l
)
(
ν
-
r
)
.
(2)Substitution Attack. R
L, after observing a message m that is transmitted by the sender, replaces m with another message m
′. R
L is successful if m
′ is accepted by R as authentic. Therefore,
(32)
P
S
(
L
)
=

max
⁡
e
L
∈
E
L
max
⁡
m
∈
M
max
⁡
m
≠
m
′
∈
M

{
|
{
e
R
∈
E
R
∣
e
L
⊂
e
R
,
e
R
⊂
t
,
e
R
⊂
t
′
}
|
|
{
e
R
∈
E
R
∣
e
L
⊂
e
R
,
e
R
⊂
t
}
|
}
=
max
⁡
n
≤
k
≤
2
r
-
n
-
1
q
(
n
-
l
)
(
k
-
n
)
q
2
(
n
-
l
)
(
r
-
n
)
=
1
q
(
n
-
l
)
.


## 6. The Advantage of the Constructed Authentication Code

The security of an authentication code could be measured by the maximum probabilities of deceptions. The smaller the probability of successful attack, the higher the security of the authentication codes. Now let us compare the security of our constructed authentication code with the known one [19].The constructed authentication code in [19] is also a multisender authentication code from symplectic geometry over finite fields, but which is in simultaneous model. If we choose the parameters n, n
′, r, and ν with 1
<
n
<
n
′
<
r
<
ν, n
>
(
r
/
2
), and n
′
-
n
>
ν
-
r, from Table 1 we see that the maximum probabilities of deceptions of our construction are smaller than the construction in [19]. Therefore, compared with the construction in [19], our construction is more efficient.Table 1
(
n
>
r
/
2
,
n
′
-
n
>
ν
-
r
).
Constructions
[19]
Size relation
Ours
The number of senders
n
=
n
The number of attackers
l
,
1
≤
l
<
n
=
l
,
1
≤
l
<
n
The parameters of codes
|
S
|
N
(
2
(
r
-
n
)
,
r
-
n
;
2
(
ν
-
n
)
)
=
N
(
2
(
r
-
n
)
,
r
-
n
;
2
(
ν
-
n
)
)
|
E
i
|
q
2
(
ν
-
n
)
=
q
2
(
ν
-
n
)
|
E
R
|
q
2
n
′
(
ν
-
n
′
)
>
q
2
n
(
ν
-
n
)
|
T
|
N
(
2
(
r
-
n
)
,
r
-
n
;
2
(
ν
-
n
)
)
q
2
n
′
(
ν
-
r
-
n
′
+
n
)
<
N
(
2
(
r
-
n
)
,
r
-
n
;
2
(
ν
-
n
)
)
q
2
n
(
ν
-
r
)
The probabilities of deceptions
P
I
(
L
)
1
q
2
(
n
′
-
l
)
(
ν
+
n
-
n
′
-
r
)
-
(
n
′
-
n
)
(
n
-
l
)
>
1
q
2
(
n
-
l
)
(
ν
-
r
)
P
S
(
L
)
1
q
(
n
′
-
l
)
(
2
n
-
2
n
′
+
1
)
+
(
n
′
-
n
)
(
n
-
l
)
>
1
q
n
-
l



---

*Source: 102301-2014-04-30.xml*