We have formerly introduced Deep Random Secrecy, a new cryptologic technique capable to ensure secrecy as close as desired from perfection against unlimited passive eavesdropping opponents. We have also formerly introduced an extended protocol, based on Deep Random Secrecy, capable to resist to unlimited active MITM. The main limitation of those protocols, in their initial presented version, is the important quantity of information that needs to be exchanged between the legitimate partners to distill secure digits. We have defined and shown existence of an absolute constant, called Cryptologic Limit, which represents the upper-bound of Secrecy rate that can be reached by Deep Random Secrecy protocols. At last, we have already presented practical algorithms to generate Deep Randomness from classical computing resources. This article is presenting an optimization technique, based on recombination and reuse of random bits; this technique enables to dramatically increase the bandwidth performance of formerly introduced protocols, without jeopardizing the entropy of secret information. That optimization enables to envision an implementation of Deep Random Secrecy at very reasonable cost. The article also summarizes former results in the perspective of a comprehensive implementation.
We have formerly introduced Deep Random Secrecy, a new cryptologic technique capable to ensure secrecy as close as desired from perfection against unlimited passive eavesdropping opponents. We have also formerly introduced an extended protocol, based on Deep Random Secrecy, capable to resist to unlimited active MITM. The main limitation of those protocols, in their initial presented version, is the important quantity of information that needs to be exchanged between the legitimate partners to distill secure digits. We have defined and shown existence of an absolute constant, called Cryptologic Limit, which represents the upper-bound of Secrecy rate that can be reached by Deep Random Secrecy protocols. At last, we have already presented practical algorithms to generate Deep Randomness from classical computing resources. This article is presenting an optimization technique, based on recombination and reuse of random bits; this technique enables to dramatically increase the bandwidth performance of formerly introduced protocols, without jeopardizing the entropy of secret information. That optimization enables to envision an implementation of Deep Random Secrecy at very reasonable cost. The article also summarizes former results in the perspective of a comprehensive implementation.
We present a new idea to design perfectly secure information exchange protocol, based on so called Deep Randomness, which means randomness relying on hidden probability distribution. Such idea drives us to introduce a new axiom in probability theory, thanks to which we can design a protocol, beyond Shannon limit, enabling two legitimate partners, sharing originally no common private information, to exchange secret information with accuracy as close as desired from perfection, and knowledge as close as desired from zero by any unlimitedly powered opponent.
We present a new form of randomness, called "Deep Randomness", generated in such a way that probability distribution of the output signal is made unknowledgeable for an observer. By limiting, thanks to Deep Randomness, the capacity of the opponent observer to perform bayesian inference over public information to estimate private information, we can design protocols, beyond Shannon limit, enabling two legitimate partners, sharing originally no common private information, to exchange secret information with accuracy as close as desired from perfection, and knowledge as close as desired from zero by any unlimitedly powered opponent. We discuss the theoretical foundation of Deep Randomness, which lies on Prior Probability theory, introduced and developed by authors like Laplace, Cox, Carnap, Jefferys and Jaynes; and we introduce computational method to generate such Deep Randomness.
We have introduced in former work the concept of Deep Randomness and its interest to design Unconditionally Secure communication protocols. We have in particular given an example of such protocol and introduced how to design a Deep Random Generator associated to that protocol. Deep Randomness is a form of randomness in which, at each draw of random variable, not only the result is unpredictable bu also the distribution is unknown to any observer. In this article, we remind formal definition of Deep Randomness, and we expose two practical algorithmic methods to implement a Deep Random Generator within a classical computing resource. We also discuss their performances and their parameters.
Randomness plays a central role in computer science, in particular cryptography. Almost all cryptographic primitives depend crucially on randomness because randomness and unpredictability in secret keys provides the means for security. Usually one assumes that perfect randomness, a sequence of independently and uniformly distributed bits, are accessible to algorithms. This is a strong assumption. Physical sources of randomness are neither uniformly random, nor produce necessarily independent bits. Therefore, the aim of this thesis is to start from a realistic model of randomness, investigate notions of secrecy and their randomness requirements and finally find practical methods for generation of randomness that matches the requirements of cryptographic primitives. We consider a model of random source where the source output follows one distribution from a set of possible distributions, each with the property that the maximum probability of symbols is bounded and can not be arbitrarily close to 1. This model does not assume independence or uniformity of the output symbols, and is considered to be a realistic model of randomness. From this point, the thesis can be divided into two main parts: In the first part, considering various notions of information theoretic secrecy, a fundamental problem is to find the properties of randomness needed to achieve security in these notions. Traditional cryptographic protocols simply assume perfect randomness and build on this assumption. We explore the results that show secrecy can not be based on imperfect randomness that is not uniform or independent. Thus a line of work attempts to relax notions of secrecy in such a way that they can be constructed with non-perfect sources, and possibly require smaller key sizes. Yet they should match real life applications. An important work in this context is entropic security where the key size could be smaller than the message depending on message distribution. Inspired by this, we propose two relaxed notions of secrecy that are motivated by practical applications. In the first notion, motivated by an application in biometrics authentication, we propose guessing secrecy where the probability of guessing the message for a computational unbounded adversary with the best strategy remains the same when a ciphertext is given or when it is not. We compare the randomness requirements of guessing secrecy with stronger notions and show that in some cases such as key length, the requirements are the same. For key distribution however, we found a family of distributions that provide guessing secrecy but not perfect secrecy. In the second notion, we investigate randomness requirements of multiple message encryption. Considering a natural extension of secrecy definition to multiple messages, we show that independent keys are needed to encrypt each message. We then propose a relaxed notion in which the security of last message is more important than past messages, although the leakage of past messages is bounded using entropic security. By this assumption, we achieve smaller key length compared to indistinguishability, and comparable to key length for entropic security. This notion has applications such as location privacy. In the second part of the thesis, since secrecy crucially depends on perfect randomness, we investigate how perfect randomness can be practically generated, specifically from human game-play. Unlike many random number generators that assume independent or uniform random bits in the random source, we base our work on the realistic model of randomness. Our main observation is that human game-play has an element of randomness coming from the errors in their game-play which is the main entertaining factor of the game. We also observed that this game-play can distinguish among a group of people if the right features are collected from the game-play. We incrementally changed our game design until the distinguishability among a small population is maximized, and then run the experiments required to show the viability of this approach over a larger population. This approach can also provide a hard to delegate authentication property where a human could not emulate the behavior of another human even given statistical information about their game-play.
In this paper, we propose a new provably secure cryptosystem for two party communication that provides security in the face of new technological breakthroughs. Most of the practical cryptosystems in use today can be breached in the future with new sophisticated methods. This jeopardizes the security of older but highly confidential messages. Our protocol is based on the bounded storage model first introduced in [1]. The protocol is secure as long as there is bound on the storage, however large it may be. We also suggest methods to extend the protocol to unbounded storage models where access to adversary is limited. Our protocol is a substantial improvement over previously known protocols and uses short key and optimal number of public random bits size of which is independent of message length. The smaller and constant length of key and public random string makes the scheme more practical. The protocol generates key using elements of the additive groupZn. Our protocol is very generalized and the protocol in [1] is a special case of our protocol. Our protocol is a step forward in making provably secure cryptosystems practical. An important open problem raised in [2] was designing an algorithm with short key and size of public random stringO(B)whereBbounds the storage of adversary. Our protocol satisfies the conditions and is easy to implement.
In this thesis, a new practical method to realize one-time pad perfect secrecy for wireless \ncommunication is presented. Most commonly used security methods are based on cryp- tographic \ntechniques employed at the upper layers of a wireless network. These methods basically rely on the \ncomputational hardness of some mathematical problems. This com- putational complexity is vulnerable \nin nature due to fast-growing computational power of hardware technology, yet not taking into \naccount the revolution of Quantum computing in further future. Another core problematic issue \nexists in symmetric security systems; there is a deadlock between securing the channel and \nestablishing the shared key. We need the key for securing the channel, on the other hand, for \nsharing the key we need a secure channel. \n \nTo address such vulnerabilities, Physical Layer Security (PLS) has been widely studied in recent \nyears. PLS schemes build on the idea of turning unpredictable and random wire- less channel \ncharacteristics into a source for information-theoretic security. Information- theoretic security \nitself, relies on Shannon’s pioneer work . Shannon, inspired by one-time pad, also known as Vernam \ncipher, theoretically showed that the only unconditional per- fect secrecy system is a one-time pad \nwith a key at least as random as the plaintext, i.e., a system that uses a different random key to \ncipher any new plaintext. In PLS key genera- tion methods, legitimate parties alternately send \nprobe signals and estimate Channel State Information (CSI) of common random channel and then \nconvert enough amount of these estimates to secure shared keys. To achieve perfect secrecy, the key \ngeneration methods must meet the key randomness and Key Generation Rate (KGR) requirements of \ntheir specific cryptographic applications. \n \nIn this research a new practical system for achieving unconditional perfect secrecy is presented. \nOur system uses channel phase as the probing parameter to fully benefit from its uniform \ndistribution over [0, 2π]. It also uses an encryption method based on modulo- \n2π addition of phase values which is the perfect counterpart of XOR addition in binary one-time \npad. Moreover, by intentionally perturbing the wireless channel in vicinity of the transceiver \nantenna based on RF-mirrors structure, it produces different random phase values in each channel \nprobing, much faster than the inherent channel variation would do, resulting in dramatically higher \nKGR than any wide-band PLS scheme presented so far and realizing true perfect secrecy. Most \nimportantly, the focus of this research is a detailed practical algorithm for implementing the \nsystem as well as empirical results which makes \nour system the first channel-phase-based PLS scheme implementation, reported so far.