Abstrakt. Verifierbara slumpmässiga funktioner (VRFs), som introduceras av Micali, Rabin och Vadhan, är pseudorandom funktioner där ägaren av fröet producerar en offentlig nyckel som utgör ett åtagande till alla värden av funktionen och sedan kan producera, för alla indata x, ett bevis på att funktionen har utvärderats korrekt på x, bevara pseudorandomness för alla andra ingångar. Ingen öppen nyckel (även en felaktigt genererad) bör göra det möjligt att bevisa mer än ett värde per insats. VRF är både en naturlig och en användbar primitiv, och tidigare arbeten har föreslagit en mängd olika konstruktioner och tillämpningar. Ändå finns det många öppna frågor i studien av VRFs, särskilt deras förhållande till mer allmänt studerade kryptografiska primitiver och bygga dem från en mängd olika kryptografiska antaganden. I detta arbete definierar vi en naturlig avkoppling av VRFs som vi kallar svaga kontrollerbara slumpmässiga funktioner, där pseudorandomness krävs för att hålla endast för slumpmässigt utvalda ingångar. Vi genomför en studie av svaga VRFs, med fokus på tillämpningar, konstruktioner, och deras förhållande till andra kryptografiska primitiva. Vi visar: -Byggen. Vi presenterar konstruktioner av svaga VRFs baserat på en mängd olika antaganden, inklusive allmänna antaganden såsom (förstärkta) fällan permutationer, samt konstruktioner baserade på specifika tal-teoretiska antaganden såsom Diffie-Hellman antagande i bilinjära grupper. - Separationer. Verifierbara slumpmässiga funktioner (både svaga och standard) kan inte konstrueras från enkelriktade permutationer på ett svartboxigt sätt. Detta utgör det första resultatet som separerar (standard) VRF från någon kryptografisk primitiv. -Ansökningar. Svaga VRFs fångar essensen av att bygga icke-interaktiv noll-kunskap bevis för alla NP språk.
Brabrski, Goldwasser, Rothblum och Vaikuntanatan REF införde en avslappning av VRFs som de kallade svaga VRFs.
V.: Weak verifiable random functions
{'venue': 'TCC', 'journal': None, 'mag_field_of_study': ['Computer Science']}