Instantiating the GPV-framework
Bachelor thesis
Permanent lenke
https://hdl.handle.net/11250/3020489Utgivelsesdato
2022Metadata
Vis full innførselSamlinger
Sammendrag
De fleste kryptosystemer som brukes i dag baserer sikkerheten sin på ett av tre matematisk vanskelige problemer: faktorisering av store heltall, diskré logarithmer eller elliptisk kurve diskré logaritmer. Disse problemer har vist seg å være vanskelig å løse for klassiske datamaskiner, men blir trivielle for kvantedatamaskiner. Siden kvantedatamaskiner fortsatt er i et tidlig stadie, er det ingen umiddelbar trussel for nåværende kryptosystemer, men post-kvantesikre alternativer har allerede blitt laget. Én av toppkandidatene for å erstatte nåværende kryptosystem er NTRU, som har blitt vist å ikke være svak mot angrep fra kvantedatamaskiner. NTRU er et asymmetrisk kryptosystem, som betyr at vi har to nøkler, én offentlig og én privat for kryptering og dekryptering av data.
GPV-rammeverket (Gentry, Peikert, Vaikuntanathan) er en oppskrift på hvordan man kan lage sikre signaturer fra en privat og en offentlig nøkkel representert som basiser for et gitter. En kryptert melding trenger en måte å verifisere at avsenderen er den den utgir seg for å være, og dette blir gjort ved å legge til en signatur når meldingen sendes. En signatur bør være kort for å minimere størrelse og tiden det tar å lage den, men ikke for kort, ellers kan en angriper gjette seg til en gyldig signatur.
I denne oppgaven beskriver vi hvordan offentlige og private nøkler blir generert i NTRU, hvordan de blir brukt til å kryptere og dekryptere en melding og til slutt hvordan nøklene blir brukt i GPV-rammeverket for å lagre sikre signaturer. Most of the cryptosystems used today bases its security on one of three mathematically hard problems: the factorization of large integers, computing a discrete logarithm, or computing an elliptic curve discrete logarithm. While these problems are hard for classical computers, they have been shown to be easily solved using a quantum computer. Since quantum computing is still in its early stages, there is no immediate threat to our current cryptosystems, but post quantum secure candidates to replace them has already been created. One of the top candidates to replace current cryptosystems is NTRU, which is not known to be vulnerable to attacks on quantum computers. NTRU is an asymmetric cryptosystem, which means that it has pairs of keys, one public and one private to encrypt and decrypt data.
The GPV (Gentry, Peikert, Vaikuntanathan) framework is a description of how to generate secure signatures from a private and a public key represented as bases for a lattice space in matrix form. When a ciphertext is sent, the recipient needs a way to ensure the identity of the sender. This is done by creating a signature s. We want the signature to be as short as possible to minimize the time it takes to create it, but not too short, or an attacker might be able to guess a valid signature. In this paper we will describe how NTRU public and private keys are created and how they are used to encrypt and decrypt messages. We will then look at how they are instantiated in the GPV framework, which will use the NTRU keys to generate signatures for encrypted messages.