The topic of this thesis is a cryptosystem, precisely a public key encryption scheme, that is based on the knapsack problem. At first we formulate terms like \mathcal{NP} -complete problem, one-way function, hard-core predicate, public key encryption scheme and semantic security which we connect in this thesis. After that we present the knapsack problem. Then we prove that the knapsack problem with appropriate parameters has a property that leads to semantic security of the encryption scheme which we present afterwards. This public key encryption scheme is based on the scheme proposed by Vadim Lyubashevsky, Adriana Palacio and Gil Segev. Powered by TCPDF (www.tcpdf.org)

In the presented work we focus on applications of decision problems from combinatorial group theory. Namely we analyse the Shpilrain-Zapata pro- tocol. We give formal proof that small cancellation groups are good platform for the protocol because the word problem is solvable in linear time and they are generic. We also analyse the complexity of the brute force attack on the protocol and show that in a theoretical way the protocol is immune to attack by adversary with arbitrary computing power.

<div>In a potentially hostile networked environment, a large diversity of security mechanisms with varying degree of sophistication are being deployed to protect valuable computer systems and digital assets. </div><div><br></div><div>While many competing implementations of similar security mechanisms are available in the current software development landscape, the robustness and reliability of such implementations are often overlooked, resulting in exploitable flaws in system deployments. In this dissertation, we systematically evaluate implementations of security mechanisms that are deployed in the wild. First, we examine how content distribution applications on the Android platform control access to their multimedia contents. With respect to a well-defined hierarchy of adversarial capabilities and attack surfaces, we find that many content distribution applications, including that of some world-renowned publications and streaming services, are vulnerable to content extraction due to the use of unjustified assumptions in their security mechanism designs and implementations. Second, we investigate the validation logic of X.509 certificate chains as implemented in various open-source TLS libraries. X.509 certificates are widely used in TLS as a means to achieve authentication. A validation logic that is overly restrictive could lead to the loss of legitimate services, while an overly permissive implementation could open door to impersonation attacks. Instead of manual analysis and unguided fuzzing, we propose a principled approach that leverages symbolic execution to achieve better coverage and uncover logical flaws that are buried deep in the code. We find that many TLS libraries deviate from the specification. Finally, we study the verification of RSA signatures, as specified in the PKCS#1 v1.5 standard, which is widely used in many security-critical network protocols. We propose an approach to automatically generate meaningful concolic test cases for this particular problem, and design and implement a provenance tracking mechanism to assist root-cause analysis in general. Our investigation revealed that several crypto and IPSec implementations are susceptible to new variants of the Bleichenbacher low-exponent signature forgery.</div>

Os sistemas criptográficos de chave pública amplamente utilizados hoje em dia tem sua segurança baseada na suposição da intratabilidade dos problemas de fatoração de inteiros e do logaritmo discreto, sendo que ambos foram demonstrados inseguros sob o advento dos computadores quânticos. Sistemas criptográficos baseados em Multivariáveis Quadráticas (MQ) utilizam como base o problema MQ, que consiste em resolver um sistema de equações polinomiais multivariáveis quadráticas sobre um corpo finito. O problema MQ foi provado como sendo NP-completo e até hoje não se conhece algoritmo, nem mesmo quântico, de tempo polinomial que possa resolver o problema, fazendo com que sistemas criptográficos baseados nesta primitiva mereçam ser investigados e desenvolvidos como reais candidatos a proverem nossa criptografia pós-quântica. Durante a CRYPTO\'2011 Sakumoto, Shirai e Hiwatari introduziram dois novos protocolos de identificação baseados em polinômios multivariáveis quadráticos, os quais chamamos de MQID-3 e MQID-5, e que em especial e pela primeira vez, tem sua segurança reduzida apenas ao problema MQ. Baseados nestas propostas iremos apresentar uma versão aprimorada do protocolo MQID-3 na qual teremos uma redução da comunicação necessária em aproximadamente 9%. / The public-key cryptography widely used nowadays have their security based on the assumption of the intractability of the problems of integer factorization and discrete logarithm, both of which were proven unsafe in the advent of quantum computers. Cryptographic systems based on Multivariate Quadratic polynomials (MQ) are based on the MQ problem, which consists in solve a system of multivariate quadratic polynomials over a finite field. The MQ problem has been proven NP-complete and so far no polynomial time algorithm is known, not even quantum, which would resolve this problem, making worthwhile to be investigated and developed as a real candidate to provide post-quantum cryptography. In CRYPTO\'2011 Sakumoto, Shirai and Hiwatari introduced two new identification protocols based on multivariate quadratic polynomials, which we call MQID-3 and MQID-5, in particular, for the first time, their security is based only on the MQ problem. Using these proposals, we will present an improved version of the protocol MQID-3 that reduces communication by approximately 9%.

