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.
The fast progress of quantum computing is a serious threat to classical cryptographic schemes like RSA and elliptic curve cryptography, and it is time to come up with safe postquantum schemes.One of the new solutions is isogeny-based cryptography which has attracted attention because of its good-security basis and comparatively small key sizes.Nevertheless, currently used post-quantum cryptographic (PQC) designs, such as lattice-based and codebased ones, are typically characterized by the high key sizes, high computational costs, or scaling issues, with the necessity to have a well-balanced and efficient cryptographic design.This paper presents a powerful isogeny-based cryptosystem, which can allow safe communication in the post-quantum context.The mathematical complexity of isogenies over supersingular elliptic curves forms the foundation of the proposed framework and it has a structured architecture comprising of parameterization, key generation, encryption/decryption and communication layers.The design of the optimization of algorithms to generate keys, exchange keys securely and encrypt messages using shared secret derivation mechanisms is part of the methodology.Security analysis is also carried out to assess the resistance to quantum attacks and against known cryptanalytic vulnerabilities.The metrics used to conduct performance evaluation are computed cost, key size, and latency, and the results are compared to typical PQC schemes, like lattice-based (Kyber) and code-based (McEliece) systems.The results show that the model proposed has much smaller key sizes (330 bytes public key) with moderate computational efficiency although a little bit more latency than lattice-based methods.
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.