Public key cryptosystems offer important advantages over symmetric methods, but the most important such systems rely on the difficulty of integer factorization (or the related discrete logarithm problem). Advances in quantum computing threaten to render such systems useless. In addition, public-key systems tend to be slower than symmetric systems because of their use of number-theoretic algorithms. I propose a new public key system which may be secure against both classical and quantum attacks, while remaining simple and very fast. The system's action is best described in terms of linear algebra, while its security is more naturally explained in the context of graph theory.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24731号 / 情博第819号 / 新制||情||138(附属図書館) / 京都大学大学院情報学研究科社会情報学専攻 / (主査)教授 神田 崇行, 教授 吉川 正俊, 教授 梅野 健, TIBOUCHI Mehdi(NTT社会情報研究所) / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Quantum computers are envisioned to be able to solve mathematical problems which are currently unsolvable for conventional computers, because of their exceptional computational power from quantum mechanics. Therefore, if quantum computers are ever built in large scale, they will certainly be able to solve many classical exponential complexity problems such as the hard problems which the current public key cryptography is constructed upon. To counteract this problem, the design of post-quantum cryptography protocols is necessary to preserve the security in the presence of quantum adversaries. Regardless of whether we can estimate the exact time for the advent of the quantum computing era, security protocols are required to be resistant against potentially-malicious power of quantum computing. In this thesis, the main focus is on the sperformance improvement of one of the potential PQC candidates, isogeny-based cryptography. Several optimized implementations of cryptography applications based on this primitive are presented. From a general viewpoint, the proposed methods, implementation techniques and libraries have a practical impact on the performance evaluation of post-quantum cryptography schemes in a wide range of applications. In particular, the provided benchmarks and optimizations on ARM-powered processors provide a reference for comparison and evaluation of isogeny-based cryptography with other post-quantum candidates during the first round of NIST's PQC standardization process. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2018. / FAU Electronic Theses and Dissertations Collection

With the emerging computing technologies and applications in the past decades, cryptography is facing tremendous challenges in its position of guarding our digital world. The advent of quantum computers is potentially going to cease the dominance of RSA and other public key algorithms based on hard problems of factorization and discrete logarithm. In order to protect the Internet at post-quantum era, great efforts have been dedicated to the design of RSA substitutions. One of them is code- based McEliece public key schemes which are immune to quantum attacks. Meanwhile, new infrastructures like Internet of Things are bringing the world enormous benefits but, due to the resource-constrained nature, require compact and still reliable cryptographic solutions. Motivated by this, many lightweight cryptographic algorithms are introduced. Nevertheless, side channel attack is still a practical threat for implementations of these new algorithms if no countermeasures are employed. In the past decades two major categories of side channel countermeasures, namely masking and hiding, have been studied to mitigate the threat of such attacks. As a masking countermeasure, Threshold Implementation becomes popular in recent years. It is sound in providing provable side channel resistance for hardware-based cryptosystems but meanwhile it also incurs significant overheads which need further optimization for constrained applications. Masking, especially for higher order masking schemes, requires low signal-to-noise ratio to be effective which can be achieved by applying hiding countermeasures. In order to evaluate side channel resistance of countermeasures, several tools have been introduced. Due to its simplicity, TVLA is being accepted by academy and industry as a one-size-fit-all leakage detection methodolgy that can be used by non-experts. However, its effectiveness can be negatively impacted by environmental factors such as temperature variations. Thus, a robust and simple evaluation method is desired. In this dissertation, we first show how differential power analysis can efficiently exploit the power consumption of a McEliece implementation to recover the private key. Then, we apply Threshold Implementation scheme in order to protect from the proposed attack. This is, to the best of our knowledge, the first time of applying Threshold Implementation in a public key cryptosystem. Next, we investigate the reduction of shares in Threshold Implementation so as to bring down its overhead for constrained applications. Our study shows that Threshold Implementation using only two shares reduces the overheads while still provides reliable first-order resistance but in the meantime it also leaks a strong second-order leakage. We also propose a hiding countermeasure, namely balanced encoding scheme based on the idea of Dual- Rail Pre-charge logic style in hardwares. We show that it is effective to mitigate the leakage and can be combined with masking schemes to achieve better resistance. Finally, we study paired t-test versus Welch's t-test in the original TVLA and show its robustness against environmental noises. We also found that using moving average in computing t statistics can detect higher-order leakage faster.

