首页 | 本学科首页   官方微博 | 高级检索  
     


Short PCPPs verifiable in polylogarithmic time with O(1) queries
Authors:Thilo Mie
Affiliation:1. Institut für Kryptographie und Sicherheit, Universit?t Karlsruhe (TH), Am Fasanengarten 5, 76131, Karlsruhe, Germany
Abstract:In this paper we show for every pair language $L\subseteq \{0,1\}^*\times\{0,1\}^*$ in ${\ensuremath{\mathsf{NTIME}}}(T)$ for some non-decreasing function $T:{{\mathbb Z}}^+\rightarrow {{\mathbb Z}}^+$ there is a ${\ensuremath{\mathsf{PCPP}}}$ -verifier such that the following holds. In time poly (|x|,log|y|,logT(|x|?+?|y|)) it decides the membership of a purported word (x,y) by reading the explicit input x entirely and querying the implicit input y and the auxiliary proof of length T(|x|?+?|y|)·poly log T(|x|?+?|y|) in a constant number of positions.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号