Carregant...
Tipus de document
Treball de fi de grauData de publicació
Llicència de publicació
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/220361
A formal introduction to zero-knowledge proofs
Títol de la revista
Autors
Director/Tutor
ISSN de la revista
Títol del volum
Recurs relacionat
Resum
The idea of zero-knowledge proof was first introduced by Goldwasser, Micali and Rackoff [GMR89] and has found its way to many real-world applications. The growing need for privacy in information exchange (e.g. transactions, digital signatures, commitment schemes, ...) lead to the development of proofs that yield nothing more than their validity.
We introduce the building blocks for zero-knowledge proofs through mathematical rigour, allowing the reader to gain a solid foundation to research further related topics. We explore some necessary notions of cryptography and probability, as well as computation theory by utilizing Turing machines as an automation abstraction. We delve into the theory of decision problems and the consequent classification through complexity classes, specially $\mathcal{P}, \mathcal{N} \mathcal{P}, \mathcal{B} \mathcal{P} \mathcal{P}$ and $\mathcal{I P}$. We use the concepts of repetition and interaction to prove that the decision error for languages in $\mathcal{B P} \mathcal{P}$ and $\mathcal{I P}$ can be decreased exponentially and explore the example of Graph Non-Isomorphism. We introduce the idea of zero-knowledge interactive proof systems and define some variations of its definition. We explore the example of Graph Isomorphism and conclude showing that the sequential repetition of zero-knowledge interactive proofs is indeed a zero-knowledge interactive proof.
Descripció
Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2024, Director: Bruno Mazorra i Luis Victor Dieulefait
Matèries (anglès)
Citació
Col·leccions
Citació
PESO VILELLA, Antonio. A formal introduction to zero-knowledge proofs. [consulta: 20 de gener de 2026]. [Disponible a: https://hdl.handle.net/2445/220361]