# Quantum Key Distribution with Post-Processing Driven by Physical Unclonable Functions
## Appendix A The Size of the Pre-Shared Key
### Message Authentication  
Data integrity or message authentication is achieved by means of the so-called message authentication codes (MACs), and one can distinguish between ITS (or else unconditionally secure) and computationally secure MACs [12; 13; 14; 15; 16]. MACs that rely on block ciphers or collision-resistant hash functions offer computational security [12; 44], as opposed to the Wegman and Carter scheme, which exploits \(\varepsilon-\)Almost Strongly Universal\({}_{2}\) (\(\varepsilon-\)ASU\({}_{2}\)) hash functions and offers unconditional security [14; 15; 16; 17; 43]. Given that QKD protocols promise the highest level of security, the Wegman-Carter authentication (WCA) scheme has been widely employed in the post-processing of data [9]. In the WCA, [PERSON] and [PERSON] share a common secret key \(k\) uniformly distributed over \(\mathbb{K}\) and let \(\mathbb{H}:=\{h_{k}:k\in\mathbb{K}\}\) denote a publicly known set of \(\varepsilon-\)ASU\({}_{2}\) hash functions. The shared key identifies uniquely a hash function, which is used by the two users for hashing messages \(m\in\mathbb{M}\). In particular, when [PERSON] wants to send an authenticated message \(m\) to [PERSON], she evaluates the tag \(\tau\), through \(\tau:=h_{k}(m)\). The message and the tag \((m,\tau)\) are sent to [PERSON] in plain text over a classical channel. In general, as a result of forgery or noise, [PERSON] receives \((m^{\prime},\tau^{\prime})\) and he accepts the message only if \(\tau^{\prime}=h_{k}(m^{\prime})\). In the framework of a man-in-the-middle attack, [PERSON] intercepts the valid message-tag pair transmitted from [PERSON] to [PERSON], and her task is to produce another message-tag pair that will be accepted by [PERSON] as originated from [PERSON]. This is a _substitution_ or chosen-message attack, and the probability of [PERSON] succeeding is quantified by the deception probability \(P_{1}^{(\mathrm{D})}\). Of course, [PERSON] may always try to impersonate [PERSON] without having access to a valid message-tag pair, but in this case, the associated deception probability \(P_{0}^{(\mathrm{D})}\) is at most as large as \(P_{1}^{(\mathrm{D})}\). In general, an \(l\)-time \(\varepsilon\)-secure MAC is defined as follows. An MAC is \(l\)-time \(\varepsilon\)-secure, if for all (including unbounded) adversaries, \(P_{l}^{(\mathrm{D})}\leq\varepsilon\). The WCA scheme described above is one-time \(\varepsilon-\)secure, with \(\varepsilon\geq 1/|\mathbb{T}|\), where \(\mathbb{T}\) denotes the set of all possible tags. Various \(\varepsilon-\)ASU\({}_{2}\) hash functions have been proposed in the literature (e.g., see references in [14; 15; 16]), which achieve  
\[P_{0}^{(\mathrm{D})}=\frac{1}{|\mathbb{T}|},\quad P_{1}^{(\mathrm{D})}=\varepsilon. \tag{1}\]  
The precise value of the security parameter \(\varepsilon\) and the length of the key vary from scheme to scheme. One can readily show the following fundamental theorem [15; 17; 43]  
A \(1\)-time \(\varepsilon\)-secure MAC must have keys of length at least \(2|\log_{2}(\varepsilon)|\). To understand this theorem, one may consider the scenario discussed above, where [PERSON] obtains a valid message-tag pair. We ask for the probability of [PERSON] guessing the correct tag for any message to be at most \(\varepsilon\), even after she has seen the valid message-tag pair. This implies that the tags in total should have at least \(2|\log_{2}(\varepsilon)|\) bits of entropy. This entropy, however, can be obtained only from the key because the message is known. The theorem can be extended to any \(l\geq 1\).