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.
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.
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 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.
In this article, we discuss a naive method of randomness reduction for cryptographic schemes, which replaces the required perfect randomness with output distribution of a computationally secure pseudorandom generator (PRG). We propose novel ideas and techniques for evaluating the indistinguishability between the random and pseudorandom cases, even against an adversary with computationally unbounded attack algorithm. Hence the PRG-based randomness reduction can be effective even for informationtheoretically secure cryptographic schemes, especially when the amount of information received by the adversary is small. In comparison to a preceding result of Dubrov and Ishai (STOC 2006), our result removes the requirement of generalized notion of “nb-PRGs ” and is effective for more general kinds of protocols. We give some numerical examples to show the effectiveness of our result in practical situations, and we also propose a further idea for improving the effect of the PRG-based randomness reduction.
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.
Our objective in this thesis is to perform formal specification and automated validation of the class of protocols associated with quantum cryptography. Current analyses and proofs regarding quantum cryptographic protocols and their security are information-theoretic and also require in--depth understanding of the underlying physics. The alternative approach presented here involves the use of computer modelling languages and verification software. In particular, the logical model checker SPIN and the probabilistic model checker PRISM are used to analyse quantum key distribution, entanglement and quantum teleportation. The value of our approach lies not only in the fact that it is conceptually simpler than existing proofs, but in that it allows us to disambiguate protocol definitions and to assess their properties in various circumstances. By varying the values of certain parameters, different attacks on the protocols can be attempted and implementation-specific attributes can be analysed. The quantum key distribution protocol BB84 has been proved to be unconditionally secure against all types of eavesdropping. Although a general proof of this result is extremely hard to generate automatically, it is possible to develop specific protocol attacks and validate the protocol by computer. Assuming two types of eavesdropping attack (intercept-resend and random-substitute), we have used the PRISM tool to compute exactly the probability of successful eavesdropping, and found it to diminish as the number of transmitted qubits is increased. This result is linked to Mayers' security criteria for BB84. Also, we briefly describe a new quantum protocol definition language, named qSpec. The recent CQP process algebra, due to Nagarajan and Gay, is reviewed and examples of its application are provided. Alternative formalisms and validation tools are discussed, including QPAlg, PROBMELA and probUSM, the logic of knowledge and time for quantum systems due to Van der Meyden, and the QCSim simulator.
Randomness is crucial for a variety of applications, ranging from gambling to computer simulations, and from cryptography to statistics. However, many of the currently used methods for generating randomness do not meet the criteria that are necessary for these applications to work properly and safely. A common problem is that a sequence of numbers may look random but nevertheless not be truly random. In fact, the sequence may pass all standard statistical tests and yet be perfectly predictable. This renders it useless for many applications. For example, in cryptography, the predictability of a randomly" chosen password is obviously undesirable. Here, we review a recently developed approach to generating true | and hence unpredictable | randomness.