No description available.

Key agreement is a cryptographic scenario between two legitimate parties, who need to establish a common secret key over a public authenticated channel, and an eavesdropper who intercepts all their messages in order to learn the secret. We consider query complexity in which we count only the number of evaluations (queries) of a given black-box function, and classical communication channels. Ralph Merkle provided the first unclassified scheme for secure communications over insecure channels. When legitimate parties are willing to ask O(N) queries for some parameter N, any classical eavesdropper needs Omega(N^2) queries before being able to learn their secret, which is is optimal. However, a quantum eavesdropper can break this scheme in O(N) queries. Furthermore, it was conjectured that any scheme, in which legitimate parties are classical, could be broken in O(N) quantum queries. In this thesis, we introduce protocols à la Merkle that fall into two categories. When legitimate parties are restricted to use classical computers, we offer the first secure classical scheme. It requires Omega(N^{13/12}) queries of a quantum eavesdropper to learn the secret. We give another protocol having security of Omega(N^{7/6}) queries. Furthermore, for any k>= 2, we introduce a classical protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1/2+k/{k+1}}) queries, approaching Theta(N^{3/2}) when k increases. When legitimate parties are provided with quantum computers, we present two quantum protocols improving on the best known scheme before this work. Furthermore, for any k>= 2, we give a quantum protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1+{k}/{k+1}})} queries, approaching Theta(N^{2}) when k increases. / Un protocole d'échange de clés est un scénario cryptographique entre deux partis légitimes ayant besoin de se mettre d'accord sur une clé commune secrète via un canal public authentifié où tous les messages sont interceptés par un espion voulant connaître leur secret. Nous considérons un canal classique et mesurons la complexité de calcul en termes du nombre d'évaluations (requêtes) d'une fonction donnée par une boîte noire. Ralph Merkle fut le premier à proposer un schéma non classifié permettant de réaliser des échanges securisés avec des canaux non securisés. Lorsque les partis légitimes sont capables de faire O(N) requêtes pour un certain paramètre N, tout espion classique doit faire Omega(N^2) requêtes avant de pouvoir apprendre leur secret, ce qui est optimal. Cependant, un espion quantique peut briser ce schéma avec O(N) requêtes. D'ailleurs, il a été conjecturé que tout protocole, dont les partis légitimes sont classiques, pourrait être brisé avec O(N) requêtes quantiques. Dans cette thèse, nous introduisons deux catégories des protocoles à la Merkle. Lorsque les partis légitimes sont restreints à l'utilisation des ordinateurs classiques, nous offrons le premier schéma classique sûr. Il oblige tout adversaire quantique à faire Omega(N^{13/12}) requêtes avant d'apprendre le secret. Nous offrons aussi un protocole ayant une sécurité de Omega(N^{7/6}) requêtes. En outre, pour tout k >= 2, nous donnons un protocole classique pour lequel les partis légitimes établissent un secret avec O(N) requêtes alors que la stratégie optimale d'espionnage quantique nécessite Theta(N^{1/2 + k/{k +1}}) requêtes, se rapprochant de Theta(N^{3/2}) lorsque k croît. Lors les partis légitimes sont équipés d'ordinateurs quantiques, nous présentons deux protocoles supérieurs au meilleur schéma connu avant ce travail. En outre, pour tout k >= 2, nous offrons un protocole quantique pour lequel les partis légitimes établissent un secret avec O(N) requêtes alors que l'espionnage quantique optimale nécessite Theta(N^{1+{k}/{k+1}}) requêtes, se rapprochant de Theta(N^{2}) lorsque k croît.

