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

Notes p(e_R, e_T) ≠ 0 implies that any source s encoded by e_T can be authenticated by e_R.

Lemma 2.1. The six-tuple (S, E_T, E_R, M, f, g) is an authentication code with arbitration; that is

• (1)

  s + e_T = m ∈ M, for all s ∈ S and e_T ∈ E_T;

• (2)

  for any m ∈ M, s = m∩P₀ is uniquely information source contained in m and there is e_T ∈ E_T, such that m = s + e_T.

Proof. (1) Let s be a source state, that is, a subspace Q of type (2s + 1 + k, s, k) containing p and contained in p₀. Write E_k, Q as

which satisfies

Let e_T be a transmitter’s rule, that is, a subspace R of type (5,2, 1) containing P and R∩P₀ = P. So, there exists u₁, u₂ ∈ R, such that R = 〈v₁, v₂,   u₁,   u₂, e_2ν+1〉 and

Therefore, M = Q + 〈u₁, u₂〉 is a subspace of type (2s + 3 + k, s + 1, k) which contains P and M∩P₀ = Q is a subspace of type (2s + 1 + k, s, k), and is not orthogonal to v₂, hence a message.

(2) Now, let m be a message; that is, m is a subspace M of type (2s + 3 + k, s + 1, k) which contains P and intersects P₀ at a subspace of type (2s + 1 + k, s, k), and is not orthogonal to v₂. By definition, P₀ contains 〈v₁, v₂, e_2ν+1〉, so P ⊂ M∩P₀ = Q, so Q is a source state. Since M ≠ P₀, there exists u₁, u₂ ∈ M but u₁, u₂ ∉ P₀ such that M = Q + 〈u₁, u₂〉. We have to show that there exists u₁, u₂ ∈ M such that R = 〈v₁, v₂, u₁, u₂, e_2ν+1〉 is a subspace of type (5,2, 1), hence a transmitter’s encoding rule.

Assume that R = 〈v₁, v₂, u₁, u₂, e_2ν+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 v₂ ∈ Q^⊥ and v₂ ∉ M^⊥, we must have that $$ or $$. Without loss of generality, let $$. If we also have $$, replacing u₁ by u₁ − u₂, we get $$ and $$. Since R is not a subspace of type (5,2, 1), certainly $$. Note that Q is a subspace of type (2s + 1 + k, s, k), v₁ ∉ Q^⊥, so there exists a vector w ∈ Q such that v₁K_lw^T = 1. Replacing u₁ by w + u₁, we have $$, $$. Then, R = 〈v₁, v₂, u₁, u₂, e_2ν+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 state Q^′ such that M = Q^′ + R^′, we have that Q^′ ⊂ M∩P₀ = Q. by Q^′ ⊂ M, Q^′ ⊂ P₀. Since dim Q^′ = dim Q = 2s + 1 + k, so Q^′ = Q. This implies that the source state Q is uniquely determined by M.

Lemma 2.2. One has

Proof.

Let Q be a subspace of type (2s + 1 + k, s, k) contained in 〈v₂〉 ^⊥ and containing P. There exists a u ∈ Q such that v₁K_lu^T = 1. We may assume that u = (0,0, R₁, 1,0, R₂, 0,0, R₃). So, Q has a matrix representation of the form

It is easy to verify that Q₁, Q₂ 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)), Q₃ arbitrarily. Furthermore, we may take (Q₁, Q₂, Q₃) as

to compute n₁, where b = (ν − 2) − (s − 1). Since Q has a matrix representation of the form where a = s − 1  and  b = ν − s − 1, we have that where a = s − 1, b = ν − s − 1, so (P₁, P₂) is a subspace of type (m₀ − (2s + 1), s₀ − s) in the 2(v − s − 1)-dimensional symplectic space. We have that

So, the number of the subspaces (Q₁, Q₂) is denoted by N(m₀ − 3, s₀ − 1;   2(ν − 2)). Then, by the transitivity of Sp_2ν+l(F_q) on the set of subspaces of the same type, we can assume that

where c = s₀ − 1, a = m₀ − 2s₀ − 1, b = ν − m₀ + s₀, a₅, b₄, b₅ arbitrarily. We may get

Lemma 2.3. The number of the source states is

Proof. Since |S| is the number of subspaces of type (2s + 1 + k, s, k) contained in P₀ and containing P, we have |S | · n₃ = n₁ · n₂.

Lemma 2.4. The number of the encoding rules of transmitter is

