Show simple item record

dc.contributor.advisorGligoroski, Danilo
dc.contributor.advisorVeroni, Mattia
dc.contributor.authorSridhar, Sahana
dc.date.accessioned2021-09-23T19:12:41Z
dc.date.available2021-09-23T19:12:41Z
dc.date.issued2021
dc.identifierno.ntnu:inspera:67987299:34461465
dc.identifier.urihttps://hdl.handle.net/11250/2781184
dc.description.abstractSikkerhet og personvern på internett som vi kjenner i dag, er truet av den nye teknologien for å bygge større og kommersielle kvantecomputere. Selv om kvantecomputere som er bygget er relativt små, og ikke veldig effektive for å forstyrre Public Key Infrastructure, er det likevel viktig å gjenkjenne den forestående trusselen. Dessuten har de berømte kvantealgoritmene på grunn av Shor, Grover og Brassard-Høyer-Tapp, rystet de klassiske grunnlagene for kryptografi med offentlig nøkkel. Disse årsakene har utløst NIST til å stå i spissen for PQC Standardiseringsprosjektet, for å muliggjøre kvalitetsutvikling og raskere distribusjon av kvantesikre kryptosystemer. Dette er for tiden i tredje runde med 7 finalister og 8 alternative kandidater - både nøkkelutvekslingsmekanismer og ordninger for digital signatur. For å forstå fremtiden for offentlig nøkkelkryptografi i post-quantumverdenen, ville den naturlige tilnærmingen være å utforske forskjellige matematiske problemer som ennå ikke kan løses av kvantecomputere. Bygget på denne forutsetningen presenterer denne avhandlingen en teoretisk studie av kryptografiske harde problemer som angivelig er kvantebestandige, og NIST runde 3 PQC signaturskjemaer konstruert av dem. For å forstå de praktiske implikasjonene av disse ordningene, er det i tillegg gjort en helhetlig evaluering av sikkerhetssikring og ytelse som en del av dette arbeidet. Open source-verktøy, som Open Quantum Safe (OQS)-prosjektet og PQClean, har blitt brukt i forbindelse med Dockercontainere for å evaluere disse ordningene kvantitativt. For å adressere den første delen av de ovennevnte forskningsspørsmålene, har kategoriene av kvantebestandige kryptografiske systemer blitt studert, nemlig (i) Latticebasert (ii) Multivariate kvadratiske (MQ) polynomer basert (iii) Hash-basert (iv) Kodebasert og (v) Isogeny-basert. I den andre delen har de seks signaturskjemaene blitt studert, som er (a) Hash / Symmetric-primitive based - Picnic og Sphincs+ (b) MQ polynomials based - GeMSS og Rainbow (c) Latticebasert - Crystals-Dilithium og Falcon. Opprinnelig inspirert av den enkle konstruksjonen av Picnic, har de 3 alternative kandidatene (i.e. Picnic, Sphincs+ og GeMSS) i NIST Round III blitt studert mer detaljert sammenlignet med finalistene (i.e. Dilithium, Falcon og Rainbow) som en del av dette arbeidet. Senere ble denne avgjørelsen også styrt av utviklingen i NIST PQC-standardiseringen, og nysgjerrigheten rundt hvorfor Picnic og de to andre ordningene ikke gjorde det som finalister. I tillegg til de kryptografiske konstruksjonene, har robustheten til ordningene gjennom deres sikkerhetsbevis og deres sårbarhet i forhold til forskjellige angrep også blitt diskutert. Videre ble det under den kvantitative analysen av ordningene innsett at GeMSS for øyeblikket ikke er i Liboqs-biblioteket til OQS. Derfor ble integrering av GeMSS i Liboqs, for å tillate evaluering av alle seks ordningene på en felles plattform og i kryptografiske protokoller som TLS, et av målene med dette arbeidet. På grunn av et nylig alvorlig nøkkelgjenopprettingsangrep [Tao et. al., IACR Cryptol. ePrint Arch 1424 (2020)] på det underliggende problemet med GeMSS, har denne oppgaven blitt ansett som irrelevant for nå. Den delvise implementeringen som er gjort til det punktet å vite om angrepet, har blitt presentert. Likevel er det gjort en omfattende sammenligning av alle de seks ordningene under hensyntagen til programvaren og maskinvarensimplementeringskompleksitet i disse ordningene. Observasjonen fra den kvantitative analysen av skjemaene har vært at Dilithium i programvareimplementeringer er den klart beste algoritmen når det gjelder ytelse og størrelse på komponentene (nøkler og signaturer). Imidlertid ser Rainbow ut til å ha veldig god ytelse i høyhastighets maskinvareimplementeringer. I denne forbindelse, til tross for at de er konstruert av enklere kryptografiske primitiver, har Picnic og Sphincs+ gjennomsnittlig ytelse sammenlignet med andre ordninger i begge plattformene. Når det gjelder den kvalitative analysen, er hver ordning sårbar for forskjellige angrep, og styrken og sikkerheten til en ordning bestemmes av dens evne til å motvirke kraftige angrep. Selv om symmetrisk baserte ordninger generelt antas å være kvantebestandige, og bare trenger å doble parametrene for å være sikre, er de fremdeles sårbare for angrep med flere mål. MQ-polynombaserte ordninger er derimot utsatt for angrep som utnytter deres matematiske konstruksjoner. Mens de latticebaserte ordningene er robuste når det gjelder konstruksjon, kan implementeringene være kompliserte og utsatt for generiske feil og sidekanalangrep som alle andre ordninger.
dc.description.abstractSecurity and privacy in the internet as we know today, is under threat from the emerging technology of building larger and commercial quantum computers. Even though the quantum computers built are relatively small, and not very effective to disrupt the Public Key Infrastructure, nevertheless, it is important to recognize the imminent threat. Besides, the famous quantum algorithms due to Shor, Grover and Brassard-Høyer-Tapp, have shaken the classical foundations of public-key cryptography. These reasons have triggered NIST to spearhead the Post-Quantum Cryptography (PQC) Standardization project, to enable quality development and faster deployment of quantum-safe cryptosystems. This is currently in the third round with 7 finalists and 8 alternative candidates – both key-exchange mechanisms and digital signature schemes. To understand the future of public-key cryptography in the postquantum world, the natural approach would be to explore different mathematical problems that cannot be solved by quantum computers, yet. Built on this premise, this thesis presents a theoretical study of cryptographic hard problems that are allegedly quantum-resistant, and the NIST round 3 PQC signature schemes constructed from them. Additionally, in order to understand the practical implications of these schemes, a holistic evaluation in terms of security assurance and performance has been done as part of this work. Open source tools, such as the Open Quantum Safe (OQS) project and PQClean, have been used in conjunction with Docker containers to evaluate these schemes quantitatively. To address the first part of the above research questions, the categories of quantum-resistant cryptographic systems have been studied, namely, (i) Lattice-based (ii) Multivariate quadratic (MQ) polynomials based (iii) Hash-based (iv) Code-based and (v) Isogeny-based. In the second part, the six signature schemes have been studied, which are (a) Hash/Symmetric-primitive based - Picnic and Sphincs+ (b) MQ polynomials based - GeMSS and Rainbow (c) Lattice-based - Crystals-Dilithium and Falcon. Initially inspired by the simple construction of Picnic, the 3 alternate candidates (i.e. Picnic, Sphincs+ and GeMSS) in NIST Round III have been studied in more detail compared to the finalists (i.e. Dilithium, Falcon and Rainbow) as part of this work. Later, this decision was also guided by the progression in the NIST PQC standardization, and the curiosity about why Picnic and the two other schemes did not make it as finalists. Along with the cryptographic constructions, the robustness of the schemes through their proofs of security, and their vulnerabilities in terms of different attacks have also been discussed. Furthermore, during the quantitative analysis of the schemes, it was realized that GeMSS is not currently in the Liboqs library of OQS. Therefore, integrating GeMSS into Liboqs, to allow for evaluation of all six schemes on a common platform and in cryptographic protocols such as TLS became one of the objectives of this work. However, due to a recent serious key recovery attack [Tao et. al., IACR Cryptol. ePrint Arch 1424 (2020)] on the underlying problem of GeMSS, this task has been deemed irrelevant for now. The partial implementation done upto the point of knowing about the attack has been presented. Nevertheless, a comprehensive comparison of all six schemes has been done taking into consideration, the software and hardware implementation complexities of these schemes. The observation from the quantitative analysis of the schemes has been that, in software implementations, Dilithium is by far the best algorithm in terms of performance and sizes of the components (keys and signatures). However, Rainbow seems to have very good performance in high-speed hardware implementations. In this regard, despite being constructed from simpler cryptographic primitives, Picnic and Sphincs+ have average performances compared to other schemes in either platforms. As for the qualitative analysis, each scheme is vulnerable to various attacks, and the strength and security of a scheme is determined by its ability to counter powerful attacks. Though symmetric-based schemes are generally believed to be quantum-resistant, needing only to double their parameters to be secure, they are still vulnerable to multi-target attacks. The MQ-polynomial based schemes on the other hand, are subject to attacks that exploit their mathematical constructions. While the lattice-based schemes are robust in terms of construction, their implementations can be complicated and subject to generic fault and side-channel attacks like any other scheme.
dc.languageeng
dc.publisherNTNU
dc.titleA Survey of Quantum-safe Digital Signatures and their building blocks
dc.typeMaster thesis


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record