As quantum computers continue to develop, they pose a threat to cryptography since many popular cryptosystems will be rendered vulnerable. This is because the security of most currently used asymmetric systems requires the computational hardness of the integer factorization problem, the discrete logarithm or the elliptic curve discrete logarithm problem. However, there are still some cryptosystems that resist quantum computing. We will look at code-based cryptography in general and the McEliece cryptosystem specifically. Our goal is to understand the structure behind the McEliece scheme, including the encryption and decryption processes, and what some advantages and disadvantages are that the system has to offer. In addition, using the results from Courtois, Finiasz, and Sendrier's paper in 2001, we will discuss a digital signature scheme based on the McEliece cryptosystem. We analyze one classical algebraic attack against the security analysis of the system based on the distinguishing problem whether the public key of the McEliece scheme is generated from a generating matrix of a binary Goppa code or a random binary matrix. The idea of the attack involves solving an algebraic system of equations and we examine the dimension of the solution space of the linearized system of equations. With the assistance from a paper in 2010 by Faugere, Gauthier-Umana, Otmani, Perret, Tillich, we will see the parameters needed for the intractability of the distinguishing problem. / Includes bibliography. / Thesis (M.S.)--Florida Atlantic University, 2015. / FAU Electronic Theses and Dissertations Collection

When the Internet was created it did not include any protocol for identifying the person behind the computer. Instead, the act of identification has primarily been established by trusting a third party. But, the rise of Distributed Ledger Technology has made it possible to authenticate a digital identity and build trust without the need of a third party. The Swedish Maritime Administration are currently validating a new maritime digital infrastructure for the maritime transportation industry. The goal is to reduce the number of accidents, fuel consumption and voyage costs. Involved actors has their identity stored in a central registry that relies on the trust of a third party. This thesis investigates how a conversion from the centralized identity registry to a decentralized identity registry affects the usability and the risk for compromised data integrity. This is done by implementing a Proof of Concept of a decentralized identity registry that replaces the current centralized registry, and comparing them. The decentralized Proof of Concept’s risk for compromised data integrity is 95.1% less compared with the centralized registry, but this comes with a loss of 53% in efficiency.

Current research on securing public computing infrastructure like Internet kiosks has focused on the use of smartphones to establish trust in a computing platform or to offload the processing of sensitive information, and the use of new cryptosystems such as Hierarchical Identity-based Encryption (HIBE) to protect kiosk user data. Challenges posed by rural kiosks, specifically (a) the absence of specialized hardware features such as Trusted Platform Modules (TPMs) or a modifiable BIOS in older recycled PCs, (b) the potential use of periodically disconnected links between kiosks and the Internet, (c) the absence of a production-ready implementation of HIBE and (d) the limited availability of smartphones in most developing regions make these approaches difficult, if not impossible, to implement in a rural public computing scenario. In this thesis, I present a practical, unobtrusive and easy-to-use security architecture for rural public computing that uses a combination of physical and cryptographic mechanisms to protect user data, public computing infrastructure and handheld devices that access this infrastructure. Key contributions of this work include (a) a detailed threat analysis of such systems with a particular focus on rural Internet kiosks and handheld devices, (b) a security architecture for rural public computing infrastructure that does not require any specialized hardware, (c) an application-independent and backward-compatible security API for securely sending and receiving data between these systems and the Internet that can operate over delay tolerant links, (d) an implementation of my scheme for rural Internet kiosks and (e) a performance evaluation of this implementation to demonstrate its feasibility.

Current research on securing public computing infrastructure like Internet kiosks has focused on the use of smartphones to establish trust in a computing platform or to offload the processing of sensitive information, and the use of new cryptosystems such as Hierarchical Identity-based Encryption (HIBE) to protect kiosk user data. Challenges posed by rural kiosks, specifically (a) the absence of specialized hardware features such as Trusted Platform Modules (TPMs) or a modifiable BIOS in older recycled PCs, (b) the potential use of periodically disconnected links between kiosks and the Internet, (c) the absence of a production-ready implementation of HIBE and (d) the limited availability of smartphones in most developing regions make these approaches difficult, if not impossible, to implement in a rural public computing scenario. In this thesis, I present a practical, unobtrusive and easy-to-use security architecture for rural public computing that uses a combination of physical and cryptographic mechanisms to protect user data, public computing infrastructure and handheld devices that access this infrastructure. Key contributions of this work include (a) a detailed threat analysis of such systems with a particular focus on rural Internet kiosks and handheld devices, (b) a security architecture for rural public computing infrastructure that does not require any specialized hardware, (c) an application-independent and backward-compatible security API for securely sending and receiving data between these systems and the Internet that can operate over delay tolerant links, (d) an implementation of my scheme for rural Internet kiosks and (e) a performance evaluation of this implementation to demonstrate its feasibility.

No description available.

Secure communication is critical to many applications. To this end, various security goals can be achieved using elliptic/hyperelliptic curve and pairing based cryptography. Polynomial multiplication is used in the underlying operations of these protocols. Therefore, as part of this thesis different recursive algorithms are studied; these algorithms include Karatsuba, Toom, and Bernstein. In this thesis, we investigate algorithms and implementation techniques to improve the performance of the cryptographic protocols. Common factors present in explicit formulae in elliptic curves operations are utilized such that two multiplications are replaced by a single multiplication in a higher field. Moreover, we utilize the idea based on common factor used in elliptic curves and generate new explicit formulae for hyperelliptic curves and pairing. In the case of hyperelliptic curves, the common factor method is applied to the fastest known even characteristic hyperelliptic curve operations, i.e. divisor addition and divisor doubling. Similarly, in pairing we observe the presence of common factors inside the Miller loop of Eta pairing and the theoretical results show significant improvement when applying the idea based on common factor method. This has a great advantage for applications that require higher speed.