Lattice-Based Zero Knowledge

Abstract

Vi presenterer 3 protokoller som benytter seg av lattice-basert zero-knowledge. Disse protokollene baserer sin sikkerhet på at det er vanskelig å løse det tilnærmede korteste vektor problemet, og kort heltallsløsning problemet. Den første protokollen er en identifikasjonsprotokoll, der vi overbeviser en mottaker om at vi kjenner til en spesifikk hemmelig nøkkel s. Den andre protokollen får vi ved å bruke en Fiat-Shamir transformasjon på den første protokollen, og får da en zero-knowledge protokoll uten interaksjon mellom sender og mottaker. Den siste protokollen er et argument of knowledge for å kjenne inputs som tilfredsstiller en aritmetisk krets. Vi presenterer også diverse teori som er nødvendig for at disse protokollene skal virke, og eksempler som illustrerer hva vi prøver å oppnå i noen av de mer kompliserte delene av konstruksjonene.

We present 3 schemes using lattice-based zero-knowledge, using the difficulty of the Approximate Shortest Vector Problem and the Short Integer Solution Problem. The first scheme is an identification scheme, proving knowledge of a secret key s. The second scheme is a signature scheme obtained by applying the Fiat-Shamir transform on the identification scheme to create a non-interactive zero-knowledge scheme. The last scheme is an argument of knowledge for the satisfiability of an arithmetic circuit. We also present various theory necessary for these algorithms to work, as well as examples illustrating what we are trying to accomplish in some of the more complicated parts of the constructions.