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 等数据库收录! |
|