Proof. Since |E_T| is the number of subspaces of type (5,2, 1) contained in P₀ and containing P, let R = 〈v₁, v₂, u₁, u₂, e_2ν+1〉, where $$, and 〈v₁, u₁〉⊥〈v₂, u₂〉. By the transitivity of Sp_2ν+1(F_q) on the set of subspaces of the same type, we can assume that

where c = s₀ − 1, a = m₀ − 2s₀ − 1, and  b = ν − m₀ + s₀. Therefore, u₁ and u₂ have the respective forms: Note that u₂ ∉ P₀ and dim (R∩p₀) = 3, so the vector u₁ cannot lie in P₀. Then, a₅, b₄, b₅ cannot equal zero at the same time. Thus, the number of u₁ is $$ and that for u₂ is q^{2(ν−2)+(l−1)}; we may get

Lemma 2.5. The number of the encoding rules of receiver is

Proof. |E_R| is the number of type (2,1, 0) intersecting P₀ at 〈v₂〉. Let H = 〈v₂, u〉, where v₂K_lu^T = 1. Following the notion of Lemma 2.4, hence u has the form

Clearly, u ∉ P₀. The number of u is q^2ν−2 · q^l, that is,

Lemma 2.6. For any m ∈ M, let the number of e_T and e_R contained in m be a and b, respectively. Then,

Proof. Let M be a message, and Q = M∩P₀, 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 = 〈v₁, v₂, u₁, u₂, e_2ν+1〉. Here, $$. Following the notation of Lemma 2.4, we can assume that Q has a matrix representation of the form

where a = m₀ − 2s₀ − 1, b = ν + s₀ − m, c = s₀ − s, and  d = s − 1. By $$ and R being the subspace of type (5,2, 1), we can assume where b₁ ≠ 0. Then, where a = m₀ − 2s₀ − 1, b = ν + s₀ − m, c = s₀ − s,   and  d = s − 1.

• (1)

  Note that M is fixed, so, for u₁, the a₄, a₅, a₆, b₄, b₅, b₆, and f₃ are fixed and, for u₂, the c₄, c₅, c₆, d₄, d₅, d₆, and g₃ are fixed. Therefore, the number of u₁ is q^{2(s−1)+(k−1)} · (q − 1) and the number of u₂ is q^{2(s−1)+(k−1)+1}. Then, the number of e_T contained in m is

  $$ (2.34)

• (2)

  Let H = 〈v₂, u〉 be a receiver’s encoding rule contained in M, where v₂K_lu^T = 1. Clearly, u ∉ Q, then we can assume that u has the form

  $$ (2.35)

Note that where k ∈ F_q. Therefore, the number of (h₄, h₅, h₆, i₄, i₅, i₆, j₃) is q. Then, the number of e_R contained in m is

Lemma 2.7. The number of the messages is

Proof. For any m ∈ M, there is uniquely s ∈ S and e_T ∈ E_T satisfying m = s + e_T; the number of e_T is a. Thus,

Lemma 2.8. (1) For any e_T ∈ E_T, the number of e_R contained in e_T is q³.

(2) For any e_R ∈ E_R, the number of e_T containing e_R is $$.

Proof. (1) Let R be a transmitter’s encoding rule; we can assume that R = 〈v₁, v₂, u₁, u₂, e_2ν+1〉. Here, $$, and 〈v₁, u₁〉⊥〈v₂, u₂〉. Then, the receiver’s encoding rule H contained in R should have the form H = 〈v₂, k₁v₁ + k₂u₁ + u₂ + k₃e_2ν+1〉, where k₁, k₂, k₃ ∈ F_q. So, the number of H is q³.

(2) Let H be a receiver’s encoding rule, and H = 〈v₂, u〉, where v₂K_lu^T = 1. Therefore, 〈v₁, v₂, u, e_2ν+1〉 is a subspace of type (4,1, 1). The number of subspace 〈v₁, v₂, u, u₁, e_2ν+1〉 of type (5,2, 1) is q^2ν−4 · q^l−1. Here, $$. Note that $$ and $$. It is easy to see that the number of u₁ ∈ P₀ such that 〈v₁, v₂, u₁, e_2ν+1〉 is a subspace of type (4,1, 1) is $$. So, the number of transmitter’s encoding rules e_T containing H is $$.

Lemma 2.9. For any m ∈ M and e_R ⊂ m, the number of e_T contained in m and containing e_R is

