The thesis presents the basics of Quantum Key Distribution, a survey of the present techniques, a look at the possible future, and finally a comparison to the alternative technique of using public key or manual distribution of keys. Techniques to integrate QKD with the existing telecom fiber infrastructure have been studied, and so has the EU-funded project SECOQC. Last the security and efficiency of QKD have been examined, with focus on what level of security that is required, existing security solutions have been used as a comparison. / ICG QC

Avec la possibilité de l’existence d’un ordinateur quantique, les primitives cryptographiques basées sur la théorie des nombres risquent de devenir caduques. Il devient donc important de concevoir des schémas résistants à ce nouveau type de menaces. Les réseaux euclidiens et les codes correcteurs d’erreurs sont deux outils mathématiques permettant de construire des problèmes d’algèbre linéaire, pour lesquels il n’existe aujourd’hui pas d’algorithme quantique permettant d’accélérer significativement leur résolution. Dans cette thèse, nous proposons quatre primitives cryptographiques de ce type : deux schémas de signatures (dont une signature traçable) basés sur les réseaux, un protocole de délégation de signature utilisant du chiffrement complètement homomorphe, et une nouvelle approche permettant de construire des cryptosystèmes très efficaces en pratique basés sur les codes. Ces contributions sont accompagnées de paramètres concrets permettant de jauger les coûts calculatoires des primitives cryptographique dans un monde post-quantique. / In the likely event where a quantum computer sees the light, number theoretic based cryptographic primitives being actually in use might become deciduous. This results in an important need to design schemes that could face off this new threat. Lattices and Error Correcting Codes are mathematical tools allowing to build algebraic problems, for which – up to-date – no quantum algorithm significantly speeding up their resolution is known. In this thesis, we propose four such kind cryptographic primitives: two signatures schemes (among those a traceable one) based on lattices, a signature delegation protocol using fully homomorphic encryption, and a new framework for building very efficient and practical code-based cryptosystems. These contributions are fed with concrete parameters allowing to gauge the concrete costs of security in a post-quantum world.

Orientador: Antonio Vidiella Barranco / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Física Gleb Wataghin / Made available in DSpace on 2018-08-18T11:59:35Z (GMT). No. of bitstreams: 1 Souza_DouglasDelgadode_M.pdf: 7468816 bytes, checksum: aba803ba35bfdb89aa8428cc3b6862d3 (MD5) Previous issue date: 2011 / Resumo: Neste trabalho, introduzimos um protocolo para a distribuição quântica de chaves (QKD) que faz uso de três estados comprimidos da luz: dois estados de bit, utilizados para a transmissão de informação, e um estado de Isca, utilizado para a detecção de espionagem. Seu desenvolvimento teve como base o protocolo de P. Horak (H04) para estados comprimidos, que por sua vez consiste de uma generalização do protocolo de R. Namiki e T. Hirano (NH03) para estados coerentes. Analisamos sua segurança considerando dois tipos de ataques: ataque por medida simultânea das quadraturas e ataque por troca do canal por canal superior. Para esta análise utilizamos uma descrição em termos da função de Wigner, obtendo a partir dela distribuições de probabilidade conjuntas e marginais. Da distribuição para os estados de Isca definimos uma Medida da Espionagem M, e discutimos sua utilidade para o cálculo da taxa de informação vazada para Eva em cada ataque. Por fim, para o ataque por troca do canal, analisamos o efeito da introdução de um limiar de pós-seleção sobre as informações de Bob e Eva, demonstrando que maiores distâncias de transmissão (menores transmissividades) podem ser suportadas pelo protocolo com o aumento deste parâmetro, ao custo de menores taxas de aceitação de bits / Abstract: In this work, we introduce a new protocol for Quantum Key Distribution which makes use of three squeezed coherent states of light: two bit states, used for transmission of information, and a Decoy state, used for eavesdropping detection. Its development was based on the protocol for squeezed coherent states suggested by P. Horak [39], which in turn consists of a generalization of the protocol by R. Namiki and T. Hirano [38] for coherent states. We analyze its security by considering two kinds of attack: simultaneous quadrature measurement attack and superior channel attack. For this analysis we use a description in terms of the Wigner function, obtaining from it some joint and marginal probability distributions. From the distribution for the Decoy states we define an Eavesdropping Measure M, and discuss its usefulness in calculating the rate of information leaked to Eve in each attack. Finally, for the superior channel attack, we analyze the influence of a post-selection threshold over the Bob and Eve information, showing that, by raising this parameter, larger transmission distances (smaller transmittivities) can be handled by the protocol at the expense of lower bit acceptance rates / Mestrado / Física Geral / Mestre em Física

