# Synthesis of Sources of Common Randomness Based on Keystream Generators with Shared Secret Keys
## 4 Information-Theoretic Analysis of the Source of Common Randomness Based on KSG(Kg)  
**Theorem 1**. : _Let the set of information available to [PERSON] over the public channel during the execution of the IR phase of an SKD protocol be denoted as \(S=\{S_{i}\}\), \(/S/=n_{p}\), where_  
\[S_{i}=\sum_{j=1}^{N_{i}}Y_{j}.m_{ij}. \tag{18}\]  
_Let \(m_{i}\) denote the binary vector--mask associated with each \(S_{i}\), of the form_\[m_{i}=\left[m_{i1},\ m_{i2},\ \ldots,\ m_{iN_{i}}\right],\ m_{ij}\in\{0,1\}. \tag{19}\]  
_Then, the lower bound on the equivocation of the secret key of \(KSG(K_{G})\), based on observations from the public channel, is given by_  
\[H\Big{(}K_{G}\mid S_{1},\ S_{2},\ldots,\ S_{n_{p}}\Big{)}\geq|K_{G}|-n_{p} \Bigg{(}1-\frac{1}{n_{p}}\sum_{i=1}^{n_{p}}h_{b}(\varepsilon_{i})\ \Bigg{)} \tag{20}\]  
\[\varepsilon_{i}=\frac{1}{2}\bigg{(}1-(1-2\varepsilon)^{\sum_{j=1}^{N_{i}}m_{ ij}}\bigg{)} \tag{21}\]  
_where \(\varepsilon\) is the parameter of the Bernoulli distribution \(B(\varepsilon)\), of the random variable \(X\), and \(h_{b}\) denotes the binary entropy function_  
\[h_{b}(x)=-plog(p)-(1-p)log(1-p),\ p\in(0,1). \tag{22}\]  
**Proof of Theorem 1. ** According to [36], for every symmetric cipher system \(\{K,\ X,\ Y\}\), where \(K\) is the secret key, \(X\) is the message, and \(Y\) is the ciphertext, the following holds  
\[H(K\mid Y)=H(K)+H(X)-H(Y). \tag{23}\]  
Based on Equation (18), it follows that  
\[S_{i}=\sum_{j=1}^{N_{i}}\big{(}X_{j}\oplus C_{j}\big{)}\cdot m_{ij}=\sum_{j=1} ^{N_{i}}X_{j}\cdot m_{ij}\oplus\sum_{j=1}^{N_{i}}C_{j}\cdot m_{ij}=\tilde{X}_{ i}\oplus\tilde{C}_{i}. \tag{24}\]  
Therefore, the observations \(S_{i}\) on the public channel can be regarded as the ciphertext of an equivalent cipher system \(\left\{K_{G},\tilde{X}_{i},S_{i}\right\}\), given that each sequence \(\tilde{C}_{i}\) is generated by the corresponding \(KSG_{i}(K_{G})\) using the same secret key \(K_{G}\). The entropy of the equivalent plaintext \(\tilde{X}_{i}\) is given by  
\[ \begin{array}{c}H\Big{(}\tilde{X}_{i}\Big{)}=H\Big{(}\sum_{j=1}^{N_{i}}X_{j }\cdot m_{ij}\Big{)}=h_{b}(\varepsilon_{i})\,\\ \varepsilon_{i}=\frac{1}{2}\bigg{(}1-(1-2\varepsilon)^{\sum_{j=1}^{N_{i}}m_{ ij}}\bigg{)}.\end{array}  \tag{25}\]  
Namely, Equation (25) directly follows from the fact that \(\tilde{X}_{i}\) is the sum \(\sum_{j=1}^{N_{i}}m_{ij}\) of i.i.d. random variables \(X_{j}\) distributed according to \(B(\varepsilon)\); see for example proofs in [37; 38]. If the observations \(\{S_{i}\}\) on the public channel are considered as the ciphertext of the cipher system \(\{K_{G},\ X,\ S\}\), then the following equalities hold  
\[ \begin{array}{c}H(K_{G}\mid S_{1})=H(K_{G})+h_{b}(\varepsilon_{1})-H(S_{1}), \\ H(K_{G}\mid S_{2})=H(K_{G})+h_{b}(\varepsilon_{2})-H(S_{2}),\\................................................\ \\ H\Big{(}K_{G}\mid S_{n_{p}}\Big{)}=H(K_{G})+h_{b}\big{(}\varepsilon_{n_{p}} \big{)}-H\big{(}n_{p}\big{)}.\end{array}  \tag{26}\]  
The sum of these equations results in  
\[\sum_{i=1}^{n_{p}}H(K_{G}\mid S_{i})=n_{p}H(K_{G})+\sum_{i=1}^{n_{p}}h_{b}( \varepsilon_{i})-\sum_{i=1}^{n_{p}}H(S_{i}). \tag{27}\]  
Given that \(S_{i}\) are mutually independent, the following holds  
\[\sum_{i=1}^{n_{p}}H(K_{G}\mid S_{i})=H\Big{(}K_{G}\mid S_{1},\ S_{2},\ \ldots,\ S_{n_{p}}\Big{)}-\big{(}n_{p}-1\big{)}H(K_{G}). \tag{28}\]which, by substitution into (27), gives  
\[H\Big{(}K_{G}\mid S_{1},S_{2},\ldots,S_{n_{p}}\Big{)}=H(K_{G})+\sum_{i=1}^{n_{p}} h_{b}(\varepsilon_{i})-\sum_{i=1}^{n_{p}}H(S_{i}). \tag{29}\]  
Bearing in mind that the entropy satisfies the inequality \(H(S_{i})\leq 1\), we obtain  
\[H\Big{(}K_{G}\mid S_{1},\ S_{2},\ldots,\ S_{n_{p}}\Big{)}\geq|K_{G}|+\sum_{i=1 }^{n_{p}}h_{b}(\varepsilon_{i})-n_{p}. \tag{30}\]  
which proves the claim (20) of the theorem. This completes the proof.