Today both government agencies and companies struggle to keep up with the pace of the continuous change of technology. With all new technology there are benefits, but new problems might also occur. Implementing new technology for certain tasks may increase both efficiency and security, resulting in a more sustainable work environment. One technology that is increasingly adopted is digital signatures. Instead of using classical handwritten signatures on documents, a digital signature can be more time efficient and have higher security. In order to implement a digital signature technology some security aspects must be addressed and certain properties ensured. In the document signature process, each time an individual verifies a signature attached onto a document a log entry is created. This log contains information about who verified which document, does it have multiple parts that have been signed, does it need multiple signatures in order to be valid, and at what time and date was the document signed. Logs help to ensure the validity of the document and thereby increase the security provided by the digital signatures. At KTH, a student must sign an application form with a regular ink-written signature to start a thesis project. This process can in most cases delay the start up to two weeks. This study aims to implement digital signatures for one specific form, an application form for a thesis project. The hypothesis at the start of the project was that the use of digital signature would decrease the time of waiting significantly. Personnel at KTH using digital signature would facilitate their work efficiency, due to less printing and archiving of papers as well fewer meetings. This study will provide the reader with the necessary fundamental knowledge of cryptography and how digital signatures use this underlying technology. The methodology used in this study was to identify and modify certain software settings, as well collect data from students and personnel at KTH. The collected data was based on time measurements of digital signature processes from students and a faculty member. The results show digital signatures are faster than the current signing process with traditional ink-written signatures. Additionally, the use of digital signatures is expected to reduce the need for printing, transport, and sorting of paper documents. The resulting reduction in use of physical paper should provide environmental benefits. / Dagens myndigheter och företag har det svårt att ständigt följa den tekniska utvecklingen. Ny teknik skapar oftast nya fördelar och andra förmåner men kan ibland också orsaka problem. Att implementera ny teknik för specifika ändamål kan öka både effektivitet och säkerhet, vilket resulterar i en mer effektiv arbetsplats. En teknik som introduceras allt mer på sistone är digitala signaturer. Istället för att signera dokument med en handskriven signatur kan en digital signatur vara mer tidseffektiv och ha en högre säkerhet. För att implementera tekniken bakom digitala signaturer måste särskilda säkerhetsaspekter adresseras och specifika inställningar säkerställas. I signaturprocessen måste varje individ verifiera signaturen som är bifogad på dokumentet, denna verifiering skapar även en logg. En logg innehåller bland annat information om vem som verifierade dokumentet, om dokumentet har fler än en bifogad signatur, behöver dokumentet fler signaturer för att vara giltigt och vilken tid och datum var dokumentet signerat. En logg säkerställer validiteten av dokumentet och ökar därmed säkerheten för digitala signaturer. På KTH krävs en skriftlig ansökan för att påbörja ett examensarbete. Med nuvarande process kan det i vissa fall leda till en försenad projektstart med upp till två veckor. Den här studien syftar till att implementera digitala signaturer för ett specifikt formulär, en ansökningsblankett för att påbörja ett examensarbete. Hypotesen vid projektstart var att användning av digitala signaturer skulle kunna förminska väntetiden signifikant. Anställda på KTH som utnyttjar digitala signaturer skulle kunna förbättra deras arbetseffektivitet på grund av färre pappersutskrifter, mindre pappersarkivering och färre möten. Den här studien kommer att förse läsaren med de mest nödvändiga kunskaperna av kryptografi och hur digitala signaturer använder krypteringsfenomenet. Metodiken som användes syftade till att identifiera och modifiera specifika mjukvaruinställningar samt samla in data från studenter och personal på KTH. Den insamlade datan baserades på tidsmätningar av digitala signatursprocesser från studenter, studievägledare och handledare. Resultatet från studien visade att digitala signaturer skulle ge en snabbare signeringsprocess än nuvarande formulär. Det kan dessutom förväntas att med digitala signaturer skulle pappersutskrifter, papperstransporter och sortering av dessa dokument reduceras. Resultatet av minskad användning av fysiskt papper kommer att generera arbetsfördelar.

No / The Versatile and Ubiquitous Secret Sharing System, a cloud data repository secure access and a web based authentication scheme. It is designed to implement the sharing, distribution and reconstruction of sensitive secret data that could compromise the functioning of an organisation, if leaked to unauthorised persons. This is carried out in a secure web environment, globally. It is a threshold secret sharing scheme, designed to extend the human trust security perimeter. The system could be adapted to serve as a cloud data repository and secure data communication scheme. A secret sharing scheme is a method by which a dealer distributes shares of a secret data to trustees, such that only authorised subsets of the trustees can reconstruct the secret. This paper gives a brief summary of the layout and functions of a 15-page secure server-based website prototype; the main focus of a PhD research effort titled ‘Cryptography and Computer Communications Security: Extending the Human Security Perimeter through a Web of Trust’. The prototype, which has been successfully tested, has globalised the distribution and reconstruction processes. / Petroleum Technology Development Fund