Proof. Let M be a message, and let H = 〈v₂, 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

where b₁ ≠ 0, a = s − 1, and  b = ν − s − 1.

Note that M is fixed, so a₄, b₄, f₃ are fixed. Assume that R is a transmitter’s encoding rule contained in M and containing H. Let R = 〈v₁, v₂, u, u₁, e_2ν+1〉, where $$. Thus, u₁ has the form

where d₁ ≠ 0. Note that (c₄, d₄, g₃) = k(a₄, b₄, f₃) and u₁ ∉ P₀, so k ≠ 0. Hence, u₁, c₄, d₄, and g₃ are fixed. Then, the number of u₁ is q^{2(s−1)+(k−1)} · (q − 1); that is, the number of R is q^{2(s−1)+(k−1)} · (q − 1).

Lemma 2.10. Assume that m₁ and m₂ are two distinct messages which commonly contain a transmitter’s encoding rule $$. s₁ and s₂ contained in m₁ and m₂ are two source states, respectively. Assume that s₀ = s₁ ⋂ s₂, dim   s₀ = k₁, then 3 ≤ k₁ ≤ 2s + k, and

• (1)

  the number of e_R contained in m₁ ⋂ m₂ is$$;

• (2)

  for any e_R ⊂ m₁ ⋂ m₂, the number of e_T containing  e_R is $$.

Proof. Since $$, $$, and m₁ ≠ m₂, then s₁ ≠ s₂. Again because of s₁⊃P₀ and s₂⊃P₀, 3 ≤ k₁ ≤ 2s + k. From $$, it is easy to know that $$. Therefore,

• (1)

  By the definition of the message, we can assume that m₁ and m₂ have the form as follows, respectively:

where b₄ ≠ 0, where d₄ ≠ 0. Thus, where g₄ ≠ 0. Since dim (m₁∩m₂) = k₁ + 2, therefore If e_R ⊂ m₁∩m₂, then

Since R₁, R₄ are arbitrary, every row of (0 0 R₃ 0 1 R₆ R₇) is the linear combination of the base

thus the number of it is $$. So, it is easy to know that the number of e_R contained in m₁ ⋂ m₂ is

• (2)

  Assume that m₁ ⋂ m₂ has the form of (2.46), then, for any e_R ⊂ m₁ ⋂ m₂, we can assume that

  $$ (2.51)

If e_R ⊂ e_T and e_T ⊂ m₁ ⋂ m₂, then where is the linear combination on the basis of then the number of e_T containing e_R is $$.

Theorem 2.11. The above construction yields anA²-code with the following size parameters:

Moreover, assume that the encoding rules e_T and e_R are chosen according to a uniform probability distribution, the largest probabilities of success for different types of deceptions:

Proof. (1) The number of m containing e_R is b,   then

• (2)

  Assume that opponent gets m₁, which is from transmitter, and sends m₂ instead of m₁, when s₁ contained in m₁ is different from s₂ contained in m₂; the opponent’s substitution attack can be successful. Because e_R ⊂   e_T ⊂ m₁, the opponent selects $$ satisfying $$ and dim (s₁ ⋂ s₂) = k₁, then

where k₁ = 2s + k.

• (3)

  Assume that R 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 q³. Let M^′ be another message, such that M^′ = R^′ + Q and R ≠ R^′. Then, e_R contained R ⋂ M^′ is at most q. So,

• (4)

  From Lemmas 2.8 and 2.9, thus

• (5)

  Assume that the receiver declares to receive a message m₂ instead of m₁,   when s₂ contained in m₁ is different from s₂ contained in m₂; the receiver’s substitution attack can be successful. Since e_R ⊂ e_T ⊂ m₁, receiver is superior to select $$, satisfying $$, thus $$, and dim (s₁∩s₂) = k₁ as large as possible. Therefore, the probability of a receiver’s successful substitution attack is

where k₁ = 2s + k.

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,

where J = {i₁, i₂, …, i_j}, i ∉ J.

Proof. Let $$, then

It is easy to know that |e ∈ E^λ∣τ_J(e) = e_J | = |E|^λ−j, and From Lemma 2.6, we know that the number of e_i satisfying (3.4) is a. For any e_i satisfying (3.4), the number of e satisfying τ_J(e), τ_i(e) = e_i is |E|^λ−J−1. So, and a = q^4s+2k−5, thus Now, we compute the probability of substitution attack: we know that and $$, whenever $$, while and $$, therefore where k₁ = 2s + k.