Lattice-Based Zero-Knowledge Proofs From Commitments

Abstract

Hovedformålet med denne oppgaven er å studere den nyeste lattice baserte zero-knowledge protokollen som ble introdusert av Lyubashevsky, Nguyen og Plançon. Vi starter med å introdusere de kryptografiske definisjonene og den matematiske teorien vi trenger. For å oppnå full forståelse av protokollen, ser vi på noen tidligere lattice baserte zero-knowledge protokoller som førte frem til denne. Alle disse protokollene bruker lattice baserte commitment systemer, og vi vier ett kapittel til å se på to ulike commitment systemer for lattice elementer og tilhørende bevis av åpning. I det siste kapittelet kommer vi frem til en praktisk protokoll som kan bli brukt i en mengde ulike lattice baserte kryptografiske systemer.

The main purpose of this thesis is to study the state of the art lattice-based zero-knowledge protocol that was given by Lyubashevsky, Nguyen and Plançon. We start by introducing the cryptographic definitions and mathematical theory that we need. In order to fully understand the scheme, we look at some of the previous lattice-based zero-knowledge schemes that lead up to it. All of these protocols uses lattice-based commitment schemes, and we dedicate a chapter to look at two commitment schemes for lattice elements and their opening proofs. In the final chapter we end up with a practical protocol that can be used in a variety of lattice-based cryptographic systems.