<p dir="ltr">Distributed cryptographic protocols typically assume a bounded number of malicious parties (who behave arbitrarily) in the system---and in turn, a lower bound on the number of <i>honest</i> parties (who follow and only follow a protocol faithfully/honestly without performing unspecified computations)---for their respective security guarantees to hold. However, when deploying these protocols in practice, the nature of computing parties does not necessarily align nicely with the protocols' assumptions. Specifically, there may be only a few honest/compliant parties, or none exists. Instead, non-malicious parties may be <i>semi-honest</i> (who follow the protocol specifications but are curious to learn as much information as possible from semi-honest parties' transcripts) or <i>rational</i> (who take actions that maximize their utilities instead of actions benefiting the protocol the most, e.g., performing extra computations or not following protocols). In such cases, the security guarantees of such protocols may deviate greatly in real life from what is theoretically promised, leaving a huge gap between theory and practice. </p><p dir="ltr">In this thesis, I bridge such a gap by enhancing the fault tolerance of various distributed cryptographic primitives by <i>relaxing the assumption on the existence of honest parties</i>.</p><p dir="ltr">First, in the context of <b>secure multi-party computations</b>, without honest parties, my goal is to induce honest (i.e., not compromising correctness) and non-curious (i.e., not harming privacy) behaviors from rational participants via game theoretic and cryptographic techniques. In particular, I first demonstrate how to ensure protocol correctness and deter collusion among parties to recover secrets---which also breaks privacy---in multiserver private information retrieval with a singleton access structure. Then for primitives with more general (non-singleton) access structures, I introduce a distinct treatment through the lens of verifiable secret sharing. The two solutions are designed with a public bulletin board, commitment schemes, digital signature schemes, zkSNARKs (zero-knowledge succinct non-interactive arguments of knowledge), and distinct incentive structures tailored for varying access structures underlying the schemes.</p><p dir="ltr">Second, in <b>permissionless blockchain systems</b>, for protocols without privacy guarantees like computation outsourcing and consensus, my goal is to incentivize rational parties to behave correctly. This means to act according to the protocol specifications or as implied by the security requirements of the primitive, e.g., fairly distribute rewards to participants based on contributions in proof-of-work (PoW) blockchains. Specifically, I present a defense against an undercutting attack in PoW blockchains from a game theory perspective and propose a decentralized computation outsourcing protocol built on permissionless blockchain systems based on multi-unit auctions.</p>

Security of cryptographic algorithms relies on the computational difficulty of deriving the secret key using public information. Cryptanalysis, including logical and implementation attacks, plays an important role in allowing the security community to estimate their cost, based on the computational resources of an attacker. Practical implementations of cryptanalytic systems require complex designs that integrate multiple functional components with many parameters. In this thesis, methodologies are proposed to improve the design process of cryptanalytic systems and reduce the cost of design space exploration required for optimization. First, Bluespec, a rule-based HDL, is used to increase the abstraction level of hardware design and support efficient design space exploration. Bluespec is applied to implement a hardware-accelerated logical attack on ECC with optimized modular arithmetic components. The language features of Bluespec support exploration and this is demonstrated by applying Bluespec to investigate the speed area tradeoff resulting from various design parameters and demonstrating performance that is competitive with prior work. This work also proposes a testing environment for use in verifying the implementation attack resistance of secure systems. A modular design approach is used to provide separation between the device being tested and the test script, as well as portability, and openness. This yields an open-source solution that supports implementation attack testing independent of the system platform, implementation details, and type of attack under evaluation. The suitability of the proposed test environment for implementation attack vulnerability analysis is demonstrated by applying the environment to perform an implementation attack on AES. The design of complex cryptanalytic hardware can greatly benefit from better design methodologies and the results presented in this thesis advocate the importance of this aspect. / Master of Science

