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