Cryptographic digital signatures provide authentication to communicating parties over communication networks. They are integral asymmetric primitives in cryptography. The current digital signature infrastructure adopts schemes that rely on the hardness of finding discrete logarithms and factoring in finite groups. Given the recent advances in physics which point towards the eventual construction of large scale quantum computers, these hard problems will be solved in polynomial time using Shor’s algorithm. Hence, there is a clear need to migrate the cryptographic infrastructure to post-quantum secure alternatives. Such an initiative is demonstrated by the PQCRYPTO project and the current Post-Quantum Cryptography (PQC) standardization competition run by the National Institute of Standards and Technology (NIST). This dissertation considers hash-based digital signature schemes. Such algorithms rely on simple security notions such as preimage, and weak and strong collision resistances of hash functions. These notions are well-understood and their security against quantum computers has been well-analyzed. However, existing hash-based signature schemes have large signature sizes and high computational costs. Moreover, the signature size increases with the number of messages to be signed by a key pair. The goal of this work is to develop hash-based digital signature schemes to overcome the aforementioned limitations. First, FORS, the underlying few-time signature scheme of the NIST PQC alternate candidate SPHINCS+ is analyzed against adaptive chosen message attacks, and DFORS, a few-time signature scheme with adaptive chosen message security, is proposed. Second, a new variant of SPHINCS+ is introduced that improves the computational cost and security level. Security analysis for the new variant is presented. In addition, the hash-based group digital signature schemes, Group Merkle (GM) and Dynamic Group Merkle (DGM), are studied and their security is analyzed. Group Merkle Multi-Treem (GMMT) is proposed to solve some of the limitations of the GM and DGM hash-based group signature schemes. / Graduate

We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating party can try to bias the output bit towards a preferred value. For weak coin flipping the parties have known opposite preferred values. By a weak coin flipping protocol with bias ϵ we mean that neither player can force the outcome towards their preferred value with probability more than 1/2+ϵ. While it is known that classically, ϵ=1/2 (the worst possible), Mochon showed in 2007 that quantumly, weak coin flipping can be performed with arbitrarily small bias (near perfect). His non-constructive proof used the so-called point game formalism—a series of equivalent reductions which were introduced by Kitaev to study coin-flipping. He constructed point games with bias ϵ(k)=1/(4k+2) to prove the existence. The best known explicit protocol, however, had bias approaching ϵ(1)=1/6 (also due to Mochon, 2005). In the present work, we try to make the non-constructive part of the proof constructive, to wit, we make three main contributions towards the conversion of point-games into explicit protocols. First, we propose a framework—TIPG-to-Explicit-protocol Framework (TEF)—which simplifies the task of constructing explicit protocols. We use this framework to construct a protocol with bias ϵ(2)=1/10. We then give the exact formulae for the unitaries corresponding to the point-games due to Mochon, allowing us to describe (almost) perfect coin flipping protocols analytically, i.e. with bias ϵ(k) for arbitrarily large k. Finally, we introduce an algorithm we call the Elliptic Monotone Align (EMA) algorithm. This algorithm, together with TEF, lets us convert any point-game into an explicit protocol numerically. We conclude by giving another analytic construction of unitaries for Mochon's games using the ellipsoid picture introduced for the EMA algorithm. / Nous étudions le weak coin flipping, une primitive cryptographique fondamentale où deux parties méfiantes doivent établir à distance un bit aléatoire partagé. Un tricheur peut essayer de biaiser le bit de sortie vers une valeur préférée. Pour le weak coin flipping, les parties ont des valeurs préférées opposées. Par un protocole de weak coin flipping avec biais ϵ, nous entendons qu'aucun des deux joueurs ne peut forcer le résultat vers sa valeur préférée avec une probabilité supérieure à 1/2+ϵ. Alors que l'on sait que classiquement, ϵ=1/2 (le pire possible), Mochon a montré en 2007 qu'un weak coin flipping quantique peut être effectué avec un biais arbitrairement faible (presque parfait). Sa preuve non constructive a utilisé le formalisme dit du jeu de points (point games)—une série de réductions équivalentes qui ont été introduites par Kitaev pour étudier le coin flipping. Il a construit des jeux de points avec un biais ϵ(k)=1/(4k+2) pour en prouver l'existence. Le protocole explicite le plus connu, cependant, avait un biais approchant ϵ(1)=1/6 (également dû à Mochon, 2005). Dans le présent travail, nous essayons de rendre la partie non constructive de la preuve constructive, c'est-à-dire que nous apportons trois contributions principales à la conversion des jeux de points en protocoles explicites. Premièrement, nous proposons un cadre—TIPG-to-Explicit-protocol Framework (TEF)—qui simplifie la tâche de construction de protocoles explicites. Nous utilisons ce cadre pour construire un protocole avec un biais ϵ(2)=1/10. Nous donnons ensuite les formules exactes des unitaires correspondant aux jeux de points dus à Mochon, ce qui nous permet de décrire analytiquement des protocoles de coin flipping (presque) parfaits, c'est-à-dire avec un biais ϵ(k) pour un k arbitrairement grand. Enfin, nous introduisons un algorithme que nous appelons le Elliptic Monotone Align (EMA) Algorithm. Cet algorithme, associé à TEF, nous permet de convertir numériquement tout jeu de points en un protocole explicite. Nous concluons en donnant une autre construction analytique des unitaires pour les jeux de Mochon en utilisant l'image ellipsoïdale introduite pour l'algorithme EMA. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

