# Quantum Key Distribution with Post-Processing Driven by Physical Unclonable Functions
## Appendix A The Size of the Pre-Shared Key
### Message Authentication
[PERSON] and [PERSON] have shown that one can have a one-time \(2/|\mathbb{T}|-\)secure MAC with a key length that scales linearly with the length of the tag and logarithmically with the length of the message [16; 17], i.e.,  
\[|k|\simeq 4\log_{2}(|\mathbb{T}|)\log_{2}[\log_{2}(\mathbb{M})]. \tag{2}\]  
In the framework of QKD, we usually deal with binary messages, key and tags, and in this case, this expression reads  
\[|k|\simeq 4|\tau|\log_{2}(|m|), \tag{3}\]  
where \(|\tau|\) and \(|m|\) denote the lengths of the tag and the message, respectively. Accordingly, the security of the WCA scheme is  
\[\varepsilon=2^{-|\tau|+1} \tag{4}\]  
A family of \(\varepsilon-\)ASU\({}_{2}\) hash functions can be also constructed efficiently by means of Toeplitz matrices [18]. In this case, the tag \(\tau\) is obtained by multiplication of a \(|\tau|\times|m|\) Toeplitz matrix with the message \(m\). The elements of the matrix are either \(0\) or \(1\), whereas the matrix is uniquely identified by a binary string of length \(|\tau|+|m|-1\) which determines the elements of the first column and the first row. In the authentication scheme discussed by [PERSON], the tag is also encrypted by means of an OTP encryption with \(|\tau|-\)bit random key. This authentication scheme is \(1\)-time \(\varepsilon\)-secure, with [16; 18]  
\[\varepsilon=\frac{2|m|}{2^{|\tau|}}+\frac{1}{2^{|\tau|}}. \tag{5}\]for key length \(|k|>3|\tau|\) or else \(|k|>3\log(\varepsilon)\). As mentioned above, throughout this work we assume that channel authentication takes place in the key sifting, the error verification, and the privacy amplification [11]. Let \(\varepsilon^{\rm(ks)}\), \(\varepsilon^{\rm(ev)}\), and \(\varepsilon^{\rm(pa)}\) denote the corresponding deception probabilities. In view of the union bound, the overall probability of undetected failure (failure of security) for the QKD protocol is bounded from above as follows  
\[P_{\rm fail}\leq P_{\rm fail}^{\rm(auth)}+P_{\rm fail}^{\rm(other)}, \tag{10}\]  
where the first term refers to the probability of failure due to the authentication in these phases of the post-processing, and the second term refers to the failure due to other reasons. The former probability is related to the aforementioned deception probabilities for the phases involving authentication. The deception probabilities must be as low as possible so that the overall probability for the QKD to undergo an undetected failure is very small. For instance, asking for the right-hand side of the inequality to be equal to \(10^{-9}\) so that \(P_{\rm fail}\leq 10^{-9}\), we need \(\varepsilon^{\rm(ks)}\), \(\varepsilon^{\rm(ev)}\), \(\varepsilon^{\rm(pa)}<10^{-9}\simeq 2^{-30}\). Recalling Theorem 1 for \(\varepsilon=2^{-30}\), we have that the required key length for each authentication session satisfies \(|k^{(j)}|>60\) bits. Under these conditions, the total length of the pre-shared key required for ITS authentication in QKD should satisfy  
\[|k_{\rm auth}|\geq 2|k^{\rm(ks)}|+|k^{\rm(ev)}|+|k^{\rm(pa)}|>240\;{\rm bits}, \tag{11}\]  
where we have taken into account the fact that the service channel has to be authenticated both ways in the case of key sifting [11]. This is a low bound on the required key length, which is independent of the applied ITS MAC, as Theorem 1 is very general and depends only on the value of \(\varepsilon\). More tight bounds can be obtained by considering specific authentication schemes, such as the ones mentioned above. Taking into account the typical key lengths required for error reconciliation, the total length of the pre-shared key in a typical QKD protocol may increase considerably. Unconditionally secure \(l\)-time \(\varepsilon\)-secure MACs for \(l\gg 1\) typically require very long keys. MACs that rely on block ciphers or collision resistant hash functions may require considerably smaller keys, but they offer computational security only [44], thereby affecting the security of the entire QKD protocol.