Quantum cryptography, or quantum key distribution (QKD), provides a means of unconditionally secure communication. The security is in principle based on the fundamental laws of physics. Security proofs show that if quantum cryptography is appropriately implemented, even the most powerful eavesdropper cannot decrypt the message from a cipher. The implementations of quantum crypto-systems in real life may not fully comply with the assumptions made in the security proofs. Such discrepancy between the experiment and the theory can be fatal to the security of a QKD system. In this thesis we address a number of these discrepancies. A perfect single-photon source is often assumed in many security proofs. However, a weak coherent source is widely used in a real-life QKD implementation. Decoy state protocols have been proposed as a novel approach to dramatically improve the performance of a weak coherent source based QKD implementation without jeopardizing its security. Here, we present the first experimental demonstrations of decoy state protocols. Our experimental scheme was later adopted by most decoy state QKD implementations. In the security proof of decoy state protocols as well as many other QKD protocols, it is widely assumed that a sender generates a phase-randomized coherent state. This assumption has been enforced in few implementations. We close this gap in two steps: First, we implement and verify the phase randomization experimentally; second, we prove the security of a QKD implementation without the coherent state assumption. In many security proofs of QKD, it is assumed that all the detectors on the receiver's side have identical detection efficiencies. We show experimentally that this assumption may be violated in a commercial QKD implementation due to an eavesdropper's malicious manipulation. Moreover, we show that the eavesdropper can learn part of the final key shared by the legitimate users as a consequence of this violation of the assumptions.

Quantum cryptography, or quantum key distribution (QKD), provides a means of unconditionally secure communication. The security is in principle based on the fundamental laws of physics. Security proofs show that if quantum cryptography is appropriately implemented, even the most powerful eavesdropper cannot decrypt the message from a cipher. The implementations of quantum crypto-systems in real life may not fully comply with the assumptions made in the security proofs. Such discrepancy between the experiment and the theory can be fatal to the security of a QKD system. In this thesis we address a number of these discrepancies. A perfect single-photon source is often assumed in many security proofs. However, a weak coherent source is widely used in a real-life QKD implementation. Decoy state protocols have been proposed as a novel approach to dramatically improve the performance of a weak coherent source based QKD implementation without jeopardizing its security. Here, we present the first experimental demonstrations of decoy state protocols. Our experimental scheme was later adopted by most decoy state QKD implementations. In the security proof of decoy state protocols as well as many other QKD protocols, it is widely assumed that a sender generates a phase-randomized coherent state. This assumption has been enforced in few implementations. We close this gap in two steps: First, we implement and verify the phase randomization experimentally; second, we prove the security of a QKD implementation without the coherent state assumption. In many security proofs of QKD, it is assumed that all the detectors on the receiver's side have identical detection efficiencies. We show experimentally that this assumption may be violated in a commercial QKD implementation due to an eavesdropper's malicious manipulation. Moreover, we show that the eavesdropper can learn part of the final key shared by the legitimate users as a consequence of this violation of the assumptions.

This thesis extends the applicability of quantum cryptography. First, we prove that quantum cryptography at least equals classical cryptography in an important area, namely authentication. The quantum key distribution protocols presented here show that, contrary to previous belief, authentication can be done with quantum methods only. In addition, we have designed quantum security systems in unconventional settings. The security of sensor networks poses specific challenges, as the sensor nodes in particular can be physically picked up by the intruder. Our scheme protects both the integrity of the communication messages and it also protects the identity of the nodes, such that a reading intrusion of a node is detectable. The problem of access control in a hierarchy refers to a large number of users, organized in a hierarchy, having selective access rights to a database. Our quantum solution introduces quantum keys to the effect that the cryptographic scheme is dynamically adaptable to changes in the user structure, and it exhibits increased security levels. To the best of our knowledge, this thesis is the first to introduce quantum keys, that is secret keys defined by an array of qubits. We show that quantum keys make it possible for two parties to communicate with one-time pads without having to meet in advance. Also, opposite to previous cryptographic ``common sense", the security level of a quantum cryptosystem with quantum keys and quantum messages increases while being used, meaning the security increases over time. / Thesis (Ph.D, Computing) -- Queen's University, 2010-03-12 11:38:07.086

This thesis explains low temperature operation of an InGaAs Avalanche Photo Diode (APD) cooled using thermoelectric coolers in order to utilize in the quantum cryptographic applications. A theoretical background for the equipment used in the experiment was provided. Circuitry and mechanics used for the low temperature operation were designed. Performance measures for APD were explained and experiment results were presented.