No description available.

With the monetization of user data, data breaches have become very common these days. In the past five years, there were more than 7000 data breaches involving theft of personal information of billions of people. In the year 2020 alone, the global average cost per data breach was $3.86 million, and this number rose to $4.24 million in 2021. Therefore, the need for maintaining data security and privacy is becoming increasingly critical. Over the years, various data encryption schemes including RSA, ECC, and AES are being used to enable data security and privacy. However, these schemes are deemed vulnerable to quantum computers with their enormous processing power. As quantum computers are expected to become main stream in the near future, post-quantum secure encryption schemes are required. To this end, through NIST’s standardization efforts, code-based and lattice-based encryption schemes have emerged as one of the plausible way forward. Both code-based and lattice-based encryption schemes enable public key cryptosystems, key exchange mechanisms, and digital signatures. In addition, lattice-based encryption schemes support fully homomorphic encryption (FHE) that enables computation on encrypted data. Over the years, there have been several efforts to design efficient FPGA-based and ASIC-based solutions for accelerating the code-based and lattice-based encryption schemes. The conventional code-based McEliece cryptosystem uses binary Goppa code, which has good code rate and error correction capability, but suffers from high encoding and decoding complexity. Moreover, the size of the generated public key is in several MBs, leading to cryptosystem designs that cannot be accommodated on low-end FPGAs. In lattice-based encryption schemes, large polynomial ring operations form the core compute kernel and remain a key challenge for many hardware designers. To extend support for large modular arithmetic operations on an FPGA, while incurring low latency and hardware resource utilization requires substantial design efforts. Moreover, prior FPGA solutions for lattice-based FHE include hardware acceleration of basic FHE primitives for impractical parameter sets without the support for bootstrapping operation that is critical to building real-time privacy-preserving applications. Similarly, prior ASIC proposals of FHE that include bootstrapping are heavily memory bound, leading to large execution times, underutilized compute resources, and cost millions of dollars. To respond to these challenges, in this dissertation, we focus on the design of efficient hardware accelerators for code-based and lattice-based public key cryptosystems (PKC). For code-based PKC, we propose the design of a fully-parameterized en/decryption co-processor based on a new variant of McEliece cryptosystem. This co-processor takes advantage of the non-binary Orthogonal Latin Square Code (OLSC) to achieve a lower computational complexity along with smaller key size than that of the binary Goppa code. Our FPGA-based implementation of the co-processor is ∼3.5× faster than an existing classic McEliece cryptosystem implementation. For lattice-based PKC, we propose the design of a co-processor that implements large polynomial ring operations. It uses a fully-pipelined NTT polynomial multiplier to perform fast polynomial multiplications. We also propose the design of a highly-optimized Gaussian noise sampler, capable of sampling millions of high-precision samples per second. Through an FPGA-based implementation of this lattice-based PKC co-processor, we achieve a speedup of 6.5× while utilizing 5× less hardware resources as compared to state-of-the-art implementations. Leveraging our work on lattice-based PKC implementation, we explore the design of hardware accelerators that perform FHE operations using Cheon-Kim-Kim-Song (CKKS) scheme. Here, we first perform an in-depth architectural analysis of various FHE operations in the CKKS scheme so as to explore ways to accelerate an end-to-end FHE application. For this analysis, we develop a custom architecture modeling tool, SimFHE, to measure the compute and memory bandwidth requirements of hardware-accelerated CKKS. Our analysis using SimFHE reveals that, without a prohibitively large cache, all FHE operations exhibit low arithmetic intensity (<1 Op/byte). To address the memory bottleneck resulting from the low arithmetic intensity, we propose several memory-aware design (MAD) techniques, including caching and algorithmic optimizations, to reduce the memory requirements of CKKS-based application execution. We show that the use of our MAD techniques can yield an ASIC design that is at least 5-10× cheaper than the large-cache proposals, but only ∼2-3× slower. We also design FAB, an FPGA-based accelerator for bootstrappable FHE. FAB, for the first time ever, accelerates bootstrapping (along with basic FHE primitives) on an FPGA for a secure and practical parameter set. FAB tackles the memory-bounded nature of bootstrappable FHE through judicious datapath modification, smart operation scheduling, and on-chip memory management techniques to maximize the overall FHE-based compute throughput. FAB outperforms all prior CPU/GPU works by 9.5× to 456× and provides a practical performance for our target application: secure training of logistic regression models. / 2025-01-16T00:00:00Z

