prikaz prve stranice dokumenta Interaktivni dokazi
  Download
PDF 252.54 KB
master's thesis
Interaktivni dokazi
Zagreb: University of Zagreb, Faculty of Science, 2022. urn:nbn:hr:217:018568
Žufić, Ivan
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Žufić, I. (2022). Interaktivni dokazi (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:018568

Žufić, Ivan. "Interaktivni dokazi." Master's thesis, University of Zagreb, Faculty of Science, 2022. https://urn.nsk.hr/urn:nbn:hr:217:018568

Žufić, Ivan. "Interaktivni dokazi." Master's thesis, University of Zagreb, Faculty of Science, 2022. https://urn.nsk.hr/urn:nbn:hr:217:018568

Žufić, I. (2022). 'Interaktivni dokazi', Master's thesis, University of Zagreb, Faculty of Science, accessed 16 May 2024, https://urn.nsk.hr/urn:nbn:hr:217:018568

Žufić I. Interaktivni dokazi [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2022 [cited 2024 May 16] Available at: https://urn.nsk.hr/urn:nbn:hr:217:018568

I. Žufić, "Interaktivni dokazi", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2022. Available at: https://urn.nsk.hr/urn:nbn:hr:217:018568

Metadata
TitleInteraktivni dokazi
Title (english)Interactive proof
AuthorIvan Žufić
MentorMarko Horvat (mentor)
Committee memberMarko Horvat (predsjednik povjerenstva)
Committee memberZvonko Iljazović (član povjerenstva)
Committee memberNenad Antonić (član povjerenstva)
Committee memberHrvoje Planinić (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2022-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
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:018568
Study programmeTitle: 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 resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2022-06-09 10:26:17