# Synthesis of Sources of Common Randomness Based on Keystream Generators with Shared Secret Keys
## 7 Computational Complexity and Overhead Analysis
### Comparative Operational Complexity per Secret Key Bit in SKD Systems  
When comparing SKD architectures, the supreme criterion for practical viability is the operational complexity per distilled secret key bit under equivalent security guarantees. To enable a fair and insightful comparison, consider:  
* System A: A classical SKD system based on natural CR sources (e.g., wireless fading, biometric signals) requiring an AD phase to reduce Eve's correlation while increasing Alice-Bob correlation.
* System B (Proposed): An autonomous SKD system using a synthetic CR source created by combining a local Bernoulli random sequence with a keystream from a shared-key generator, \(KSG(K_{G})\). This architecture completely removes the need for \(AD\), operating with maximum intrinsic correlation and maximum second-order Renyi entropy.  
The AD phase in System A requires exponentially more initial raw data to achieve the same final block length \(n_{IR\_end}\) at the end of IR phase, particularly under high initial Eve-Alice correlations, see [1; 40]. The produced sequence has reduced second-order Renyi entropy, necessitating greater compression during PA to meet security parameters. System A typically undergoes a compression \(n_{IR\_end}\rightarrow\left|R(W_{i}|S=s)\right|\), [53] where, due to residual correlation with Eve side information \(\left|R(W_{i}|S=s)\right|\ll\max H(W_{i}|S=s)=\left|W_{i}\right|\), leading to a significantly lower yield of distilled secret bits per cycle.  
In contrast, System B ensures that the second-order Renyi entropy equals the maximal Shannon entropy for the reconciled sequence. This allows the PA step to operate with minimal compression \(n_{IR\_end}\to n_{IR\_end}-t\), where \(t=34\) is a fixed security margin independent of data block of length \(n\).  
As a result, for a reasonably large \(n_{IR\_end}\), the final distilled secret key length is close \(n_{IR\_end}\) in System B but can be dramatically smaller in System A.  
Given that both systems have similar complexity in IR (Winnow: \(O(n_{IR})\)) and PA (Toeplitz universal hash: \(O\big{(}n_{IR\_end}\text{log}\,n_{IR\_end}\big{)}\), see [54; 55]) the effective per-distilled-bit complexity for System A becomes significantly higher due to the necessity of AD, and reduced output length after PA.  
In contrast, System B requires only the additional cost of generating the keystream using \(KSG(K_{G})\), which can be efficiently implemented with \(\sim\)1-15 operations per generated keystream bit depending on the chosen KSG (AES, Grain, Trivium, etc.) and minimal additional RAM and energy overhead, see Table 3.  
Moreover, this advantage increases for System B as the initial Eve-Alice correlation in System A increases, further reducing System A's efficiency. Thus, the proposed architecture not only simplifies the protocol stack by eliminating the AD phase but also maximizes the effective key rate while minimizing operational and communication overheads, achieving superior efficiency for secure autonomous SKD in practical deployments.