Mutually unbiased bases is an important topic in the recent quantum system researches. Although there is much work in this area, many problems related to mutually unbiased bases are still open. For example, constructing a complete set of mutually unbiased bases in the Hilbert spaces with composite dimensions has not been achieved yet. This thesis defines a weaker concept than mutually unbiased bases in the Hilbert spaces with composite dimensions. We call this concept, weak mutually unbiased bases. There is a duality between such bases and the geometry of the phase space Zd × Zd, where d is the phase space dimension. To show this duality we study the properties of lines through the origin in Zd × Zd, then we explain the correspondence between the properties of these lines and the properties of the weak mutually unbiased bases. We give an explicit construction of a complete set of weak mutually unbiased bases in the Hilbert space Hd, where d is odd and d = p1p2; p1, p2 are prime numbers. We apply the concept of weak mutually unbiased bases in the context of quantum tomography and quantum cryptography. / Egyptian government.

In 2016, NIST started a post quantum cryptography (PQC) standardization project in response to the rapid development of quantum algorithms which break many public-key cryptographic schemes. As the project nears its end, it is necessary to assess the resistance of its finalists to side-channel attacks. Although several side-channel attacks on software implementations PQCfinalists have been presented in recent papers, hardware implementations have been investigated much less. In this thesis, we present the first side-channel attack on an FPGA implementation of one of the NIST PQC finalists, Saber. Our experiments are performed on a publicly availible implementation of Saber compiled with Xilinx Vivado for an Artix-7 XC7A100T FPGA. We trained several deep learning models in an attempt to recover the Hamming weight and value of messages using their corresponding power traces. We also proposed a method to determine the Hamming weight of messages through binary search based on these models. We found out that, due to the difference in software and hardware implementations, the previously presented message recovery method that breaks a masked software implementation of Saber cannot be directly applied to the hardware implementation. The main reason for this is that, in the hardware implementation used in our experiments, all 256 bits of a message are processed in parallel, while in the software implementation used in the previous work, the bits are processed one-by-one. Future works includes finding new methods for analyzing hardware implementations. / Under 2016 startade NIST ett standardiseringsprojekt efter kvantkryptering (PQC) som svar på den snabba utvecklingen av kvantalgoritmer som bryter många kryptografiska system med offentliga nyckel. När projektet närmar sig sitt slut är det nödvändigt att bedöma finalisternas motstånd mot sidokanalsattacker. Även om flera sidokanalsattacker på programvaruimplementationer PQC-finalister har presenterats i de senaste tidningarna, har hårdvaruimplementationer undersökts mycket mindre. I denna avhandling presenterar vi den första sidokanalsattacken på en FPGA-implementering av en av NIST PQC-finalisterna, Sabre. Våra experiment utförs på en allmänt tillgänglig implementering av Sabre kompilerad med Xilinx Vivado för en Artix-7 XC7A100T FPGA. Vi tränade f lera modeller för djupinlärning i ett försök att återställa Hamming-vikten och värdet av meddelanden med hjälp av deras motsvarande kraftspår. Vi föreslog också en metod för att bestämma Hamming-vikten för meddelanden genom binär sökning baserat på dessa modeller. Vi fick reda på att, på grund av skillnaden i mjukvaru- och hårdvaruimplementationer, kan den tidigare presenterade meddelandeåterställningsmetoden som bryter en maskerad mjukvaruimplementering av Sabre inte direkt appliceras på hårdvaruimplementeringen. Den främsta anledningen till detta är att i hårdvaruimplementeringen som används i våra experiment bearbetas alla 256 bitar i ett meddelande parallellt, medan i mjukvaruimplementeringen som användes i det tidigare arbetet bearbetas bitarna en i taget. Framtida arbete inkluderar att hitta nya metoder för att analysera hårdvaruimplementationer.

