Abstract
In this paper, we show a “direct” equivalence between certain authentication codes and robust threshold schemes. It was previously known that authentication codes and robust threshold schemes are closely related to similar types of designs, but direct equivalences had not been considered in the literature. Our new equivalences motivate the consideration of a certain “key-substitution attack.” We study this attack and analyze it in the setting of “dual authentication codes.” We also show how this viewpoint provides a nice way to prove properties and generalizations of some known constructions.
1 Background and Our Contributions
In this paper, we study various aspects of optimal authentication codes and robust threshold schemes. We only consider unconditionally secure authentication codes and threshold schemes in this paper. Detailed definitions and basic results on authentication codes and robust threshold schemes can be found in Sections 2.1 and 2.2. In this section, we just give a brief overview of previous results along with a summary of our contributions.
A(k, n)-threshold scheme allows a secret to be split into n shares so that k shares are necessary and sufficient for the secret to be reconstructed. Such a scheme is robust if a “fake” share, along with k−1 valid shares, does not result in an incorrect secret being reconstructed. Robust threshold schemes are often constructed by a two-step process: First, the secret is “encoded” using a suitable combinatorial structure such as a difference set [1], EDF [2] or AMD code [3, 4]. Second, the encoded secret is shared using a traditional Shamir threshold scheme. Robust (k, n)-threshold schemes were introduced in 1988 by Tompa andWoll [5] and they have received considerable study by many authors since then; see, for example, [1, 2, 6, 7, 8]. Recent papers on this topic include [9, 10, 11].
An authentication code provides a method for a sender to encode a message using a secret key so that a designated receiver can decode the message using the same key. An active adversary should not be able to find a “bogus” message which the receiver would accept as valid. Optimal authentication codes also have a long history. Some important early papers include [2, 12, 13, 14, 15]. Some additional papers, which specifically discuss “splitting” authentication codes, include [16, 17, 18]. Finally, [19, 20] are two recent works on this topic.
There has been previous work, for example in [1, 2], discussing constructions for “optimal” authentication codes and robust threshold schemes In the context of authentication codes, “optimal” means that the deception probabilities are as small as possible and the number of encoding rules (or keys) is also as small as possible. For a robust threshold scheme, “optimal” means that the deception probabilities meet a specified bound that is expressed in terms of the number of possible shares and the number of possible secrets.
Previous work has used combinatorial structures such as BIBDs, difference sets, external BIBDs (EBIBDs), external difference families (EDFs) and splitting BIBDs in order to construct optimal robust threshold schemes and authentication codes. Additionally, some partial converses have been proven, which show that optimal authentication codes and robust threshold schemes imply the existence of some of the above-mentioned combinatorial structures.
Without going into details, the following are the main previous results along this line:
In [2] it is shown that a robust threshold scheme can be constructed from an EDF with λ = 1. (This construction incorporates a Shamir threshold scheme as an ingredient.) Conversely, certain robust threshold schemes give rise to certain EBIBDs.
In [1] it is shown that a robust threshold scheme can be constructed from a difference set. (This construction also incorporates a Shamir threshold scheme as an ingredient.) Conversely, certain robust threshold schemes give rise to certain symmetric BIBDs (SBIBDs).
In [2], a construction is given for splitting authentication codes from EDFs with λ = 1. This paper also constructs certain authentication codes from splitting BIBDs with λ = 1, as well as proving a converse result.
The above results suggest that there could be connections between authentication codes and robust threshold schemes, as they are closely related to similar (and sometimes identical) types of designs. For example, the combinatorial designs generated by EDFs (which include difference sets as a special case) can be used to construct both robust threshold schemes and authentication codes.
One of the main contributions of this paper is to show a “direct” equivalence between certain authentication codes and (2, 2)-robust threshold schemes. We also study a key-substitution attack for authentication codes and interpret it in light of what we term “dual authentication codes.”
The rest of this paper is organized as follows. Detailed definitions of authentication codes and robust threshold schemes are given in Sections 2.1 and 2.2, along with some basic results that we use in the rest of the paper. We also introduce key-substitution attacks, which have not been studied previously, in this section. In Section 3, we prove our main equivalence result involving authentication codes and (2, 2)-robust threshold schemes. Various combinatorial constructions for authentication codes that are studied in Section 4. These constructions, which are based on designs such as BIBDs (including symmetric and splitting BIBDs) and external difference families, produce authentication codes that in turn yield (2, 2)-robust threshold schemes via the equivalences proven in Section 3. The notion of “dual authentication codes” is introduced and explored in Section 5. This allows a deeper understanding of key-substitution attacks. Finally, some closing remarks are given in Section 6.
2 Definitions and Basic Results
We present definitions of authentication codes and robust threshold schemes on this section, along with a few basic results.
2.1 Authentication Codes
We follow Simmons’ model for unconditionally secure authentication [12]. A key K determines an encoding rule eK, which is a possibly randomized mapping e K : 𝒮 → M. Elements in 𝒮 are called sources and elements of M are messages. In general, we view eK(s) as a set of messages in the case that encoding is randomized (this is often called authentication with splitting). The key K is chosen from a keyspace 𝒦. The key and the source can be treated as independent random variables. If |eK(s)| = c for all s ∈ 𝒮 and all K ∈ 𝒦, the code is called a c-splitting authentication code.
Given a key K and a message m, at most one source should be “possible.” That is, for every key K, we require that
For any key K, denote
The set μ(K) consists of all the messages that are valid encodings of a source under key K. Also, for any message m, denote
The set κ(m) consists of all the keys for which m is a valid encoding of some source.
The encoding matrix of an authentication code is a matrix E in which the rows are indexed by the keys in 𝒦 and the columns are indexed by the sources in 𝒮. The entry E(k, s) is simply the set (of messages) eK(s). The entries E(k, s) in the encoding matrix are singletons if and only if the code has no splitting, i.e., c = 1.
We are primarily interested in authentication codes having perfect secrecy, i.e., codes having the property that a message reveals no information about the source to an adversary who does not know the key. We also often want authentication codes that are secure against both message-substitution and key-substitution attacks. These attacks are defined as follows.
In a message-substitution attack (also called a substitution attack), the adversary sees a message m and replaces it with a message m′ ≠ m. The adversary wins if m′ ∈ eK(s′) and m ∈ eK(s), where K is the (unknown) secret key and s′ ≠ s. This is often just called a substitution attack; these types of attacks have been considered for many years.
In a key-substitution attack, the adversary sees a key K and replaces it with a key K′ ≠ K. The adversary wins if m ∈ eK(s) and m ∈ eK′(s′), where m is the (unknown) message and s′ ≠ s. This is perhaps a less natural type of attack to consider than a message-substitution attack. In fact, we are not aware of any previous study of unconditionally secure authentication codes that considers key-substitution attacks. However, we should note that a similar attack has been studied in the setting of systematic algebraic manipulation detection (AMD) codes; see [3].
There is another attack that is often studied for authentication codes, namely, an impersonation attack. In this attack, the adversary chooses a message, without seeing a “previous” message, hoping that it is an encoding of some source under the (unknown) key K.
The success probability of an attack (impersonation, message-substitution or key-substitution) is the probability that the adversary wins the corresponding “game.” This probability is computed over a random choice of key, source, and message encoding (if encoding of messages is randomized, i.e., in the case of a code with splitting) according to the probability distributions specified on them. Throughout this paper, we assume that the probability distributions defined on the keys and message encodings are uniform. That is, Prob[K] = 1 /b for all keys K ∈ 𝒦, where b = |𝒦|, and in a c-splitting code, for a given key K ∈ 𝒦 and source s ∈ 𝒮, we have Prob[m] = 1/c for all m ∈ eK(s).
Source probability distributions are often (but not always) assumed to be uniform. Also, in all of the attacks we study, we assume that a key is used to encode only one message.
The adversary’s optimal success probability for an impersonation attack is often denoted by
Theorem 2.1
[12, 17, 18] Suppose a c-splitting authentication code for k sources has v messages. Then
For a code without splitting (i.e., c = 1), the bounds obtained from Theorem 2.1 are
The following two results will be used several times later in the paper. They do not assume equiprobable sources.
Lemma 2.2
Suppose a c-splitting authentication code for k sources has v messages, b equiprobable keys and equiprobable message encoding. Then
Proof. Let K be the key that was chosen by the sender/ receiver. The message m chosen by the attacker will be accepted as valid if and only if K ∈ κ(m). Since there are b possible keys, the choice of m will be a successful impersonation with probability |κ(m)|/b.
Define
Clearly
However, we also have
Therefore,
and equality occurs if and only if |κ(m)| = bck/v for all messages m.
The adversary’s optimal attack is to choose m so that |κ(m)| is maximized. Hence, the maximum success probability of an impersonation attack is at least ck/v, and equality occurs if and only if |κ(m)| = bck/v for all messages m. □
Theorem 2.3
Suppose a c-splitting authentication code for k sources has v messages, b equiprobable keys and equiprobable message encoding. Consider the following three conditions:
the code achieves perfect secrecy;
within each column of the encoding matrix, every message occurs the same number of times.
Then the code satisfies conditions 1. and 2. if and only if it satisfies condition 3.
Proof. For any s ∈ 𝒮 and m ∈ 𝓜, define
Thus κ(m, s) contains the keys for which m is a valid encoding of s. We observe that
Suppose the code satisfies 2. Perfect secrecy is achieved if and only if
for all s ∈ 𝒮 and all m ∈ 𝓜. By Bayes’ Theorem, this is equivalent to proving
for all s ∈ 𝒮 and all m ∈ 𝓜.
For a given message m, equations (1) and (2) imply that |κ(m, s1)| = |κ(m, s2)| for all sources s1, s2. It is clear that
where the sets κ(m, s) (s ∈ 𝒮) are disjoint. Therefore
for any fixed source s ∈ 𝒮.
Now, assume additionally that the code satisfies condition 1. From Lemma 2.2, we have |κ(m)| = bck/v. Hence, it follows that
for every m ∈ 𝓜, s ∈ 𝒮. Therefore, condition 3. holds.
Conversely, suppose condition 3. holds. Let s ∈ 𝒮. Then |κ(m1, s)| = |κ(m2, s)| for all m1, m2 ∈ 𝓜. We have
since there are b rows in the encoding matrix and each cell contains c messages. Therefore, equation (4) holds for all s ∈ 𝒮 and all m ∈ 𝓜. Hence, from (1),
for all s ∈ 𝒮 and all m ∈ 𝓜. Then
so Prob[m | s] = Prob[m] for all s ∈ 𝒮 and m ∈ 𝓜. Therefore, equation (2) holds and we have perfect secrecy.
To see that
for all m ∈ 𝓜. Then
□
2.2 Threshold Schemes
An unconditionally secure (2, 2)-threshold scheme enables a secret s to be “split” into two shares v1 and v2 in such a way that
v1 and v2 uniquely determine s via a reconstruction function. We express this as Reconstruct(v1, v2) = s.
No individual share yields any information about the secret. That is,
More generally, a (k, n)-threshold scheme enables a secret s to be split into n shares in such a way that any k shares permit the secret to be reconstructed, but no set of k − 1 or fewer shares yield any information about the secret.
In a robust (2, 2)-threshold scheme, we consider the scenario where one player may modify their share, hoping that Reconstruct will then yield an incorrect secret. So we consider a setting where Reconstruct either returns a secret or ⊥, where the latter indicates that no secret can be reconstructed from the two given shares. Suppose that the first player, P1, alters their share as
where s′ ≠ s. P1 loses the game if
Similarly, if P2 alters their share as
A robust (2, 2)-threshold scheme is ϵ-secure if no strategy by P1 or P2 will allow them to win the deception game with probability exceeding ϵ. Subsequently, we may refer to such a scheme simply as an ϵ-secure (2, 2)-threshold scheme.
3 Equivalences
In the next subsections, we show the equivalence of certain authentication codes and robust (2, 2)-threshold schemes.
3.1 Threshold Scheme to Authentication Code
Given an ϵ-secure robust (2, 2)-threshold scheme, we construct an authentication code. This is somewhat similar to the the construction used by Kurosawa, Obana and Ogata in [7, Theorem 15].
For any ordered pair of shares (v1, v2) such that Reconstruct(v1, v2) = s, define
The probability distribution on the sources in the authentication code should be the same as the probability distribution on the shares of the threshold scheme. Also, note the following correspondences:
| threshold scheme | authentication code | |
|---|---|---|
| source s | ⟷ | secret s |
| share v1 | ⟷ | key K |
| share v2 | ⟷ | message m. |
We show that the resulting authentication scheme satisfies various properties now.
Message-substitution attack. Suppose an adversary replaces m ≠ eK(s) with m′ ≠ m in the authentication code. This corresponds to modifying share v2 (the second share) from m to m′ in the robust threshold scheme. Because the threshold scheme is robust, we know that
In other words,
Therefore, the probability of a successful message-substitution attack is at most ϵ.
Key-substitution attack. Suppose an adversary replaces K with K ′ = K in the authentication code, where m ∈ eK(s). This corresponds to modifying share v1 (the first share) from K to K′ in the robust threshold scheme. Because the threshold scheme is robust, we know that
In other words,
Therefore, the probability of a successful key-substitution attack is at most ϵ.
Perfect Secrecy. The threshold scheme has the property that one share yields no information about the value of the secret. Therefore, in particular,
Suppose the share v2 is fixed but we have no information about the share v1. Then we have no information about the secret s. In the corresponding authentication code, this means that the message m = v2 provides no information about the source s when the key K = v1 is not known, so we have perfect secrecy.
It is also possible to construct authentication codes with similar properties from any robust (k, n)-threshold scheme with k ≥ 2. For example, see [1]. The idea is to fix shares for the first k − 2 players, say, by choosing some (k − 2)-tuple of shares that occurs with probability greater than 0. Consider the subset of distribution rules such that the first k − 2 shares take on the specified values. Retain the shares for the next two players, but throw away the shares that would be given to the last n − k players. This gives rise to a (2, 2)-threshold scheme, which can then be used to construct an authentication code using the above-described technique.
3.2 Authentication Code to Threshold Scheme
The construction in the previous subsection can easily be reversed. Now we start with an authentication code having perfect secrecy and we assume that message-substitution and key-substitution attacks have success probability at most ϵ. We construct a (2, 2)-threshold scheme as follows: shares for P1 are keys in the authentication code, shares for P2 are messages in the authentication code, and secrets are sources in the authentication code. Note that P1 and P2 have shares of the same size if and only if the number of keys is the same as the number of messages (in the authentication code).
For every m ∈ eK(s), construct a distribution rule (K, m; s), i.e., v1 = K, v2 = m and
We need to show that the resulting set of distribution rules defines an ϵ-secure (2, 2)-threshold scheme.
Secret reconstruction. Suppose that we have two distribution rules (K, m; s) and (K, m; s′) with s′ ≠ s. Then m ∈ eK(s) ∩ eK(s′) in the authentication code, which is not allowed. Thus, two shares determine at most one secret.
Information revealed by one share. We want to prove that
If v1 = K is given, then this yields no information about s because K and s are independent in the authentication code. If v2 = m is given, then this yields no information about s because the authentication code has perfect secrecy.
Modifying v1. Suppose P1 replaces their share
so
Modifying v2. Suppose P2 replaces their share
so
3.3 Main Theorem
Summarizing the results in the two previous subsections, we have our main equivalence theorem. For simplicity, we assume equiprobable distributions of sources (in the authentication code) and secrets (in the threshold scheme).
Theorem 3.1
There exists an authentication code with perfect secrecy for k uniformly distributed sources that is ϵ-secure against message-substitution and key-substitution attacks if and only if there exists an ϵ-secure (2, 2)-threshold scheme for k uniformly distributed secrets.
4 Combinatorial Constructions
In this section, we look at various constructions for authentication codes that are based on combinatorial designs, paying particular attention to the properties (namely, perfect secrecy and key-substitution attacks) that are relevant for the construction of robust (2, 2)-threshold schemes using Theorem 3.1. Throughout this section, we assume standard design-theoretic definitions that can be found, for example, in [21].
4.1 Symmetric BIBDs
First, we give a simple construction using symmetric BIBDs (i.e., SBIBDs). This is a slight generalization of constructions given in [1, 2] since we do not require that the SBIBD is generated from a difference set.
Suppose that (X,𝓑) is a (v, k, λ)-SBIBD (so λ(v − 1) = k(k − 1)). Suppose that X = {xi : 1 ≤ i ≤ v} is the set of points in the design and 𝓑 = {Bj : 1 ≤ j ≤ v} is the set of blocks in the design. We can order each block Bj to obtain a k-tuple C j = (c1,j , . . . , ck,j) in such a way that the following property is satisfied:
for every i, 1 ≤ i ≤ v, and every ℓ, 1 ≤ ℓ ≤ k. That is, we can write out the ordered blocks Cj (1 ≤ j ≤ v) as the rows of a v by k array E in such a way that every point occurs once in each column of the array E. Such an array is known as a Youden square; see, for example, [21, §VI.65].
A Youden square can be constructed from any SBIBD by using systems of distinct representatives. However, in the case where the SBIBD is generated from a difference set in an abelian group G, the Youden square occurs automatically if we arbitrarily order the base block and then generate the rest of the (ordered) blocks by developing the base block through the group G.
Suppose we use E as an encoding matrix for an authentication code. Thus, a key corresponds to a block in the design, or equivalently a row in E. The k sources are the k columns in E and the messages are the v points in the design. We assume that the sources are equiprobable.
It is not difficult to verify that this authentication code is (k−1)/(v−1)-secure against message-substitution and key-substitution attacks (see the proof of Theorem 4.3 for additional detail). It is also clear that this authentication code provides perfect secrecy; this follows immediately from Theorem 2.3 using the “Youden square” property of the authentication matrix. This construction is in fact a special case of [2, Theorem 5.5], extended to include the perfect secrecy property by using an appropriate ordering of the blocks, as described above.
Starting with this authentication code, we obtain from Theorem 3.1 an ϵ-secure (2, 2)-threshold scheme for k equiprobable secrets, where ϵ = (k − 1)/(v − 1). Summarizing, we have the following theorem.
Theorem 4.1
If there exists a (v, k, λ)-SBIBD, then there exists
an authentication code with perfect secrecy for k equiprobable sources that is (k−1)/(v−1)-secure against message-substitution and key-substitution attacks, and
a(k−1)/(v−1)-secure (2, 2)-threshold scheme for k equiprobable secrets, in which the share sets for both players have size v.
Example 4.1
A (7, 3, 1)-SBIBD is just a projective plane of order 2, often called the Fano plane. The seven blocks in the design can be obtained from the base block {0, 1, 3} by developing it in the group ℤ7. After ordering the blocks appropriately, we obtain the following Youden square.
| s1 | s2 | s3 |
| 0 | 1 | 3 |
| 1 | 2 | 4 |
| 2 | 3 | 5 |
| 3 | 4 | 6 |
| 4 | 5 | 0 |
| 5 | 6 | 1 |
| 6 | 0 | 2 |
This Youden square is the encoding matrix for an authentication code with perfect secrecy having
The corresponding (2, 2)-threshold scheme is (1/3)-secure and has the following 21 distribution rules:
| v1 | v2 | s |
| 0 | 0 | s1 |
| 1 | 1 | s1 |
| 2 | 2 | s1 |
| 3 | 3 | s1 |
| 4 | 4 | s1 |
| 5 | 5 | s1 |
| 6 | 6 | s1 |
| v1 | v2 | s |
| 0 | 1 | s2 |
| 1 | 2 | s2 |
| 2 | 3 | s2 |
| 3 | 4 | s2 |
| 4 | 5 | s2 |
| 5 | 6 | s2 |
| 6 | 0 | s2 |
| v1 | v2 | s |
| 0 | 3 | s3 |
| 1 | 4 | s3 |
| 2 | 5 | s3 |
| 3 | 6 | s3 |
| 4 | 0 | s3 |
| 5 | 1 | s3 |
| 6 | 2 | s3 |
Any deception carried out by P1 or P2 succeeds with probability 1/3. For example, suppose
We should note that the authentication codes and robust threshold schemes obtained from Theorem 4.1 are optimal in various senses. In the case of the authentication code, the impersonation and message-substitution attacks have success probability that is as small as possible, according to Massey’s bounds [13]. Also, the number of encoding rules (or keys) is as small as possible, from [15, Theorem 2.1].
For the threshold schemes, we have v possible shares, k possible secrets, and the scheme is ϵ-secure where ϵ = (k − 1)/(v − 1). This meets the bound proven in [1, Corollary 3.3]. In fact, as a result of our discussion above, we have shown the following strong characterization of these “optimal” robust (2, 2)-threshold schemes.
Theorem 4.2
There exists a (v, k, λ)-SBIBD if and only if there exists a(k − 1)/(v − 1)-secure (2, 2)-threshold scheme for k equiprobable secrets.
4.2 BIBDs
More generally, we can use any BIBD (i.e, not necessarily a symmetric BIBD) to construct an authentication code. It has also been shown that the resulting authentication codes can provide perfect secrecy if obvious numerical conditions are satisfied; for example, see [14, Theorem 6.4]. Here is a “classical” construction of authentication codes from BIBDs.
Theorem 4.3
Suppose there is a (v, b, r, k, λ)-BIBD where r ≡ 0 mod k. Then there is an authentication code for k equiprobable sources, having v messages and b equiprobable keys, which satisfies the following properties:
the code provides perfect secrecy, and
if r = k, then the optimal key-substitution attack has success probability (k − 1)/(v − 1), and if λ = 1, then the optimal key-substitution attack has success probability 1/k.
Proof. First, we order each block in such a way that each element occurs exactly r/k times in each position. To do this, the technique used in the proof of [14, Theorem 6.4] can be applied (the proof of [14, Theorem 6.4] assumed λ = 1, but the method can be generalized easily to arbitrary λ). Then, Theorem 2.3 shows that the resulting authentication code has perfect secrecy and
We now prove 3, which treats the special cases of (1) SBIBDs and (2) BIBDs with λ = 1. First, we look at authentication codes derived from an SBIBD. The encoding matrix has one occurrence of each message in each column. Suppose we replace any key Ki with any other key Kj. There are exactly λ messages that occur in both Ki and Kj, and each such message occurs in a different position in Ki and Kj. Thus the attack is successful if and only if the message m is one of these λ messages. The sources are equiprobable, so the success probability is λ/k = (k − 1)/(v − 1).
Suppose now that the code is derived from a BIBD with λ = 1. Suppose the attacker replaces a key K i with another key Kj. Observe that there is at most one message that occurs in both Ki and Kj. If Ki and K j contain no common message, or if they contain a common message in the same column, the attack will not succeed. Therefore the attacker should choose K j so that K i and K j contain a common message that occurs in different columns. Given a message m in row Ki, there are r − r/k = r(k − 1)/k rows in which m occurs in a different column than it does in Ki. Since λ = 1 and there are k messages in row Ki, the number of rows Kj such that Ki and K j contain a common message that occurs in different columns is precisely kr(k − 1)/k = r(k − 1). The optimal attack is to choose one of these r(k − 1) rows; the success probability is
□
Computing the success probability of a key-substitution attack is, in general, more complicated, as blocks of a BIBD might intersect in different numbers of points. There were two types of BIBDs considered in part 3 of Theorem 4.3. Suppose we then construct a robust (2, 2)-threshold scheme from the authentication code using the transformation given in Section 3. The success of modifying share v1 is quantified by the success of the key-substitution attack in the authentication code setting, whereas the success of modifying share v2 is the same as the success of the message-substitution attack in the authentication code setting. In general, the success probabilities of the two share-modification attacks will be different; however, if we start with an SBIBD, the probabilities are the same. Theorem 4.1 is fact just the specialization of Theorem 4.3 to symmetric BIBDs.
Applying Theorem 3.1, we have the following.
Theorem 4.4
If there exists a (v, k, 1)-BIBD, then there exists
an authentication code with perfect secrecy for k equiprobable sources that is (1/k)-secure against message-substitution and key-substitution attacks, and
a(1/k)-secure (2, 2)-threshold scheme for k equiprobable secrets.
Proof. We showed in Theorem 4.3 that the authentication code arising from a (v, k, 1)-BIBD is (k − 1)/(v − 1)-secure against message-substitution attacks and (1/k)-secure against key-substitution attacks. Since we have
if a (v, k, 1)-BIBD exists, the authentication code is (1/k)-secure against both attacks. Then the stated result follows directly from Theorem 3.1.
□
We note that the (2, 2)-threshold scheme arising from part 2. of Theorem 4.4 has share sets (for the two players) of different sizes, unless the BIBD is a projective plane.
4.3 External difference families
A construction for splitting authentication codes using external difference families (or EDFs) was given in [2]. First, we define EDFs. Let G be an additive abelian group of order n having identity 0. An (n, k, c, λ)-external difference family is a set of k c-subsets of G, say D1, . . . , D k, such that the following multiset equation holds.
That is, whenwe look at the differences of elements from different c-subsets in the EDF, we see every non-zero value occurring exactly λ times. Therefore, a necessary condition for existence of an (n, k, c, λ)-EDF is that the following equation holds:
The following theorem is a straightforward generalization of [2, Theorem 3.4], which only addressed the case λ = 1 and did not explicitly discuss key-substitution attacks.
Theorem 4.5
Suppose there is an (n, k, c, λ)-EDF. Then there is a c-splitting authentication code E for k equiprobable sources, having n messages and n equiprobable keys, such that
the code provides perfect secrecy,
the optimal key-substitution attack has success probability c(k − 1)/(n − 1).
Proof. We first specify an arbitrary ordering of the k c-subsets in the EDF and then we develop the EDF through the abelian group G, maintaining the same ordering (as is done in Example 4.2). This yields the encoding matrix of a c-splitting authentication code. In each column of the encoding matrix, we see exactly c occurrences of each element of G. From Theorem 2.3, we have perfect secrecy and
In a message-substitution attack, a message m is substituted with m′. There are precisely λ rows of E that contain m and m′ in different c-subsets; these are the keys for which the particular substitution will succeed. Also, there are kc rows that contain m. Since the sources are equiprobable, the probability of a successful message substitution is
by applying (5).
For a key-substitution attack, a key K is given to the attacker and the attacker must choose a different key K′. Because the encoding matrix is generated from an EDF, there is a value d ∈ G, d = 0, such that eK′(s) = eK(s) + d for all s. From this fact, it is not hard to see that
Hence, there are exactly λ messages m such that the attack where K is replaced by K ′ is successful. Since there are kc possible messages m ∈ μ(K), and these values of m are equally likely, the key-substitution attack has success probability λ/(kc) = c(k − 1)/(n − 1).
□
Observe that the values of
Example 4.2
The three sets {1, 7, 11}, {4, 7, 9}, {5, 16, 17} form a (19, 3, 3, 3)-EDF in ℤ19. We can develop these sets modulo 19 to obtain an encoding matrix, E, for a 3-splitting authentication code. See Figure 1.
An encoding matrix for a 3-splitting authentication code
The rows of E are indexed by K0, . . . , K18. The optimal success probability of a message-substitution attack or a key-substitution attack is 1/6. The code also has perfect secrecy.
An EDF also gives rise to a robust (2, 2)-threshold scheme by applying Theorem 3.1. The two share sets in the threshold scheme have the same size because the authentication code derived from the EDF has the same number of messages as keys.
Theorem 4.6
If there exists an (n, k, c, λ)-EDF, then there exists a c(k − 1)/(n − 1)-secure (2, 2)-threshold scheme for k equiprobable secrets, in which the share sets for both players have size n.
4.4 Splitting BIBDs
Splitting BIBDs were defined in [2]. A (v, u × c, 1)-splitting BIBD is a set system consisting of a set X of v points and a set 𝓑 of blocks of size uc, which satisfies the following properties:
each block B can be partitioned into u subsets of size c, which are denoted Bi, 1 ≤ i ≤ u, and
given any two distinct points x and y, there is a unique block B such that x ∈ Bi and y ∈ B j, where i ≠ j.
We note that (v, u × 1, 1)-splitting BIBD is the same thing as a (v, u, 1)-BIBD. A (v, u × c, 1)-splitting BIBD has replication number r and b blocks, where
Of course r and b must be integers if a (v, u × c, 1)-splitting BIBD exists.
The following definition is new. A (v, u × c, 1)-splitting BIBD is equitably ordered if the multiset equation
is satisfied for all i, 1 ≤ i ≤ u. If a splitting BIBD is equitably ordered, then it yields an authentication code with perfect secrecy, from Theorem 2.3.
It is shown in [22] that a (v, u × c, 1)-splitting BIBD can be equitable ordered only if
In the case c = 1, where a splitting BIBD is just a BIBD, the condition (6) is necessary and sufficient for the design to be equitably orderable. This fact follows from Theorem 4.3. However, when c > 1, it is not known if (6) is a sufficient condition for a splitting BIBD to be equitably orderable.
The following result is shown in [22].
Lemma 4.7
Suppose that a (v, u × c, 1)-splitting BIBD is generated by base blocks over an abelian group of order v, and suppose every orbit of blocks has size v. Then the splitting BIBD can be equitably ordered.
Example 4.3
A (25, 3 × 2, 1)-splitting BIBD is presented in [16]. It has points in ℤ25 and it is generated from the base block
If we order the base block as
and maintain this ordering as the block is developed, we obtain the blocks
This is an equitable ordering of the splitting BIBD.
It is also shown in [22] that some infinite families of splitting BIBDs that are constructed recursively can be equitably ordered. Specifically, the cases u = 2 and (u, c) = (3, 2), (3, 3), (3, 4) and (4, 2) are almost completely solved (with a small number of possible exceptions). See [22] for additional details.
Theorem 4.8
Suppose there is an equitably ordered (v, u × c, 1)-splitting BIBD. Then there is a c-splitting authentication code E for u equiprobable sources, having v messages and b = v(v − 1)/(u(u − 1)c2) keys, such that
the code provides perfect secrecy,
the optimal key-substitution attack has success probability 1 /(cu).
Proof. Part 1 follows from Theorem 2.3 because the splitting BIBD is equitably ordered. Part 2 is shown in [2, Theorem 5.5]. Part 3 is proven as follows. Suppose K is the given key. Fix any message m ∈ μ(K). Since the splitting BIBD is equitably ordered, there are
keys K ′ such that m ∈ eK(s)∩eK′(s′) with s ≠ s′. Since λ = 1, the number of keys K ′ ≠K such that there exists a message
The attacker should replace K by one of these v −1 keys. Since sources are equiprobable, the key-substitution attack will succeed with probability
□
Applying Theorem 3.1, we have the following.
Theorem 4.9
If there exists an equitably ordered (v, u × c, 1)-splitting BIBD, then there exists
a c-splitting authentication code with perfect secrecy for u equiprobable sources that is (1/cu)-secure against message-substitution and key-substitution attacks, and
a (1/cu)-secure (2, 2)-threshold scheme for k equiprobable secrets.
Proof. We showed in Theorem 4.8 that the authentication code arising from a (v, u × c, 1)-splitting BIBD is c(u − 1)/(v − 1)-secure against message-substitution attacks and (1/cu)-secure against key-substitution attacks. In the proof of Theorem 4.8 it is shown that b ≥ v, so
or
Hence the authentication code is (1/cu)-secure against both attacks and the stated result follows directly from Theorem 3.1.
□
5 Dual Authentication Codes
Suppose we have an authentication code with sources 𝒮, messages M, and keyspace 𝒦. The encoding matrix is denoted by E. Then we can construct another authentication code, which we call the dual code, by simply interchanging the roles of messages and keys. Thus, the encoding matrix of the dual code is the matrix F having entries
where s ∈ 𝒮 and m ∈ M. The keys in the dual code are the same as the messages in the original code.
It is not hard to see that a key-substitution attack in an authentication code is “equivalent” to a message-substitution attack in the dual code.
Theorem 5.1
A message-substitution attack in an authentication code is successful if and only if the corresponding key-substitution attack is successful in the dual authentication code.
Note that the probability of a “key” in the dual code is the same as the probability of the corresponding message in the original code. Thus, keys in the dual code will be equiprobable if and only if messages in the original code are equiprobable. In all the examples we consider, we will assume that condition 3. of Theorem 2.3 holds. This will ensure that a code and its dual both have equiprobable keys and messages.
Theorem 5.1 provides an alternative method to compute success probabilities of key-substitution attacks. We illustrate by reconsidering some of the constructions from Section 4, where we computed these success probabilities from first principles.
If we begin with an authentication code having an encoding matrix that is a (v, k, λ)-SBIBD, then the rows of the encoding matrix of the dual code, considered as sets, forms the dual design of the SBIBD. It is a classical result in design theory that the dual design of an SBIBD is again a (v, k, λ)-SBIBD. Thus, Theorem 5.1 provides a quick way to see that the optimal success probabilities of the key-substitution and message-substitution attacks are identical in this particular situation (as we showed previously in Theorem 4.1).
Example 5.1
We return to Example 4.1, where we constructed an authentication code from a (7, 3, 1)-SBIBD. We display the encoding matrices of the code and the dual code:
| E = | s1 | s2 | s3 |
| 0 | 1 | 3 | |
| 1 | 2 | 4 | |
| 2 | 3 | 5 | |
| 3 | 4 | 6 | |
| 4 | 5 | 0 | |
| 5 | 6 | 1 | |
| 6 | 0 | 2 |
| F = | s1 | s2 | s3 |
| K0 | K6 | K4 | |
| K1 | K0 | K5 | |
| K2 | K1 | K6 | |
| K3 | K2 | K0 | |
| K4 | K3 | K1 | |
| K5 | K4 | K2 | |
| K6 | K5 | K3 |
The rows of E are indexed by K0, . . . , K 6 and the rows of F are indexed by 0, . . . , 6. The rows of F comprise the blocks of the dual (7, 3, 1)-SBIBD.
Suppose we start with an authentication code E arising from an EDF and then we construct the dual authentication code, F. Let D1, . . . , D k be the c-subsets in the original EDF. It is not hard to see that the dual authentication code F is generated from the EDF consisting of the k sets − D1, . . . , −Dk. The dual authentication code F satisfies the same properties as E because it is also obtained from an (n, k, c, λ)-EDF. Thus we see immediately from Theorem 5.1 that the success probability of a key-substitution attack in E is c(k − 1)/(n − 1) (as we showed previously in Theorem 4.5).
To illustrate, we present a small example.
Example 5.2
We have already noted in Example 4.2 that the three sets {1, 7, 11}, {4, 7, 9}, {5, 16, 17} form a (19, 3, 3, 3)-EDF in ℤ19. We develop these sets modulo 19 to obtain the following encoding matrices for a 3-splitting authentication code and its dual code:
| E = | s1 | s2 | s3 |
| {1, 7, 11} | {4, , 9} | {5, 16, 17} | |
| {2, 8, 12} | {5, 7, 10} | {6, 17, 18} | |
| {3, 9, 13} | {6, 8, 11} | {7, 18, 0} | |
| ⋮ | ⋮ | ⋮ | |
| {0, 6, 10} | {3, 5, 8} | {4, 15, 16} |
| F = | s1 | s2 | s3 |
| {K8, K12, K18} | {K10, K13, K15} | {K2, K3, K14} | |
| {K9, K13, K0} | {K11, K14, K16} | {K3, K4, K15} | |
| {K10, K14, K1} | {K12, K15, K17} | {K4, K5, K16} | |
| ⋮ | ⋮ | ⋮ | |
| {K7, K11, K17} | {K10, K13, K15} | {K1, K2, K13} |
The rows of E are indexed by K0, . . . , K18 and the rows of F are indexed by 0, . . . , 18. We can view F as being generated from the EDF consisting of sets {8, 12, 18}, {10, 13, 15}, {2, 3, 14}.
Here is another example, which makes use of a BIBD with λ = 1 that is not a symmetric BIBD.
Example 5.3
We construct an authentication code from a (13, 3, 1)-BIBD. This design has r = 6, and ≡ 0 mod 3, so we can ensure that the corresponding authentication code has perfect secrecy. The 26 blocks of the design can be generated from the two base blocks {0, 1, 4} and {0, 2, 8} by developing them modulo 13. The 26 by 3 encoding matrix E of the code is as follows:
| s1 | s2 | s3 | s1 | s2 | s3 |
| 0 | 1 | 4 | 0 | 1 | 8 |
| 1 | 2 | 5 | 1 | 2 | 9 |
| 2 | 3 | 6 | 2 | 3 | 10 |
| 3 | 4 | 7 | 3 | 4 | 11 |
| 4 | 5 | 8 | 4 | 5 | 12 |
| 5 | 6 | 9 | 5 | 6 | 0 |
| 6 | 7 | 10 | 6 | 7 | 1 |
| 7 | 8 | 11 | 7 | 8 | 2 |
| 8 | 9 | 12 | 8 | 9 | 3 |
| 9 | 10 | 0 | 9 | 10 | 4 |
| 10 | 11 | 1 | 10 | 11 | 5 |
| 11 | 12 | 2 | 11 | 12 | 6 |
| 12 | 0 | 3 | 12 | 0 | 7 |
The dual code has the following 13 by 3 encoding matrix F:
| s1 | s2 | s3 |
| {K0, K13} | {K12, K25} | {K9, K18} |
| {K1, K14} | {K0, K13} | {K10, K19} |
| {K2, K15} | {K1, K14} | {K11, K20} |
| {K3, K16} | {K2, K15} | {K12, K21} |
| {K4, K17} | {K3, K16} | {K0, K22} |
| {K5, K18} | {K4, K17} | {K1, K23} |
| {K6, K19} | {K5, K18} | {K2, K24} |
| {K7, K20} | {K6, K19} | {K3, K25} |
| {K8, K21} | {K7, K20} | {K4, K13} |
| {K9, K22} | {K8, K21} | {K5, K14} |
| {K10, K23} | {K9, K22} | {K6, K15} |
| {K11, K24} | {K10, K23} | {K7, K16} |
| {K12, K25} | {K11, K24} | {K8, K17} |
As can be seen, the dual code is 2-splitting. The rows of E are indexed by K0, . . . , K 25 and the rows of F are indexed by 0, . . . , 12. Theorem 4.3 states that the optimal success probability of a key-substitution attack for E is 1/3. This is of course the same as the optimal success probability of a message-substitution attack for F, by Theorem 5.1.
We now explore some additional properties relating authentication codes to their duals.
Theorem 5.2
Suppose a c-splitting authentication code for u sources has b equiprobable keys, equiprobable message encoding, v messages, perfect secrecy, and
Proof. The proof of Theorem 2.3 establishes that equation (4) holds, i.e., every message m occurs bc/v times in each column s of the encoding matrix E. This immediately implies that the dual code is (bc/v)-splitting. Therefore the dual code is a (bc/v)-splitting authentication code for u sources having v equiprobable keys and equiprobable message encoding. Each “message” in the dual code occurs c times in each column s of F (where F is the the encoding matrix of the dual code). Therefore, from Theorem 2.3, the dual code has perfect secrecy and
□
We note that the hypotheses of Theorem 5.2 are satisfied whenever we construct an authentication code from an equitably ordered BIBD or splitting BIBD.
The authentication code presented in Example 5.3 satisfies the hypotheses of Theorem 5.2 with v = 13, b = 26, u = 3, c = 1. Thus, the dual code is 2-splitting with perfect secrecy, each “message” Ki occurs once in each column of F. The code and dual code both have
Summary and Discussion
Our goal in this paper has been to develop some theory to better understand various connections between authentication codes and threshold schemes, as well as how certain combinatorial designs can be used to construct these cryptographic objects. To this end, we have proven a simple direct equivalence of certain authentication codes and (2, 2)-threshold schemes. Further, we have introduced the notion of a key-substitution attack and observed that it is identical to a message-substitution attack in a “dual authentication code.”
We have already mentioned that robust (k, n)-threshold schemes are usually constructed by “combining” an algebraic object such as a difference set, EDF, or AMD code with a Shamir threshold scheme. These objects all live in a finite group and, consequently, the construction of the resulting threshold schemes is algebraic. The main equivalence result we have proven (Theorem 3.1) is a purely combinatorial result. It would be of interest to extend our equivalence theorem in some way to handle robust (k, n)-threshold schemes in a strictly combinatorial setting. There is a purely combinatorial analogue of Shamir threshold schemes—namely, orthogonal arrays—so this is perhaps possible.
Acknowledgement
D.R. Stinson’s research is supported by NSERC discovery grant RGPIN-03882.
References
[1] W. Ogata, K. Kurowawa and D.R. Stinson, Optimum secret sharing scheme secure against cheating, SIAM J. Discrete Math. 20 (2006), 79–95.10.1007/3-540-68339-9_18Search in Google Scholar
[2] W. Ogata, K. Kurowawa, D.R. Stinson and H. Saido, New combinatorial designs and their applications to authentication codes and secret sharing schemes, Discrete Math. 279 (2004), 383–405.10.1016/S0012-365X(03)00283-8Search in Google Scholar
[3] R. Cramer, Y. Dodis, S. Fehr, C. Padró and D. Wichs, Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors, Lecture Notes in Computer Science 4965 (2008), 471–488 (Eurocrypt 2008).10.1007/978-3-540-78967-3_27Search in Google Scholar
[4] M.B. Paterson and D.R. Stinson, Combinatorial characterizations of algebraic manipulation detection codes involving generalized difference families, Discrete Math. 339 (2016), 2891–2906.10.1016/j.disc.2016.06.004Search in Google Scholar
[5] M. Tompa and H. Woll, How to share a secret with cheaters, Journal of Cryptology 1 (1988), 133–138.10.1007/3-540-47721-7_20Search in Google Scholar
[6] M. Carpentieri, A. De Santis and U. Vaccaro, Size of shares and probability of cheating in threshold schemes, Lecture Notes in Computer Science 765 (1994), 118–125 (Eurocrypt ’93).10.1007/3-540-48285-7_10Search in Google Scholar
[7] K. Kurowawa, S. Obana andW. Ogata, t-cheater identifiable k, n threshold secret sharing schemes, Lecture Notes in Computer Science 963 (1995), 410–423. (CRYPTO ’95 Proceedings.)10.1007/3-540-44750-4_33Search in Google Scholar
[8] C. Blundo and A. De Santis, Lower bounds for robust secret sharing schemes, Information Processing Letters 63 (1997) 317–321.10.1016/S0020-0190(97)00135-XSearch in Google Scholar
[9] L. Cianciullo and H. Ghodosi, Improvements to almost optimum secret sharing with cheating detection, Lecture Notes in Computer Science 11049 (2018), 193–205 (IWSEC 2018).10.1007/978-3-319-97916-8_13Search in Google Scholar
[10] Y. Liu, Linear k, n secret sharing scheme with cheating detection, Security Comm. Networks 9 (2016), 2115–2121.10.1109/CIT/IUCC/DASC/PICOM.2015.287Search in Google Scholar
[11] D. Becerra and G. Vega, Secret sharing scheme with efficient cheating detection, In “NISS19: Proceedings of the 2nd International Conference on Networking, Information Systems & Security”, 2019, Article No. 5.10.1145/3320326.3320331Search in Google Scholar
[12] G.J. Simmons, Authentication theory / coding theory, Lecture Notes in Computer Science 196 (1985), 411–431. (CRYPTO ’84 Proceedings.)10.1007/3-540-39568-7_32Search in Google Scholar
[13] J.L. Massey, Cryptography—a selective survey, In “Digital Communications,” 1986, pp. 3–21.Search in Google Scholar
[14] D.R. Stinson, The combinatorics of authentication and secrecy codes, Journal of Cryptology 2 (1990), 23–49.10.1007/BF02252868Search in Google Scholar
[15] R.S. Rees and D.R. Stinson, Combinatorial characterizations of authentication codes II, Designs, Codes and Cryptography 7 (1996), 239–259.10.1007/BF00124515Search in Google Scholar
[16] G. Ge, Y. Miao and L. Wang, Combinatorial constructions for optimal splitting authentication codes, SIAM J. Discrete Math. 18 (2005), 663–678.10.1137/S0895480103435469Search in Google Scholar
[17] M. De Soete, New bounds and constructions for authentication/secrecy codes with splitting, Journal of Cryptology 3 (1991), 173–186.10.1007/BF00196910Search in Google Scholar
[18] C. Blundo, A. De Santis, K. Kurosawa and W. Ogata, On a fallacious bound for authentication codes, Journal of Cryptology 12 (1999), 155–159.10.1007/s001459900049Search in Google Scholar
[19] M. Liang, L. Ji and J. Zhang, Some new classes of 2-fold optimal or perfect splitting authentication codes, Cryptogr. Commun. 9 (2017) 407–430.10.1007/s12095-015-0179-9Search in Google Scholar
[20] M. Li, M. Liang, B. Du and J. Chen, A construction for optimal c-splitting authentication and secrecy codes, Designs, Codes and Cryptography 86 (2018), 1739–1755.10.1007/s10623-017-0421-xSearch in Google Scholar
[21] C.J. Colbourn and J.H. Dinitz, eds. Handbook of Combinatorial Designs, Second Edition. Chapman & Hall/CRC, 2007.10.1201/9781420010541Search in Google Scholar
[22] M.B. Paterson and D.R. Stinson. Algebraic manipulation detection codes and authentication codes with perfect secrecy. Preprint.Search in Google Scholar
© 2020 M. B. Paterson and D. R. Stinson, published by De Gruyter
This work is licensed under the Creative Commons Attribution 4.0 International License.
