# Synthesis of Sources of Common Randomness Based on Keystream Generators with Shared Secret Keys
## 6 From Ideal Security Towards Perfect Security by SKD Based on CR KSG and Winnow IR Protocol  
The security of the proposed SKD based on the CR KSG relies on the ideality of the KSG in the Shannon sense [36]. In [PERSON]'s definition of an ideal system, it is important that the key equivocation is not reduced to zero with an unlimited increase in the available ciphertext [36]. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \(\left|K_{\mathbf{G}}\right|\) & \(\mathbf{r}\) & \(\mathbf{\Delta}_{\mathbf{K}_{G}}\) & \(\widetilde{\left|K_{s}\right|}_{max}\) & \(\mathbf{n}_{IR0}\) \\ \hline
256 & 0.500 & 128 & 0.0056 & 732 \\
512 & 0.250 & 128 & 0.1533 & 2194 \\
1024 & 0.125 & 128 & 0.1955 & 5118 \\
4096 & 0.031 & 128 & 0.2005 & 20,469 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Maximum effective secret key rate \(\widetilde{\left|K_{s}\right|}_{max}\) and the corresponding base block length \(n_{IR0}\), for typical values of key length \(\left|K_{G}\right|\) and a fixed security margin \(t=34\). Figure 10: Initial data block length \(n_{IR0}\) given in (85) as a function of \(r\) for various values of \(\left|K_{G}\right|\). Figure 9: The effective secrecy capacity \(\widetilde{\left|K_{S}\right|}\) given in (87) as a function of the parameter \(r\) for various values of \(\left|K_{G}\right|\). The security margin \(t\) is fixed at 34, according to explanation given in Remark 8. An extension of the original Shannon concept to the so-called Ideally Secret Autonomous Robust (ISAR) ciphering system was introduced in [23]. According to Definition 3, in [23], the ISAR ciphering system can maintain minimal key equivocation at a predefined value \(\Delta_{K}\), independently of the message's probability distribution and without an additional secret key distribution system. **Remark 11**. : _According to Theorem 1, common randomness block of proposed SKD based on CR KSG is an ISAR ciphering system, in which the ciphertext consists of all parity bits transmitted over the public channel. Therefore, an attack on the system aimed at reconstructing the key \(K_{G}\) faces an uncertainty on the order of \(2^{\Delta_{K_{G}}}\). In other words, the cryptanalyst is presented with \(2^{\Delta_{K_{G}}}\) equally probable hypothesis for the key \(K_{G}\)._  
Figure 11 illustrates an extension of the basic CR SKD System from Figure 1 to a system whose ultimate purpose is the generation of secret keys for the Vernam cipher [43], which is used to encrypt an independent message source \(M\). An intriguing question is whether and under what conditions this system can achieve perfect secrecy. To answer this question, it is necessary to prove the following theorem. **Theorem 6**. : _For the CR SKD system the following holds_  
\[H(W_{i}|S)=H(W_{i})\, \tag{88}\]  
\[R(W_{i}|S=s)=|W_{i}|. \tag{89}\]  
Proof. : The information from the public channel, \(S=\{S_{i}\}\), available to Eve, is always in the form of parity bits given by  
\[S_{i}=\sum_{j=1}^{N}Y_{j}\cdot m_{ij}\,\ m_{ij}\in\{0,1\} \tag{90}\]  
Figure 11: Perfectly secure system based on SKD by CR KSG and Winnow IR protocol. where \(m_{ij}\in\{0,1\}\) are the bits of the mask vector associated with \(S_{i}\), as indicated in Theorem 1, Formulas (18) and (19). After transmitting the bit \(S_{i}\), [PERSON] discards one bit from a known position \(j^{*}\) within the current block of length \(N\), as a result of which Equation (90) is transformed into equation  
\[\tilde{S_{i}}=\sum_{ \begin{subarray}{c}j=1\\ j\
eq j^{*}\end{subarray} }^{N}Y_{j}.m_{ij}. \tag{91}\]  
Equation (91) can also be written in the following equivalent form  
\[\tilde{S_{i}}=S_{i}\oplus Y_{j^{*}}. \tag{92}\]  
Since \(P\big{(}Y_{j^{*}}=1\big{)}=P\big{(}Y_{j^{*}}=0\big{)}=0.5\), knowing the parity bit \(S_{i}\) does not provide any information about \(\overline{S}_{i}\) of the remaining bits. After the completion of the IR protocol, the sequence \(W_{i}\) consists only of the bits that remain after the exclusion of the bits at positions \(j^{*}\).