O síle algebraických grupových modelů
On the power of algebraic group models
diploma thesis (DEFENDED)

View/ Open
Permanent link
http://hdl.handle.net/20.500.11956/199269Identifiers
Study Information System: 282808
Collections
- Kvalifikační práce [11963]
Author
Advisor
Referee
Příhoda, Pavel
Faculty / Institute
Faculty of Mathematics and Physics
Discipline
Mathematics for Information Technologies
Department
Computer Science Institute of Charles University
Date of defense
2. 6. 2025
Publisher
Univerzita Karlova, Matematicko-fyzikální fakultaLanguage
Czech
Grade
Excellent
Keywords (Czech)
algebraický grupový model|extrahovatelnost|nevědomé samplování|závazek k polynomuKeywords (English)
algebraic group model|extractability|oblivious sampling|polynomial commitment schemeV této práci zkoumáme sílu dvou idealizovaných kryptografických modelů-Algebraic- kého Grupového Modelu (AGM), který představili Fuchsbauer, Kiltz a Loss (CRYPTO 2018), a jeho rozšíření AGMOS, které představili Lipmaa, Parisella a Siim (TCC 2023). Speciální pozornost věnujeme důkazům bezpečnostních vlastností závazků k polynomům. Předkládáme formální tvrzení, které naznačuje, že AGM je příliš silný pro smysluplnou analýzu závazků k polynomům. Dále se věnujeme modelu AGMOS. Pokračujeme ve for- malizaci důkazové techniky, kterou představili Lipmaa et al. Pro určitou třídu bezpeč- nostních her dokazujeme, že důkaz bezpečnosti v AGM lze "zdvihnout" do AGMOS.
In this thesis, we examine the power of two recent idealized cryptographic models-the Algebraic Group Model (AGM) of Fuchsbauer, Kiltz, and Loss (CRYPTO 2018) and its extension AGM with Oblivious Sampling (AGMOS) of Lipmaa, Parisella, and Siim (TCC 2023). Special attention is given to proofs of security properties of polynomial commitment schemes (PCSs). We give formal evidence to the intuition that the AGM is too powerful for a meaningful analysis of PCSs. Moving on to the AGMOS, we further formalize the proof technique of Lipmaa et al. For a certain class of security games, we prove that an AGM proof of security can be "lifted" to the AGMOS.