arvutiteaduse instituudi lõputööderegister


Lakoonilise nullteadmusargumendisüsteemi optimiseeritud implementatsioon
Nimi Hendri -
Kokkuvõte Käesolevas töös üritame konstrueerida lakoonilise mitteinteraktiivse nullteadmustõestuste süsteemi implementatsiooni. Mitteinteraktiivne nullteadmustõestuste süsteem on protokoll, milles üks osapool, keda kutsutakse tõestajaks, tõestab teistele osapooltele, keda kutsutakse verifitseerijateks, et mingi verifitseerijale esitatud väide on tõene. Nullteadmusprotokoll peab muuhulgas garanteerima, et vastav tõestus ei lekita väite kohta muud informatsiooni peale väite kehvituse. Antud töös käsitleme tõeväärtusskeemide kehtestatavuse probleemi. Tõeväärtusskeemi kehtestatavuse probleem on küsimus selle kohta, kas leidub sisend, millel antud tõeväärtusskeem saab väljundiks väärtuse tõene. Implementeeritud tõestusskeem põhineb Helger Lipmaa tööl \cite{eprint2013:Lipmaa:NIZKSPECC}, mis kasutab tõestuse konstrueerimiseks lineaarkatte programme \emph{(span program)} ja lineaarseid veaparanduskoode. Töös anname ka kerge ülevaate nullteadmustõestuste üldisest olemusest, et ülejäänud töö olemust paremini selgitada. Me konstrueerime mitteadaptiivse versiooni tõestussüsteemist. Lisaks nullteadmustõestusele iseloomulikele omadustele on see versioon kasulik ka verifitseeritava arvutamise saavutamiseks, nagu käsitletud näiteks artiklis \cite{Pinnochio2013:Parno}. Töö algab ülevaatega mitteinteraktiivsest nullteadmusest ning lineaarkatte programmidest. Edasises kirjeldame, kuidas esitada tõeväärtusskeemi kehtestatavuse probleemi kasutades mainitud lineaarkatte programme. Lõpuks kirjeldame oma implementatsiooni, keskendudes olulistele detailidele ning kasutatud teekidele. Töö kokkuvõtteks on jõudlustulemused ning suunad edasisteks täiendusteks.
Lõputöö keel inglise
Lõputöö tüüp Teaduste magister (4+2) Informaatika*
Juhendaja(d) Helger Lipmaa
Kaitsmise aasta 2013
PDF lisad