A mix of physics, mathematics, and computer science, the study of quantum information seeks to understand and utilize the information that can be held in the state of a quantum system. Quantum cryptography is then the study of various cryptographic protocols on the information in a quantum system. One of the goals we may have is to verify the integrity of quantum data, a process called quantum message authentication. In this thesis, we consider two quantum message authentication schemes, the Clifford code and the trap code. While both of these codes have been previously proven secure, they have not been proven secure in the simulator model, with an efficient simulation. We offer a new class of simulator that is efficient, so long as the adversary is efficient, and show that both of these codes can be proven secure using the efficient simulator. The efficiency of the simulator is typically a crucial requirement for a composable notion of security. The main results of this thesis have been accepted to appear in the Proceedings of the 9th International Conference on Information Theoretic Security (ICITS 2016).

Orientador: Ricardo Dahab / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T11:38:01Z (GMT). No. of bitstreams: 1 OnikiChiquito_Izumi_M.pdf: 3419663 bytes, checksum: 5f621e251ebc62429a85ff141091f7f5 (MD5) Previous issue date: 2012 / Resumo: Na área de Segurança da Informação, controle de acesso diz respeito á habilidade de permitir ou negar a utilização de determinados recursos, sejam eles informações, dispositivos, serviços etc., por parte de um indivíduo. Protocolos de identificação correspondem a algoritmos criptográficos que permitem verificar, com certo grau de confiança, se a alegação de um indivíduo a respeito de sua identidade é verdadeira. Dessa forma, pode-se prover acesso controlado e conceder privilégios de utilização de recursos somente a entidades ou indivíduos cuja identidade tenha sido comprovada. Algoritmos baseados em reticulados, de uma forma geral, têm despertado particular interesse em aplicações criptográficas, devido à sua provável resistência a ataques empregando computadores quânticos, ao contrário dos criptossistemas baseados em problemas da Teoria dos Números. Por esse motivo, nos _últimos anos, tem-se buscado desenvolver protocolos de identificação cuja segurança esteja relacionada a problemas envolvendo reticulados. Neste trabalho, foram abordadas as principais propostas recentes de protocolos de identificação baseados em reticulados. Além da apresentação dos algoritmos, é feita uma análise comparativa entre protocolos selecionados, incorporando dados experimentais de execução. A etapa de implementação aqui apresentada tem também como finalidade suprir a ausência de resultados experimentais para essa categoria de protocolos, no sentido de iniciar um processo de validação para uso dos algoritmos em aplicações práticas. Questões como possibilidades de otimização e expectativas para o futuro da área também são discutidas / Abstract: One of the main concerns of the field of Information Security is access control, which refers to the restriction of access to several kinds of resources, such as data, places, devices, services and others. Identification schemes are cryptographic algorithms that allow verifying with some level of certainty if an identity claim is legitimate. Therefore, such schemes make possible to provide access control and grant privileges only to authorized individuals whose identities have been previously verified. Lattice-based algorithms are particularly interesting as the cryptography community believes them to remain secure even to quantum computers attacks, as opposite to some cryptosystems used today based on Number Theory problems. For this reason, identification schemes based on lattices have received growing attention lately. In this work, we address the main recent developments of lattice-based identification schemes. After introducing the algorithms, we make a comparative analysis of the selected schemes, using experimental data collected from our own implementation of the algorithms. The implementation phase also aims to help validating these schemes for practical use, since to this date there were practically no experimental results available. Other issues, like optimization possibilities and the future of the area, are also addressed in this work / Mestrado / Ciência da Computação / Mestra em Ciência da Computação

Many unique attributes of quantum cryptography arise from the no-cloning property of quantum information. We study this using two closely-related types of uncloneability game: no-cloning and monogamy-of-entanglement games. In a no-cloning game, a referee sends a quantum state encoding classical information to two cooperating players who split the state, then try simultaneously guessing the information, provided the key. In a monogamy-of-entanglement game, two cooperating players try to guess the referee's measurement result on a tripartite state the players prepared. In this work, we prove winning probability bounds on no-cloning games based on coset states, which have the interesting property that the players guess two different strings. We also show a rigidity property for the original monogamy-of-entanglement game, letting it be used as a test of separability. Finally, we apply these properties to construct a variety of novel cryptographic protocols for uncloneable encryption, quantum key distribution, bit commitment, and randomness expansion.