Machine Learning (ML) profitiert erheblich von der Verfügbarkeit großer Mengen an Trainingsdaten, sowohl im Bezug auf die Anzahl an Datenpunkten, als auch auf die Anzahl an Features pro Datenpunkt. Es ist allerdings oft weder möglich, noch gewollt, mehr Daten unter zentraler Kontrolle zu aggregieren. Multi-Party-Computation (MPC)-Protokolle stellen eine Lösung dieses Dilemmas in Aussicht, indem sie es mehreren Parteien erlauben, ML-Modelle auf der Gesamtheit ihrer Daten zu trainieren, ohne die Eingabedaten preiszugeben. Generische MPC-Ansätze bringen allerdings erheblichen Mehraufwand in der Kommunikations- und Laufzeitkomplexität mit sich, wodurch sie sich nur beschränkt für den Einsatz in der Praxis eignen. Das Ziel dieser Arbeit ist es, Privatsphäreerhaltendes Machine Learning mittels MPC praxistauglich zu machen. Zuerst fokussieren wir uns auf zwei Anwendungen, lineare Regression und Klassifikation von Dokumenten. Hier zeigen wir, dass sich der Kommunikations- und Rechenaufwand erheblich reduzieren lässt, indem die aufwändigsten Teile der Berechnung durch Sub-Protokolle ersetzt werden, welche auf die Zusammensetzung der Parteien, die Verteilung der Daten, und die Zahlendarstellung zugeschnitten sind. Insbesondere das Ausnutzen dünnbesetzter Datenrepräsentationen kann die Effizienz der Protokolle deutlich verbessern. Diese Beobachtung verallgemeinern wir anschließend durch die Entwicklung einer Datenstruktur für solch dünnbesetzte Daten, sowie dazugehöriger Zugriffsprotokolle. Aufbauend auf dieser Datenstruktur implementieren wir verschiedene Operationen der Linearen Algebra, welche in einer Vielzahl von Anwendungen genutzt werden. Insgesamt zeigt die vorliegende Arbeit, dass MPC ein vielversprechendes Werkzeug auf dem Weg zu Privatsphäre-erhaltendem Machine Learning ist, und die von uns entwickelten Protokolle stellen einen wesentlichen Schritt in diese Richtung dar. / Machine learning (ML) greatly benefits from the availability of large amounts of training data, both in terms of the number of samples, and the number of features per sample. However, aggregating more data under centralized control is not always possible, nor desirable, due to security and privacy concerns, regulation, or competition. Secure multi-party computation (MPC) protocols promise a solution to this dilemma, allowing multiple parties to train ML models on their joint datasets while provably preserving the confidentiality of the inputs. However, generic approaches to MPC result in large computation and communication overheads, which limits the applicability in practice. The goal of this thesis is to make privacy-preserving machine learning with secure computation practical. First, we focus on two high-level applications, linear regression and document classification. We show that communication and computation overhead can be greatly reduced by identifying the costliest parts of the computation, and replacing them with sub-protocols that are tailored to the number and arrangement of parties, the data distribution, and the number representation used. One of our main findings is that exploiting sparsity in the data representation enables considerable efficiency improvements. We go on to generalize this observation, and implement a low-level data structure for sparse data, with corresponding secure access protocols. On top of this data structure, we develop several linear algebra algorithms that can be used in a wide range of applications. Finally, we turn to improving a cryptographic primitive named vector-OLE, for which we propose a novel protocol that helps speed up a wide range of secure computation tasks, within private machine learning and beyond. Overall, our work shows that MPC indeed offers a promising avenue towards practical privacy-preserving machine learning, and the protocols we developed constitute a substantial step in that direction.

Die Quantenschlüsselverteilung (QKD), die erste anwendbare Quantentechnologie, verspricht informationstheoretisch sichere Kommunikation. In der vorliegenden Arbeit wurde das Zeit-Frequenz (TF)-QKD-Protokoll untersucht, das Zeit und Frequenz, nämlich Puls-Positionsmodulation (PPM) im Zeitbereich und Frequenzumtastung (FSK) im Frequenzbereich als die beiden komplementären Basen verwendet. Seine Sicherheit beruht den Quanteneigenschaften von Licht und auf der Zeit-Frequenz-Unschärferelation. TF-QKD kann mit größtenteils Standard-Telekommunikationstechnologie im 1550-nm-Band implementiert werden. Die PPM-Basis kann mit Modulatoren und die FSK-Basis mit Hilfe der Wellenlängenmultiplex-Technologie realisiert werden. Das TF-QKD-Protokoll ist in der Lage, ein beliebig großes Alphabet bereitzustellen, was mehr als 1 bit/Photon ermöglicht. Darüber hinaus ist es robust gegenüber athmosphärischen Störungen und somit für die Übertragung über den Freiraumkanal geeignet. In der vorliegenden Arbeit wird das TF-QKD-Protokoll theoretisch bewertet, mit Standardkomponenten für 1 bit/Photon implementiert und die Freiraumübertragung mit optischem Tracking über eine 388 m Teststrecke wird bei Tageslicht demonstriert. Unter Verwendung der vorhandenen Komponenten konnte eine sichere Schlüsselrate von 364 kbit/s back-to-back und 9 kbit/s über den Freiraumkanal demonstriert werden. / Quantum key distribution (QKD), the first applicable quantum technology, promises information theoretically secure communication. In the presented work the time-frequency (TF)-QKD protocol was examined, which uses time and frequency, namely pulse position modulation (PPM) in the time domain and frequency shift keying (FSK) in the frequency domain as the two complementary bases. Its security relies on the quantum properties of light and the time-frequency uncertainty relation. TF-QKD can be implemented mostly with standard telecom-technology in the 1550 nm band. The PPM basis can be implemented with modulators and the FSK basis with help of wavelength-division multiplexing technology. The TF-QKD protocol is capable of providing an arbitrarily large alphabet enabling more than 1 bit/photon. Moreover, it is robust in the atmosphere making it suitable for transmission over the free-space channel. In the present work the TF-QKD protocol is assessed theoretically, implemented with off-the-shelf components for 1 bit/photon and free-space transmission with optical tracking over a 388 m testbed is demonstrated in daylight. Using components at hand, secret key rates of 364 kbit/s back-to-back and 9 kbit/s over the free-space channel could be demonstrated.

