Original title:
Schémata závazků k polynomům více proměnných
Translated title:
Multivariate polynomial commitment schemes
Authors:
Bžatková, Kateřina ; Hubáček, Pavel (advisor) ; Žemlička, Jan (referee) Document type: Master’s theses
Year:
2022
Language:
eng Abstract:
[eng][cze] This thesis focuses on polynomial commitment schemes - cryptographic protocols that allow committing to a polynomial and, subsequently, proving the correctness of evaluations of the committed polynomial at requested points. As our main results, we present new schemes that enable committing to multivariate polynomials and efficiently proving the correctness of evaluations at multiple points. As the main technical tools for our constructions, we use theorems from abstract algebra related to ideals of polynomial rings and some group-theoretic properties. Compared to the state-of-the-art that inspired our work, our main contribution is the improved communication complexity achieved by our protocol.Tato diplomová práce se zabývá schématy polynomiálních závazků, což jsou schémata umožňující vytvářet polynomiální závazky a následně pomocí spuštění navrženého protokolu důvěryhodně vyhodnocovat polynomy v požadovaných bodech. Jako náš hlavní výsledek navrhujeme nové schéma, které umožňuje pracovat s polynomy více proměnných a efektivně dokazovat korektnost vyhodnocení polynomu ve více bodech. Vytvoření našeho schématu vedlo k využití poznatků z teorie algebry, především zabývající se vlastnostmi ideálů v polynomiálních okruzích a grupovými vlastnostmi. V porovnání s jiným schématem, které je též navrženo pro polynomy více proměnných, se nám podařilo zlepšit komunikační složitost během protokolu.
Keywords:
polynomial commitment schemes|arguments of knowledge|Hilbert's weak Nullstellensatz|Gröbner basis; schémata závazků k polynomům|arguments of knowledge|Slabá Hilbertova věta o nulách|Gröbnerovy báze
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/176780