Often the key bits generated by physical random number generators are not realizations of jointly independent uniformly distributed random variables, which gives rise to the concept of “practical key secrecy”. For some physical random number generators this deviation is caused by the discreteness of time measured by electronic components. In this paper, for a physical random number generator model based on the interval scheme, we obtain bounds on the practical secrecy of keys taking into account the impact of measurement time discretization.
Often the key bits generated by physical random number generators are not realizations of jointly independent uniformly distributed random variables, which gives rise to the concept of “practical key secrecy”. For some physical random number generators this deviation is caused by the discreteness of time measured by electronic components. In this paper, for a physical random number generator model based on the interval scheme, we obtain bounds on the practical secrecy of keys taking into account the impact of measurement time discretization.
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.
There is growing interest in wireless security methods that provide strong or even perfect secrecy by taking advantage of features of the physical propagation channel. In advantage-based methods, high channel quality in an average or opportunistic sense is exploited between two legitimate nodes, such that nonzero secrecy capacity can be achieved. Since such methods require bounds on the quality of the eavesdropper channel, they are somewhat impractical. Secret key generation based on tracking channel evolution in time division duplex systems is a more attractive option, where two nodes generate secret key bits based on a mutually known random channel. Since the eavesdropper channel is typically independent of the legitimate channel, the key can only be broken by brute force attacks, which are difficult when new keys are continuously generated. In this paper, the information theoretic limits of key generation schemes are investigated, based on the level of estimation error, temporal correlation, and dependence of the eavesdropper and legitimate channels. Three practical candidate key generation schemes are also considered: channel quantization and channel quantization with guardband.
The mathematical model of a binary discrete source is proposed, which is close to the practical conditions for the operation of cryptographic key generation devices. The model takes into account the non-stationarity of such devices, as well as the presence of statistical dependencies between their output bits. Within the framework of the model, an achievable and easily computable lower estimate of the practical secrecy of the key is obtained. It is shown that with certain parameters of the model, the assessment allows us to draw meaningful conclusions about the cryptographic quality of keys, while other well-known estimates do not cope with this.
Abstract In the process of quantum key distribution (QKD), the communicating parties need to randomly determine quantum states and measurement bases. To ensure the security of key distribution, we aim to use true random sequences generated by true random number generators as the source of randomness. In practical systems, due to the difficulty of obtaining true random numbers, pseudo-random number generators are used instead. Although the random numbers generated by pseudo-random number generators are statistically random, meeting the requirements of uniform distribution and independence, they rely on an initial seed to generate corresponding pseudo-random sequences. Attackers may predict future elements from the initial elements of the random sequence, posing a security risk to quantum key distribution. This paper analyzes the problems existing in current pseudo-random number generators and proposes corresponding attack methods and applicable scenarios based on the vulnerabilities in the pseudo-random sequence generation process. Under certain conditions, it is possible to obtain the keys of the communicating parties with very low error rates, thus effectively attacking the quantum key system. This paper presents new requirements for the use of random numbers in quantum key systems, which can effectively guide the security evaluation of quantum key distribution protocols.
Quantum random number generators can provide genuine randomness by appealing to the fundamental principles of quantum mechanics.In general, a physical generator contains two parts-a randomness source and its readout.The source is essential to the quality of the resulting random numbers; hence, it needs to be carefully calibrated and modeled to achieve information-theoretical provable randomness.However, in practice, the source is a complicated physical system, such as a light source or an atomic ensemble, and any deviations in the real-life implementation from the theoretical model may affect the randomness of the output.To close this gap, we propose a source-independent scheme for quantum random number generation in which output randomness can be certified, even when the source is uncharacterized and untrusted.In our randomness analysis, we make no assumptions about the dimension of the source.For instance, multiphoton emissions are allowed in optical implementations.Our analysis takes into account the finite-key effect with the composable security definition.In the limit of large data size, the length of the input random seed is exponentially small compared to that of the output random bit.In addition, by modifying a quantum key distribution system, we experimentally demonstrate our scheme and achieve a randomness generation rate of over 5 × 10 3 bit=s.
Random number generators are important devices in randomized algorithms, Monte-Carlo methods, and in simulation studies of random systems. A random number generator is usually modeled as a random source emitting independent, equally likely random bits. In practice, the random source one has at hand can deviate from this idealized model, and the random number generator operates by applying a deterministic mapping on the output of the (nonideal) random source. The deterministic mapping is chosen so that the resulting process approximates, in some sense, a sequence of independent, equally likely random bits. A prime measure of the intrinsic randomness of a given source X is the maximal rate at which random bits can be extracted from X by suitably mapping its output. This maximal rate depends on the statistics of the source X and on the sense of approximation. We study the problem of finite-precision random bit generation, where the accuracy measure is the variational distance. The relevant information theory is addressed.