Security of Signatures in The Quantum Random Oracle Model

Abstract

Målet med denne oppgaven er å studere beviselig sikkerhet i \emph{post-kvante kryptografi} (PQC) og andvende dette mot CRYSTALs gitter baserte signatur Dilithium. Først definerer vi den nødvendige teorien for å forstå gittere og det vi anser som vanskelige gitter problemer. Vi vil videre utforske identifikasjon- og signatursystemer og hva sikkerhet betyr. Vi skal se på sikkerhet i både \emph{tilfeldig orakle modellen} (ROM) og \emph{kvante tilfeldig orakel modellen} (QROM). Deretter ser vi på Dilithiums QROM bevis og for sammenligning Lyubashevskys ROM bevis. Til slutt diskuterer vi om QROM er en nødvendig modell for å bevise sikkerhet i kvantesammenheng eller om standard ROM er tilstrekkelig.

The goal for this thesis is to study provable security in Post-Quantum Cryptography (PQC) and apply this to the lattice based CRYSTAL's Dilithium signature. We will develop and explore the necessary theory of lattices and what we consider to be hard lattice problems, before studying identification schemes and signature schemes. Then proceed to explore what security means --- both in the Random Oracle Model (ROM) and the Quantum Random Oracle Model (QROM). We will then look at the QROM security of the Dilithium signature and offer a comparison with the ROM secure Lyubashevsky signature. Lastly we discuss whether the QROM is necessary for proving quantum security or if proofs in the standard ROM is sufficient.