Interaktivni dokazi

master's thesis

• Title (english): Interactive proof
• Author: Ivan Žufić
• Mentor: Marko Horvat (mentor)
• Committee member: Marko Horvat (predsjednik povjerenstva)
• Committee member: Zvonko Iljazović (član povjerenstva)
• Committee member: Nenad Antonić (član povjerenstva)
• Committee member: Hrvoje Planinić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2022-05-05, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu opisujemo IP, klasu problema rješivih u polinomnom vremenu koristeći sustave interaktivnih dokaza. Sustavi interaktivnih dokaza koriste interakciju dva stroja, dokazivača i verifikatora, za odlučivanje pripadnosti neke riječi nekom formalnom jeziku. Dokazivač je stroj s neograničenim vremenskim i memorijskim računskim mogućnostima, dok je verifikator Turingov stroj kojem dodatno omogućavamo generiranje slučajnih bitova. Dokazivač pokušava uvjeriti verifikatora u pripadnost riječi jeziku, dok verifikator pokušava provjeriti istinitost te tvrdnje. Za razliku od mnogih drugih klasa, dopuštamo verifikatoru malu mogućnost pogreške. Omogućavanje generiranja slučajnih bitova i dopuštanje pogrešaka možda ne izgleda značajno, ali ispostavlja se da je klasa IP ekvivalentna klasi PSPACE, što i dokazujemo u ovom radu. Razmatramo i varijantu interaktivnih dokaza u kojoj su verifikatorovi slučajno generirani bitovi javno dostupni. U posljednjem poglavlju navodimo neke primjene interaktivnih dokaza u kriptografiji.

Abstract (english)

In this paper, we present IP, the class of problems solvable in polynomial time using interactive proof systems. Interactive proof systems use the interaction of two machines, a prover and a verifier, to check if some word is in some formal language. The prover is a machine with unlimited computing power, while the verifier is a Turing machine which can generate random bits. The prover’s task is to convince the verifier that the word is indeed in the language, while the verifier’s task is to check the truthfulness of that claim. We allow a small chance of the verifier failing in its task. Enabling random bit generation and allowing mistakes might look insignificant, but it turns out that the class IP is equivalent to the class PSPACE, which we prove in this paper. We also consider a variant of interactive proofs in which the verifier’s randomly generated bits are publicly available to the prover. In the final chapter, we mention some applications of interactive proofs in cryptography.

• Keywords: dokazivač; verifikator; Turingov stroj; klasa IP; klasa PSPACE; kriptografija
• Keywords (english): prover; verifier; Turing machine; class IP; class PSPACE; cryptography
• Language: croatian
• URN:NBN: urn:nbn:hr:217:018568
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2022-06-09 10:26:17