A short PCP of proximity for reed-solomon codes over any large field

Probabilistically Checkable Proofs (PCPs) are an elegant, information-theoretic tool that has recently found fruitful applications in the realm of delegation of computation (e.g., blockchain, e-voting, etc.). The construction of concise proofs is a formidable challenge, and the current frontier is exemplified by the work of Ben-Sasson and Sudan, achieving a quasilinear proof length relative to the size of the instance. In this study, we conduct an in-depth analysis of a fundamental component of that construction: the low-degree test. We enhance the understanding of this essential building block by introducing potential attack scenarios that illuminate instances where the test could fail, while also elucidating the limitations of these cases. Moreover, we surmount a primary obstacle of the test by removing the constraints of a smooth field. To attain this improvement, we draw inspiration from the application of elliptic curves to Interactive Oracle Proofs (IOP). To our knowledge, this technique has never been applied to any PCP construction. Ultimately, our efforts yield a PCP sharing the same parameters while being unburdened by field constraints, resulting in a more adaptable and versatile tool.

Probabilistically Checkable Proofs (PCPs) sono un elegante information-theoretic strumento che ha recentemente trovato fruttuose applicazioni nel regno della delegation of computation (ad esempio, blockchain, e-voting, ecc.). La costruzione di proof concise è una sfida formidabile e lo stato dell'arte è esemplificato dal lavoro di Ben-Sasson e Sudan, che hanno raggiunto una proof length quasilineare rispetto alla dimensione del witness. In questo lavoro, analizziamo in modo approfondito una componente fondamentale di questa costruzione: il low-degree test. Miglioriamo la comprensione di questo elemento essenziale introducendo potenziali scenari di attacco che illuminano i casi in cui il test potrebbe fallire, chiarendo anche i limiti di questi casi. Inoltre, superiamo un ostacolo primario del test liberandolo dai vincoli di un campo con piccoli fattori. Per ottenere questo miglioramento, ci ispiriamo all'applicazione delle curve ellittiche alle Interactive Oracle Proofs (IOP). A nostra conoscenza, questa tecnica non è mai stata applicata a una costruzione di PCP. In definitiva, i nostri sforzi producono una PCP che condivide gli stessi parametri e che non è gravato da vincoli sul campo, risultando in uno strumento più adattabile e versatile.