This article bridges the gap between two topics used in sharing an encryption key: (i) Key Consolidation, i.e., extracting two identical strings of bits from two information sources with similarities (common randomness). (ii) Quantum-safe Key Encapsulation by incorporating randomness in Public/Private Key pairs. In the context of Key Consolidation, the proposed scheme adds to the complexity Eve faces in extracting useful data from leaked information. In this context, it is applied to the method proposed in [1] for establishing common randomness from round-trip travel times in a packet data network. The proposed method allows adapting the secrecy level to the amount of similarity in common randomness. It can even encapsulate a Quantum-safe encryption key in the extreme case that no common randomness is available. In the latter case, it is shown that the proposed scheme offers improvements with respect to the McEliece cryptosystem which currently forms the foundation for Quantum safe key encapsulation. [1] A. K. Khandani, "Looping for Encryption Key Generation Over the Internet: A New Frontier in Physical Layer Security," 2023 Biennial Symposium on Communications (BSC), Montreal, QC, Canada, 2023, pp. 59-64
This article bridges the gap between two topics used in sharing an encryption key: (i) Key Consolidation, i.e., extracting two identical strings of bits from two information sources with similarities (common randomness). (ii) Quantum-safe Key Encapsulation by incorporating randomness in Public/Private Key pairs. In the context of Key Consolidation, the proposed scheme adds to the complexity Eve faces in extracting useful data from leaked information. In this context, it is applied to the method proposed in [1] for establishing common randomness from round-trip travel times in a packet data network. The proposed method allows adapting the secrecy level to the amount of similarity in common randomness. It can even encapsulate a Quantum-safe encryption key in the extreme case that no common randomness is available. In the latter case, it is shown that the proposed scheme offers improvements with respect to the McEliece cryptosystem which currently forms the foundation for Quantum safe key encapsulation. [1] A. K. Khandani, "Looping for Encryption Key Generation Over the Internet: A New Frontier in Physical Layer Security," 2023 Biennial Symposium on Communications (BSC), Montreal, QC, Canada, 2023, pp. 59-64
Establishing secret common randomness between two or multiple devices in a network resides at the root of communication security. In its most frequent form of key establishment, the problem is traditionally decomposed into a randomness generation stage (randomness purity is subject to employing often costly true random number generators) and an information-exchange agreement stage, which relies either on public-key infrastructure or on symmetric encryption (key wrapping).\nThis dissertation has been divided into two main parts. In the first part, an algorithm called KERMAN is proposed to establish secret-common-randomness for ad-hoc networks, which works by harvesting randomness directly from the network routing metadata, thus achieving both pure randomness generation and (implicitly) secret-key agreement. This algorithm relies on the route discovery phase of an ad-hoc network employing the Dynamic Source Routing protocol, is lightweight, and requires relatively little communication overhead. The algorithm is evaluated for various network parameters, and different levels of complexity, in OPNET network simulator. The results show that, in just ten minutes, thousands of secret random bits can be generated network-wide, between different pairs in a network of fifty users.\nThe proposed algorithm described in this first part of this research study has inspired study of the problem of generating a secret key\nbased on a more practical model to be explored in the second part of this dissertation. Indeed, secret key establishment from common randomness has been traditionally investigated under certain limiting assumptions, of which the most ubiquitous appears to be that the information available to all parties comes in the form of independent and identically distributed (i.i.d.) samples of some correlated andom variables. Unfortunately, models employing the i.i.d assumption are often not accurate representations of real scenarios. A more capable model would represent the available information as correlated hidden Markov models (HMMs), based on the same underlying Markov chain. Such a model accurately reflects the scenario where all parties have access to imperfect observations of the same source random process, exhibiting a certain time dependency. In the second part of the dissertation , a computationally-efficient asymptotic bounds for the secret key capacity of the correlated-HMM scenario has been derived. The main obstacle, not only for this model, but also for other non-i.i.d cases, is the computational complexity. This problem has been addressed by converting the initial bound to a product of Markov random matrices, and using recent results regarding its convergence to a Lyapunov exponent.
A hybrid encryption scheme uses a key encapsulation mechanism (KEM) to generate and establish a shared secret key with the decrypter, and a secret key data encapsulation mechanism (DEM) to encrypt the data using the key that is established by the DEM. The decrypter recovers the key using the ciphertext that is generated by the KEM, and uses it to decrypt the ciphertext that is generated by the DEM.We motivate and propose hybrid encryption in correlated randomness model where all participants including the eavesdropper, have access to samples of their respective correlated random variables. We define information-theoretic KEM (iKEM), and prove a composition theorem for iKEM and DEM that allows us to construct an efficient hybrid encryption system in correlated randomness model, providing post-quantum security. The construction uses an information-theoretic one-way secret key agreement (OW-SKA) protocol that satisfies a new security definition, and a one-time symmetric key encryption system that can be implemented by XORing the output of a (computationally) secure pseudorandom generator with the message. We discuss our results and directions for future work.
Quantum information science has completely changed the way we think about and process information. From the simple realization that information is physical, we have been able to use the peculiar features of quantum mechanical phenomena to our advantage. Designing algorithms whose performance exceeds those running on classical computers, and performing secret communication whose security can actually be proven from sound assumptions are two main catalysts for the establishment of the field. This thesis discusses some progress in quantum key distribution and quantum randomness generation. Quantum key distribution, which is motivated by the increasing need to communicate securely, is on the verge of becoming an established technology. With the goal of extending the reach of quantum key distribution to more realistic scenarios, we present a study on reference-frame-independent protocols whose knowledge can help design more efficient protocols, and a framework to the security analysis of distributed-phase-reference protocols, which have been missing for many years. This allows these protocols to be used in practice against the most general adversary, although the key rate is rather pessimistic. In quantum randomness generation, the amount of extractable randomness from a quantum system depends on the level of trust or characterization of the devices; we present a study into such interaction. In the extreme situation of distrust, i.e. device-independent scenarios, we study the effect of the input randomness on the certifying power of such scenarios, and realize that one cannot amplify an arbitrary min-entropy source device-independently. Finally we discuss the amount of randomness in post-selected data, which has consequences on practical randomness generation protocols. The in depth study of randomness generation from quantum processes is well justified by the important role of randomness in modern computer science and other fields.
Current key sharing techniques rely on the hardness of solving a solvable, but complex, mathematical problem. This entails, in Information Theoretical sense, the encryption key is not secret, it can be found by solving the underlying mathemat-ical problem. Sensitive data we encrypt today using traditional techniques can be recorded by malicious parties and be deciphered in the future whenever improved hacking techniques and supporting computing technology permit. Information Theory proves the existence of methods for sharing of encryption keys that are unconditionally secure, but does not show how to bring such theoretical results to practical use. One of the central information theoretical approaches to key sharing is based on exploiting common randomness. This theoretical result states that if two dependent random variables,Aand B, are available at Alice and Bob, then, by communicating through a public channel betweenAand B, it is possible to securely share a key of size I(A;B). To bridge the gap between theory and practice, one needs a method to generate two sets of dependent random variables, one at Alice‘s side and the other one at the Bob’ side, as well as a method to extract two identical keys from these dependent random variables. This article presents a novel technique to achieve this goal over the Internet. Dependent random variables are generated by measuring packet travel times between Alice and Bob, and error-free key extraction from dependent random variables is realized by using a randomized Low Density Parity Check Code (LDPC). Through looping of packets between Alice and Bob, the mutual information between random variables is increased. Finally, methods are presented to measure the likelihood values required in decoding the underlying LDPC. It is shown that the key rate is approximately equal to0.5log9(4L2/(4L−1))≈0.5log2(L)whereLis the number of round trips (loops). Test results (based on measurements between distant nodes over the Internet) are presented, demonstrating the feasibility of the proposed technique. The proposed method is implemented entirely in software (through high-level programming, e.g., using C-language, at the application layer). This operation does not require modifying the underlying network.
In recent years, there has been a significant amount of research related to the development of quantum computers. If such a computer were to be built, it would be able to break existing public-key cryptosystems that are currently used for many purposes. This will seriously affect the privacy and integrity of digital communications, etc. That is why special attention is currently being paid to post-quantum cryptography, the main goal of which is the development of cryptographic systems that are protected from both quantum and classical attacks, and will also be able to interact with existing communication protocols and networks. In view of the significant importance of the practical application of directional encryption algorithms, at the international and state level, special attention was paid to the implementation of the proposed requirements for key encapsulation protocols. Key-establishment algorithms (KEA) form a common secret – the key for a symmetric encryption algorithm. The paper considers two KEA algorithms that use algebraic lattices: one of the finalists of the 3rd round Crystals-Kyber and the Skelya algorithm (DSTU 8961-2019). The Kyber algorithm first performs asymmetric encryption of a 32-byte message, and then generates a shared secret. The Skelya algorithm performs the same actions, but for asymmetric encryption, it uses messages of any length that do not exceed the maximum possible. That is why the last algorithm can be used not only as a KEA algorithm, but also as an asymmetric encryption algorithm. According to the NIST Security level, the Kyber algorithm provides cryptographic 1, 3, and 5 security levels, and the Rock algorithm provides cryptographic 3, 5, and 7 security levels. The cryptographic stability that is ensured for both algorithms is determined by a set of parameters. Thus, the purpose of this work is to review the details of the implementation of each of the mentioned algorithms, to compare the speed of the key generation, encapsulation and decapsulation algorithms for the Kyber and Skelya algorithms in terms of key data lengths, and the encapsulation result and computational complexity of both algorithms.
Most cryptographic primitives require randomness (for example, to generate secret keys). Usually, one assumes that perfect randomness is available, but, conceivably, such primitives might be built under weaker, more realistic assumptions. This is known to be achievable for many authentication applications, when entropy alone is typically sufficient. In contrast, all known techniques for achieving privacy seem to fundamentally require (nearly) perfect randomness. We ask the question whether this is just a coincidence, or, perhaps, privacy inherently requires true randomness? We completely resolve this question for information-theoretic private-key encryption, where parties wish to encrypt a b-bit value using a shared secret key sampled from some imperfect source of randomness [special characters omitted]. Our main result shows that if such n-bit source [special characters omitted] allows for a secure encryption of b bits, where b > log n, then one can deterministically extract nearly b almost perfect random bits from [special characters omitted]. Further, the restriction that b > log n is nearly tight: there exist sources [special characters omitted] allowing one to perfectly encrypt (log n – loglog n) bits, but not to deterministically extract even a single slightly unbiased bit. Hence, to a large extent, true randomness is inherent for encryption : either the key length must be exponential in the message length b, or one can deterministically extract nearly b almost unbiased random bits from the key. In particular, the one-time pad scheme is essentially "universal". Our technique also extends to related primitives which are sufficiently binding and hiding, including computationally secure commitments and public-key encryption.