Common use of Authentication Codes Clause in Contracts

Authentication Codes. Before we can discuss privacy amplification over a non-authentic public channel, authentication codes need to be studied, since these codes can provide unconditional authenticity for a public channel. First we introduce the terminology of authentication codes. A general authenti- cation code is a triple ( , , ) of finite sets and a map e : . Here is called the set of source states, which are pieces of information to be transmitted. For any specific s, s , which is called an encoding rule, the map e maps to a subset of , the set of messages, of size . An encoding rule is also called an authenti- cation key, and it is the common information shared by ▇▇▇▇▇ and ▇▇▇ beforehand, but ▇▇▇ has no access to it. There are two kinds of attacks. In an impersonation attack, ▇▇▇ inserts a message on the channel and impersonates the sender. In a substitution attack, ▇▇▇ replaces a correct message over the channel by a false one. The success probabilities for ▇▇▇ when trying these attacks are denoted by PI and PS, respectively. The probability of deception is defined by PD = max(PI, PS). For any authentication codes, we have the trivial inequalities PI ≥ |G| and PS ≥ |G|—1 . In the context of privacy amplification, ▇▇▇▇▇ randomly chooses a hash function, denoted by the random variable G, from a class of hash functions, and transfers it to Bob. As shown in Figure 3.1, the random variable G has the same length as S, the partially secret string used to generate the final secret. Since G does not necessarily need to be secret, authentication codes without secrecy are enough for privacy amplification against ▇▇▇’s active attacks. Therefore, we take interest in authentication codes where the messages carry all information about the source states. These kinds of authentication codes are called Cartesian codes, or systematic authentication codes, in analogy to systematic codes in coding theory. A Cartesian code is a triple ( , , ) of finite sets and a map ƒ : , where for any s and g , any message is of the form m = (g, x) with x = ƒ (g, s). The value x is called the tag or authenticator of g. According to Theorem 1 in [29], one has PS ≥ PI for Cartesian codes. Authentication codes with PI = |G| are optimal against the impersonation attack, and also called I-equitable authen|Mtic|ation codes. It is easy to see that any Cartesian I-equitable authentication code satisfies PD = PS ≥ 1/|X |. 3.3.1 Authentication Codes with Totally Secret Keys 3.3.1 Let ϵ > 0, H is ϵ-almost universal2 (or ϵ-AU2) if δH(a1, a2) ≤