The authentication code (A-code) is the one of the most fundamental cryptographic protocols in information-theoretic cryptography, and it provides information-theoretic integrity or authenticity, i.e., preventing information from being altered or substituted by the adversary having unbounded computational powers. In addition, it has a wide range of applications such as multiparty compu-tations and quantum key distribution protocols. The traditional A-code theory states that a good A-code is characterized as an A-code which satises equality of a lower bound on size of secret-keys, i.e., an A-code satisfying |K | = ϵ−2, where |K | is cardinality of the set of secret-keys and ϵ is the success probability of attacks of the adversary. However, good A-codes imply that secret-keys must be uniformly distributed. Therefore, if a non-uniformly random key is given, we cannot realize a good A-code by using it as a secret-key. Then, a natural question about this is: what is a good A-code having non-uniformly random keys? And, how can we design such a good A-code having non-uniformly random keys? To answer the questions, in this paper, we perform analysis of A-codes having non-uniformly random keys, and show the principle that guides the design for such good A-codes.
The authentication code (A-code) is the one of the most fundamental cryptographic protocols in information-theoretic cryptography, and it provides information-theoretic integrity or authenticity, i.e., preventing information from being altered or substituted by the adversary having unbounded computational powers. In addition, it has a wide range of applications such as multiparty compu-tations and quantum key distribution protocols. The traditional A-code theory states that a good A-code is characterized as an A-code which satises equality of a lower bound on size of secret-keys, i.e., an A-code satisfying |K | = ϵ−2, where |K | is cardinality of the set of secret-keys and ϵ is the success probability of attacks of the adversary. However, good A-codes imply that secret-keys must be uniformly distributed. Therefore, if a non-uniformly random key is given, we cannot realize a good A-code by using it as a secret-key. Then, a natural question about this is: what is a good A-code having non-uniformly random keys? And, how can we design such a good A-code having non-uniformly random keys? To answer the questions, in this paper, we perform analysis of A-codes having non-uniformly random keys, and show the principle that guides the design for such good A-codes.
In modern cryptography, information-theoretic security is formalized by means of some probability (e.g., success probability of adversary's guessing) or some information-theoretic measure (e.g., Shannon entropy), and the study on cryptographic protocols with information-theoretic security is one of effective applications of the probability theory, statistics, and information theory. In this paper, we study the blind authentication code (BA-code), a kind of information-theoretically secure authentication protocols, in which verifier's secret keys are not required. For realizing it, we utilize a unidirectional low-bandwidth auxiliary channel which is called a manual channel. Specifically, in this paper we propose a model, a security definition, and a construction of BA-codes in the manual channel model. Furthermore, we consider BA-codes in other models, i.e., the noisy channel model and the bounded storage model, in which no verifier's secret key is required.
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.
Cryptographic protocols, though used in a wide range of everyday tasks, are typically built for certain unrealistic ideal conditions in which the user is assumed to work. For example, one such condition that is implicitly assumed is that the user has perfect randomness that she can use as her cryptographic secret key. Another commonly made assumption is that the user runs her cryptographic tasks (such as encryption) on a device that is perfectly secure; that is, its internals are not tampered with or even observed by an adversary.
In this thesis, we focus on designing cryptographic techniques that are secure under less-than-ideal conditions. In order to remove the assumption that users share perfectly random secret keys, we study the problem of privacy amplification: key agreement between two parties who both know a weak secret w, such as a password. The goal of the protocol is to convert this non-uniform secret w into a uniformly distributed string R that is fully secret from the adversary. R may then be used as a key for running symmetric cryptographic protocols (such as encryption or authentication). Because we make no computational assumptions, the entropy in R can come only from w. Thus such a protocol must minimize the entropy loss during its execution, so that R is as long as possible. In this thesis, we present the first protocol for information-theoretic key agreement that has entropy loss linear in the security parameter. The result is optimal up to constant factors. We also extend our results to the case where the users share correlated secrets w and w' . This setting occurs, for example, when the secrets are biometric readings taken at different points of time and is more generally known as information-reconciliation.
This paper briefly deals with a wide range of topics in information-theoretic cryptography. First, we focus on the results on symmetric-key encryption and authentication codes, since these protocols are fundamental in the field and well studied in the frameworks by Shannon and Simmons, respectively. Secondly, we explain several existing assumptions and security criteria whose merit mainly lies in realizing cryptographic protocols with short/weak shared secret-keys, correlated weak secret-keys, or no shared secrets. Thirdly, we consider research themes by three aspects for further development of information-theoretic cryptography. Finally, we refer to trends of technical approaches in information-theoretic cryptography and explain our recent results brought by using the approach.
Post-quantum cryptography studies the security of classical, i.e. non-quantum cryptographic protocols against quantum attacks. Until recently, the considered adversaries were assumed to use quantum computers and behave like classical adversaries otherwise. A more conservative approach is to assume that also the communication between the honest parties and the adversary is (partly) quantum. We discuss several options to define secure encryption and authentication against these stronger adversaries who can carry out 'superposition attacks'. We re-prove a recent result of Boneh and Zhandry, stating that a uniformly random function (and hence also a quantum-secure pseudorandom function) can serve as a message-authentication code which is secure, even if the adversary can evaluate this function in superposition.
The use of wireless networks for communication has grown significantly in recent times, and continues to develop further. The broadcast nature of wireless communications makes them susceptible to a wide variety of security attacks. Unlike traditional solutions, which usually handle security at the application layer, the primary concern of this dissertation is to analyse and develop solutions for secure communication using channel coding techniques at the physical-layer. \nThe topic of physical layer authenticated encryption using high rate key generation through shared randomness is investigated in this work. First, a physical layer secret key generation scheme is discussed exploiting channel reciprocity in wireless systems. In order to address the susceptibility of this family of schemes to active attacks, a novel physical layer authentication encryption protocol is presented along with its extension to multi-node networks in the presence of active adversaries. Unlike previous work in the area of generating secret keys through shared randomness, it is demonstrated that the proposed scheme is semantically secure with respect to chosen plaintext and chosen cipher text attacks. \nSecondly, in order to increase the rate in bits per seconds at which agreed cryptographic keys are been generated, a multi-level quantization algorithm with public feedback is discussed. It is demonstrated that the proposed scheme is superior to direct information distillation approaches and can substantially increase the key generation rates even at low and medium SNRs. Furthermore, the employment of this low-overhead feedback at the information distillation process can largely simplify the information reconciliation process. \nThe proposed secret key generation schemes are tested for randomness such as required for cryptographic keys. The validation test is perfomed with the aid of National Institute of Standards and Technology (NIST) statistical test suite. The P-values obtained in each of the test carried out indicates that the key sequence generated by our algorithm is random.