On Instantiating the Fiat-Shamir Transform with Correlation Intractable Hash Functions
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2024-12-31
Department
Major/Subject
Mathematics
Mcode
Degree programme
Master's Programme in Mathematics and Operations Research
Language
en
Pages
38
Series
Abstract
The Fiat-Shamir transform is a popular method for removing interaction from interactive cryptographic protocols. One area of application are interactive systems where a prover attempts to convince a verifier of the truth of some statement. Such a system is a proof system if no (even inefficient) adversary can, with non-negligible probability, convince the verifier of a false statement, and an argument system if this guarantee only holds for efficient adversaries. The Fiat-Shamir transform is known to be secure when modelling the hash function as a random oracle, even when applied to argument systems. However, in the standard model security proofs face various difficulties, so that the hash function in the Fiat-Shamir transform cannot be securely instantiated for all argument systems [GT04]. When applied to proofs, there are two main candidate hash function properties that allow one to instantiate the hash function in the Fiat-Shamir transform securely: correlation intractability [CGH04] and entropy preservation [BLV06]. This thesis provides an overview of the Fiat-Shamir transform, obstacles to proving its security in the standard model, and constructions of hash functions that would securely instantiate it. Specifically, the main obstacles are limitations placed on seed length of the hash function [CGH04], and a black-box separation result [BGW12] showing that there is no black-box reduction to a standard cryptographic assumption showing that a hash function securely instantiates the Fiat-Shamir transform for proofs. A similar black-box separation result for correlation intractability is stated and proven. Perhaps surprisingly, constructions of correlation intractable hash functions exist. Two of these ([KRR17, PS19]) are analyzed to shed light on the limitations of the black-box separation result. Namely, the notion of correlation intractability can be weakened so that the black-box separation result no longer applies, and for exponential security assumptions the result fails to hold for relevant parameters. Finally, some questions for future research in this area are listed.Fiat-Shamir-muunnos on suosittu tapa poistaa interaktio interaktiivisista protokollista. Yksi sovelluskohde ovat interaktiiviset järjestelmät, joissa todistaja pyrkii vakuuttamaan tarkastajan väitteen olevan totta. Tällaista järjestelmää kutsutaan todistusjärjestelmäksi, jos edes rajoittamaton hyökkääjä ei kykene vakuuttamaan tarkastajaa epätodesta väittämästä yli mitättömällä todennäköisyydellä. Jos tämä takuu pätee vain tehokkaille hyökkääjille, kutsutaan järjestelmää argumenttijärjestelmäksi. Fiat-Shamir-muunnos on turvallinen, kun siinä käytetty tiivistefunktio mallinnetaan satunnaisena funktiona, jopa silloin kun sitä sovelletaan argumenttijärjestelmiin. Turvallisuustodistuksille on kuitenkin esteitä standardimallissa, jossa tiivistefunktion toteuttaa tehokas algorithmi, eikä muunnos ole turvallinen kaikille argumenttijärjestelmille. Kun muunnosta sovelletaan todistusjärjestelmiin, on kaksi pääkandidaattia tiivistefunktion ominaisuuksista, jotka takaisivat sen toteuttavan Fiat-Shamir-muunnoksen turvallisesti: "correlation intractability" (CI) [CGH04] ja "entropy preservation" (EP) [BLV06]. Tämä diplomityö tarkastelee Fiat-Shamir-muunnosta, esteitä sen turvalliseksi todistamiseksi standardimallissa ja tiivistefunktiokonstruktioita, jotka toteuttavat Fiat-Shamir-muunnoksen turvallisesti. Pääesteitä on kaksi: 1) rajoitteet tiivistefunktion seed-arvon pituudelle [CGH04] ja 2) mustan laatikon erotustulos (eng. black box separation) [BGW12], joka näyttää, ettei mikään mustan laatikon reduktiotodistus kykene näyttämään, että tiivistefunktion toteuttaisi Fiat-Shamir-muunnoksen turvallisesti kaikille todistusjärjestelmille. Vastaava tulos CI-ominaisuudelle esitetään ja todistetaan. Yllättäen CI-tiivistefunktioille on konstruktioita. Kahta näistä ([KRR17, PS19]) analysoidaan mahdottomuustulosten kontekstissa. CI-ominaisuutta voidaan heikentää niin, ettei tulos enää päde, ja voidaan käyttää eksponentiaalisen turvallisuuden takaavia oletuksia. Lopuksi esitellään mielenkiintoisia avoimia kysymyksiä.Description
Supervisor
Brzuska, ChrisThesis advisor
Hieta-aho, ErikKeywords
correlation intractability, hash functions, non-interactive zero knowlege proofs, The Fiat-Shamir transform, random oracle model, cryptography