One attractive feature of lattice-based cryptosystems is the existence of security reductions relating the difficulty of breaking the cryptosystem to the difficulty of solving variants of the shortest vector problem (Regev, STOC 2005; Peikert, ePrint 2008). As there are no known polynomial-time algorithms which solve these lattice problems, this implies the asymptotic security of the cryptosystem. However, current lattice-based cryptosystems using the learning with errors (LWE) problem select parameters for which the reduction to the underlying lattice problem gives no meaningful assurance of concrete security. We analyze the runtime of the algorithm constructed in the reductions and select parameters for a cryptosystem under which the reductions give 128-bit security. While the resulting LWE-based cryptosystem is somewhat cumbersome, requiring a dimension of n = 1460, this is less than 2 times the dimension in the recently proposed Frodo cryptosystem (Bos et al., ACM CCS 2016), and could be implemented without catastrophic damage to communication times. We also investigate the runtime necessary for a reduction to give meaningful security assurances for current cryptosystems. / Thesis / Master of Science (MSc) / The advent of quantum computing poses a serious threat to modern cryptography, as most cryptosystems in use today are vulnerable to attacks by quantum algorithms. Recently proposed cryptosystems based on lattices are conjectured to be resistant to attacks by quantum computers. These cryptosystems also have a conditional security guarantee: if the cryptosystem can be broken by an attack, then a reduction exists which uses that attack to solve variants of the shortest vector problem (Regev, STOC 2005; Peikert, ePrint 2008). As these problems have no known efficient solutions, breaking the cryptosystem should be hard. However this guarantee only holds if the cryptosystem is constructed using parameters which satisfy conditions given in the reduction. Current proposals do not do this, and so cannot claim even a conditional security guarantee. We analyze two reductions and select parameters for a cryptosystem which satisfy these conditions. We also investigate the runtime necessary for a reduction to give meaningful security assurances for current cryptosystems.

In this thesis, we generate a lower bound on the security of quantum protocols for secure function evaluation. Central to our proof is the concept of gentle measurements of quantum states, which do not greatly disturb a quantum state if a certain outcome is obtained with high probability. We show how a cheating party can leverage gentle measurements to learn more information than should be allowable. To quantify our lower bound, we reduce a specific cryptographic task known as die-rolling to secure function evaluation and use the concept of gentle measurements to relate their security notions. Our lower bound is then obtained using a known security bound for die-rolling known as Kitaev's bound. Due to the generality of secure function evaluation, we are able to apply this lower bound to obtain lower bounds on the security of quantum protocols for many quantum tasks. In particular, we provide lower bounds for oblivious transfer, XOR oblivious transfer, the equality function, the inner product function, Yao's millionaires' problem, and the secret phrase problem. Note that many of these lower bounds are the first of their kind, which is a testament to the utility of our lower bound. As a consequence, these bounds prove that unconditional security for quantum protocols is impossible for these applications, and since these are constant lower bounds, this rules out any form of boosting toward perfect security. Our work lends itself to future research on designing optimal protocols for the above listed tasks, and potentially others, by providing constant lower bounds to approximate or improve. / Master of Science / Quantifying the cryptographic security of quantum applications is the focus of much research in the quantum cryptography discipline. Quantum protocols might have better security than their classical counterparts, and this advantage might make the adoption of quantum cryptographic protocols a viable option. In this thesis, we introduce a method for generating constant lower bounds on the security of a variety of quantum applications. This is accomplished through finding a lower bound on the security of a protocol that is general, and by virtue of its generality, can be scoped to quantum applications such that the lower bound can be applied, and constant lower bounds generated for these applications. The significance of the work in this thesis is that many of the constant lower bounds presented are the first of their kind for these quantum applications, thus proving the impossibility of them having unconditional security. This also proves that one cannot asymptotically boost towards perfect security in these quantum tasks by any means. These constant lower bounds also provide a foundation for future work in the study of these quantum applications, specifically in the search for upper and lower bounds on their cryptographic security, as well as in the search for protocols that approximate these bounds.

In the context of a system design, resource-constraints refer to severe restrictions on allowable resources, while resource-efficiency is the capability to achieve a desired performance and, at the same time, to reduce wasting resources. To design for low-cost platforms, these fundamental concepts are useful under different scenarios and they call for different approaches, yet they are often mixed. Resource-constrained systems require aggressive optimizations, even at the expense of performance, to meet the stringent resource limitations. On the other hand, resource-efficient systems need a careful trade-off between resources and performance, to achieve the best possible combination. Designing systems for resource-constraints with the optimizations for resource-efficiency, or vice versa, can result in a suboptimal solution. Using modern cryptographic applications as the driving domain, I first distinguish resource-constraints from resource-efficiency. Then, I introduce the recurring strategies to handle these cases and apply them on modern cryptosystem designs. I illustrate that by clarifying the application context, and then by using appropriate strategies, it is possible to push the envelope on what is perceived as achievable, by up to two orders-of-magnitude. In the first part of this dissertation, I focus on resource-constrained modern cryptosystems. The driving application is Physical Unclonable Function (PUF) based symmetric-key authentication. I first propose the smallest block cipher in 128-bit security level. Then, I show how to systematically extend this design into the smallest application-specific instruction set processor for PUF-based authentication protocols. I conclude this part by proposing a compact method to combine multiple PUF components within a system into a single device identifier. In the second part of this dissertation, I focus on resource-efficient modern cryptosystems. The driving application is post-quantum public-key schemes. I first demonstrate energy-efficient computing techniques for post-quantum digital signatures. Then, I propose an area-efficient partitioning and a Hardware/Software codesign for its implementation. The results of these implemented modern cryptosystems validate the advantage of my approach by quantifying the drastic improvements over the previous best. / Ph. D.