Abstrakt. När moderna datorer rör sig mot mindre enheter och kraftfulla molnplattformar delegeras allt fler beräkningar till kraftfulla tjänsteleverantörer. Interaktiva bevis är en allmänt använd modell för att utforma effektiva protokoll för kontrollerbar beräkningsdelegation. Rationella bevis är betalningsbaserade interaktiva bevis. Betalningarna är utformade för att uppmuntra provtagarna att ge korrekta svar. Om provtagare felrapportera svaret då de ådrar sig en betalningsförlust på minst 1/u, där u är nytta gapet i protokollet. I detta arbete karakteriserar vi starkt kraften hos rationella bevis som är supereffektiva, det vill säga kräver bara logaritmisk tid och kommunikation för verifiering. Vi karakteriserar också kraften i enkelsidiga rationella protokoll som endast kräver logaritmiskt utrymme och slumpmässighet för verifiering. Våra protokoll har stark (det vill säga polynom, logaritmisk, och även konstant) nytta gap. Slutligen visar vi när och hur rationella protokoll kan konverteras för att ge fullständighet och soliditet garantier för klassiska interaktiva bevis.
I uppföljningsarbetet REF, författarna skala ner kraften i kontrollören och design super-effektiv MRIP protokoll med starka nytta-gap garantier.
Efficient Rational Proofs with Strong Utility-Gap Guarantees
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}