The Internet of things (IoT) recently blossomed remarkably and has been transforming the everyday physical entities around us into an ecosystem of information that will enrich our lives in unimaginable ways. Authentication is one of the primary goals of security in the IoT and acts as the main gateway to a secure system which transmits confidential and/or private data.This thesis focuses on a Device-to-Device Mutual Authentication Protocol, designed for the smart home network, which is an essential component of communication in the Internet of Things(IoT). The protocol has been developed based on asymmetric cryptography to authenticate the devices in the network and for the devices to agree on a shared secret session key. In order to ensure the security of a communications session between the devices, the session keys are changed frequently - ideally after every communication session. The proposed scheme has been programmed in HLPSL, simulated and its efficiency verified using the SPAN/ AVISPA tool. When SPAN substantiates the protocol simulation and the attacker simulation, the back-ends of the AVISPA tool verifies the safety and security of the proposed authentication protocol. The thesis also evaluates the protocol's security against the attacks successful against protocols proposed by other researchers. / Graduate / 0544 / 0984 / 0537 / pwilson1@uvic.ca

A criptografia de chave pública sem certificado (certificateless) é uma alternativa ao modelo convencional de criptografia assimétrica, pois a autenticação da chave pública ocorre implicitamente durante a execução dos protocolos, sem a necessidade de gerenciamento e distribuição de certificados digitais. Potencialmente reduz custos computacionais e o nível de segurança alcançado é maior quando comparado ao modelo baseado em identidade. Nesta tese de doutorado, modelos formais de segurança para acordo de chave com autenticação sem certificado são aprimorados visando dois objetivos paralelos: (1) aumentar o nível de confiança que usuários podem depositar na autoridade geradora de chaves secretas parciais e (2) viabilizar protocolos que sejam eficientes computacionalmente e com propriedades de segurança relevantes, dentre as quais se inclui resistência a ataques de adversários que têm total controle do canal de comunicação e que podem substituir chaves públicas de usuários por valores arbitrários. Para atestar que as melhorias efetuadas são praticáveis e possibilitam que os objetivos sejam alcançados, novos protocolos são propostos para o caso que envolve dois participantes na comunicação. Os protocolos são provados seguros, usando-se técnica de redução de problemas computacionais. / Certificateless public key cryptography is an alternative model to traditional asymmetric key cryptography, because the public key authentication occurs implicitly during a protocol run, with no need of digital certificates management and distribution. It has the potential to reduce computing costs, and it allows a higher security level than the one in the identity-based model. In this PhD thesis, formal security models for certificateless authenticated key agreement are improved with two independent objectives: (1) to increase the trust level for the partial secret key generating authority on which users rely, and (2) to enable computationally efficient protocols, with significant security properties, such as resistance against attacks from adversaries with full control of the communication channel, and from adversaries who are able to replace users\' public keys by any chosen value. In order to demonstrate that these improvements made are feasible and achieve the objectives, new protocols are proposed in the two-party case. These protocols are proved secure by using reduction techniques for provable security.