Zugl.: Bochum, Univ., Diss., 2009

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

This thesis aims at providing efficient and side-channel protected implementations of isogeny-based primitives, and at their application in threshold protocols. It is based on a sequence of academic papers. Chapter 3 reviews the original variable-time implementation of CSIDH and introduces several optimizations, e.g. a significant improvement of isogeny computations by using both Montgomery and Edwards curves. In total, our improvements yield a speedup of 25% compared to the original implementation. Chapter 4 presents the first practical constant-time implementation of CSIDH. We describe how variable-time implementations of CSIDH leak information on private keys, and describe ways to mitigate this. Further, we present several techniques to speed up the implementation. In total, our constant-time implementation achieves a rather small slowdown by a factor of 3.03. Chapter 5 reviews practical fault injection attacks on CSIDH and presents countermeasures. We evaluate different attack models theoretically and practically, using low-budget equipment. Moreover, we present countermeasures that mitigate the proposed fault injection attacks, only leading to a small performance overhead of 7%. Chapter 6 initiates the study of threshold schemes based on the Hard Homogeneous Spaces (HHS) framework of Couveignes. Using the HHS equivalent of Shamir’s secret sharing in the exponents, we adapt isogeny based schemes to the threshold setting. In particular, we present threshold versions of the CSIDH public key encryption and the CSI-FiSh signature scheme. Chapter 7 gives a sieving algorithm for finding pairs of consecutive smooth numbers that utilizes solutions to the Prouhet-Tarry-Escott (PTE) problem. Recent compact isogeny-based protocols, namely B-SIDH and SQISign, both require large primes that lie between two smooth integers. Finding such a prime can be seen as a special case of finding twin smooth integers under the additional stipulation that their sum is a prime. / Die vorliegende Dissertation stellt effiziente und Seitenkanal-geschützte Implementierungen Isogenie-basierter Verfahren bereit, und behandelt deren Verwendung in Threshold-Protokollen. Sie basiert auf einer Reihe von Veröffentlichungen. Kapitel 3 untersucht die originale variable-time Implementierung von CSIDH und beschreibt einige Optimierungen, wie etwa die effizientere Berechnung von Isogenien durch die Verwendung von Montgomery- und Edwards-Kurven. Insgesamt erreichen die Optimierungen eine Beschleuningung von 25% gegenüber der Referenzimplementierung. Kapitel 4 enthält die erste effiziente constant-time Implementierung von CSIDH. Es beschreibt inwiefern variable-time Implementierungen Informationen über private Schlüssel liefern, und entsprechende Gegenmaßnahmen. Des Weiteren werden einige Techniken zur Optimierung der Implementierung beschrieben. Insgesamt ist die constant-time Implementierung nur etwa 3x langsamer. Kapitel 5 untersucht praktische Fault-injection Attacken auf CSIDH und beschreibt Gegenmaßnahmen. Es betrachtet verschiedene Angriffsmodelle theoretisch und praktisch unter der Verwendung von low-budget Equipment. Die Gegenmaßnahmen führen zu einer sehr kleinen Performance-Verschlechterung von 7%. Kapitel 6 initiiert die Untersuchung von Threshold-Verfahren basierend auf Hard Homogeneous Spaces (HHS). Unter Verwendung der HHS-Version von Shamir Secret Sharing im Exponenten, werden Threshold-Varianten der CSIDH Verschlüsselung und des CSI-FiSh Signaturschemas definiert. Kapitel 7 enthält einen Sieb-Algorithmus zur Suche nach Paaren von aufeinanderfolgenden glatten Zahlen, unter Verwendung von Lösungen des Prouhet-Tarry-Escott-Problems. Die kürzlich veröffentlichten Isogenie-Verfahren B-SIDH und SQISign benötigen große Primzahlen, die zwischen zwei glatten ganzen Zahlen liegen. Die Suche nach solchen Primzahlen ist ein Spezialfall der Suche nach glatten benachbarten Zahlen, unter der zusätzlichen Bedingung dass deren Summe prim ist.

No description available.

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 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.