?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.title=Arya%3A+Nearly+linear-time+zero-knowledge+proofs+for+correct+program+execution&rft.creator=Bootle%2C+J&rft.creator=Cerulli%2C+A&rft.creator=Groth%2C+J&rft.creator=Jakobsen%2C+S&rft.creator=Maller%2C+M&rft.description=There+have+been+tremendous+advances+in+reducing+interaction%2C+communication+and+verification+time+in+zero-knowledge+proofs+but+it+remains+an+important+challenge+to+make+the+prover+efficient.+We+construct+the+first+zero-knowledge+proof+of+knowledge+for+the+correct+execution+of+a+program+on+public+and+private+inputs+where+the+prover+computation+is+nearly+linear+time.+This+saves+a+polylogarithmic+factor+in+asymptotic+performance+compared+to+current+state+of+the+art+proof+systems.%0D%0A%0D%0AWe+use+the+TinyRAM+model+to+capture+general+purpose+processor+computation.+An+instance+consists+of+a+TinyRAM+program+and+public+inputs.+The+witness+consists+of+additional+private+inputs+to+the+program.+The+prover+can+use+our+proof+system+to+convince+the+verifier+that+the+program+terminates+with+the+intended+answer+within+given+time+and+memory+bounds.+Our+proof+system+has+perfect+completeness%2C+statistical+special+honest+verifier+zero-knowledge%2C+and+computational+knowledge+soundness+assuming+linear-time+computable+collision-resistant+hash+functions+exist.+The+main+advantage+of+our+new+proof+system+is+asymptotically+efficient+prover+computation.+The+prover%E2%80%99s+running+time+is+only+a+superconstant+factor+larger+than+the+program%E2%80%99s+running+time+in+an+apples-to-apples+comparison+where+the+prover+uses+the+same+TinyRAM+model.+Our+proof+system+is+also+efficient+on+the+other+performance+parameters%3B+the+verifier%E2%80%99s+running+time+and+the+communication+are+sublinear+in+the+execution+time+of+the+program+and+we+only+use+a+log-logarithmic+number+of+rounds.&rft.subject=Zero-knowledge+proofs%2C+Succinct+arguments+of+knowledge%2C+TinyRAM%2C+Ideal+linear+commitments%2C+Post-quantum+security&rft.publisher=Springer&rft.contributor=Peyrin%2C+T&rft.contributor=Galbraith%2C+S&rft.date=2018-10-27&rft.type=Proceedings+paper&rft.language=eng&rft.source=+++++In%3A+Peyrin%2C+T+and+Galbraith%2C+S%2C+(eds.)+Advances+in+Cryptology+%E2%80%93+ASIACRYPT+2018%3A+24th+International+Conference+on+the+Theory+and+Application+of+Cryptology+and+Information+Security%2C+Brisbane%2C+QLD%2C+Australia%2C+December+2%E2%80%936%2C+2018%2C+Proceedings%2C+Part+I.++(pp.+pp.+595-626).++Springer%3A+Cham%2C+Switzerland.+(2018)+++++&rft.format=text&rft.identifier=https%3A%2F%2Fdiscovery.ucl.ac.uk%2Fid%2Feprint%2F10063978%2F1%2FZKRAM-Asiacrypt2018-Final.pdf&rft.identifier=https%3A%2F%2Fdiscovery.ucl.ac.uk%2Fid%2Feprint%2F10063978%2F&rft.rights=open