Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes - Laboratoire d'informatique de l'X (LIX) Accéder directement au contenu
Article Dans Une Revue Designs, Codes and Cryptography Année : 2022

Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

Résumé

We consider the proximity testing problem for error-correcting codes which consist in evaluations of multivariate polynomials either of bounded individual degree or bounded total degree. Namely, given an oracle function f : L m Ñ F q , where L Ă F q , a verifier distinguishes whether f is the evaluation of a low-degree polynomial or is far (in relative Hamming distance) from being one, by making only a few queries to f. This topic has been studied in the context of locally testable codes, interactive proofs, probabilistically checkable proofs, and interactive oracle proofs. We present the first interactive oracle proofs of proximity (IOPP) for tensor products of Reed-Solomon codes (evaluation of polynomials with bounds on individual degrees) and for Reed-Muller codes (evaluation of polynomials with a bound on the total degree). Such low-degree polynomials play a central role in constructions of probabilistic proof systems and succinct non-interactive arguments of knowledge with zero-knowledge. For these applications, highly-efficient multivariate low-degree tests are desired, but prior probabilistic proofs of proximity required super-linear proving time. In contrast, for multivariate codes of length N , our constructions admit a prover running in time linear in N and a verifier which is logarithmic in N. For fixed constant number of variables m, the efficiency parameters of our IOPPs for multivariate codes compare well, all things equal, with those of the IOPP for Reed-Solomon codes of [Ben-Sasson et al., ICALP 2018] from which they are directly inspired.
Fichier principal
Vignette du fichier
paper-eccc.pdf (710.94 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03454113 , version 1 (29-11-2021)

Identifiants

Citer

Daniel Augot, Sarah Bordage, Jade Nardi. Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes. Designs, Codes and Cryptography, 2022, ⟨10.1007/s10623-022-01134-z⟩. ⟨hal-03454113⟩
233 Consultations
334 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More