Internet-of-Things (IoT) devices have become increasingly popular in the last 10 years, yet also show an acceptance for lack of security due to hardware constraints. The range of sophistication in IoT devices varies substantially depending on the functionality required, so security options need to be flexible. Manufacturers typically either use no security, or lean towards the use of the Advanced Encryption Standard (AES) with a 128-bit key. AES-128 is suitable for the higher end of that IoT device range, but is costly enough in terms of memory, time, and energy consumption that some devices opt to use no security. Short development and a strong drive to market also contribute to a lack in security. Recent work in lightweight cryptography has analyzed the suitability of custom protocols using AES as a comparative baseline. AES outperforms most custom protocols when looking at security, but those analyses fail to take into account block size and future capabilities such as quantum computers. This thesis analyzes lightweight cryptographic primitives that would be suitable for use in IoT devices, helping fill a gap for "good enough" security within the size, weight, and power (SWaP) constraints common to IoT devices. The primitives have not undergone comprehensive cryptanalysis and this thesis attempts to provide a preliminary analysis of confidentiality. The first is a single-stage residue number system (RNS) pseudorandom number generator (PRNG) that was shown in previous publications to produce strong outputs when analyzed with statistical tests like the NIST RNG test suite and DIEHARD. However, through analysis, an intelligent multi-stage conditional probability attack based on the pigeonhole principle was devised to reverse engineer the initial state (key) of a single-stage RNS PRNG. The reverse engineering algorithm is presented and used against an IoT-caliber device to showcase the ability of an attacker to retrieve the initial state. Following, defenses based on intentional noise, time hopping, and code hopping are proposed. Further computation and memory analysis show the proposed defenses are simple in implementation, but increase complexity for an attacker to the point where reverse engineering the PRNG is likely no longer viable. The next primitive proposed is a block cipher combination technique based on Galois Extension Field multiplication. Using any PRNG to produce the pseudorandom stream, the block cipher combination technique generates a variable sized key matrix to encrypt plaintext. Electronic Codebook (ECB) and Cipher Feedback (CFB) modes of operation are discussed. Both system modes are implemented in MATLAB as well as on a Texas Instruments (TI) MSP430FR5994 microcontroller for hardware validation. A series of statistical tests are then run against the simulation results to analyze overall randomness, including NIST and the Law of the Iterated Logarithm; the system passes both. The implementation on hardware is compared against a stream cipher variation and AES-128. The block cipher proposed outperforms AES-128 in terms of computation time and consumption for small block sizes. While not as secure, the cryptosystem is more scalable to block sizes used in IoT devices. / Master of Science / An Internet-of-Things (IoT) device is a single-purpose computer that operates with less computing resources and sometimes on battery power. The classification of IoT can range anywhere from motion sensors to a doorbell camera, but IoT devices are used in more than just home automation. The medical and industrial spaces use simple wireless computers for a number of tasks as well. One concern with IoT, given the hardware constraints, is the lack of security. Since messages are often transmitted through a wireless medium, anybody could eavesdrop on what is being communicated if data is not encrypted prior to transmission. Cryptography is the practice of taking any string of data and obfuscating it through a process that only valid parties can reverse. The sophistication of cryptographic systems has increased to the point where IoT manufacturers elect to use no security in many cases because the hardware is not advanced enough to run them efficiently. The Advanced Encryption Standard (AES) is usually the choice for security in the IoT space, but typically only higherend devices can afford to use AES. This thesis focuses on alternative lightweight systems to AES. First, a single-stage residue number system (RNS) pseudorandom number generator (PRNG) is analyzed, which has been proven to generate statistically random outputs in previous publications. PRNGs are a cheap method of producing seemingly random outputs through an algorithm once provided with an initial state known as a seed. An intelligent attack on the PRNG is devised, which is able to reverse engineer the initial state, effectively breaking the random behavior. Three defenses against the attack are then implemented to protect against the reported vulnerability. Following, a block cipher combination technique is presented, using the aforementioned PRNG as the source of randomness. A block cipher is a method of encrypting large chunks of data together, to better obfuscate the output. Using a block cipher is more secure than just using a PRNG for encryption. However, PRNGs are used to generate the key for the proposed block cipher, as they offer a more efficient method of security. The combination technique presented serves to increase the security of PRNGs further. The cipher is shown to perform better on an IoT-caliber device in terms of computation time and energy consumption at smaller block sizes than AES.