pipette
ENEnglish

Delegating Computation with Approximate Arithmetic: Interactive Proofs for Wizards

Aritra Das, Debayan Gupta, Arup Mondal, Mihir More

PreprintDice ser un gran avance

En palabras de los autores

We study interactive proofs for arithmetic circuits over the complex numbers in which both the prover and the verifier compute approximately (unlike muggles, wizards can use magic, i.e., floating-point numbers). The goal is to prove that a claimed output is close to the exact output : for thresholds , the honest prover is accepted whenever , and every prover is rejected with high probability whenever . Existing proof systems for real-valued data verify rounded finite-field computations. Bitan et al.~[EUROCRYPT~2026] gave an approximate sum-check protocol. We extend the protocol of Goldwasser, Kalai, and Rothblum (GKR) [STOC~2008] to public-coin interactive proofs for logspace-uniform layered circuits over of size , depth , and inputs, under public bounds on gate values and wiring coefficients. At constant soundness error, the verifier runs in time , the communication is , and the prover runs in time , where is the bit precision. To the best of our knowledge, these are the first doubly efficient interactive proofs in which both parties compute approximately. GKR reduces two claims about a layer to one on a random line, which leaves the unit circle, where our error bounds hold. We instead label gates by complex roots of unity and combine the two claims with a random root of unity as coefficient. We choose the error thresholds backward from the input layer, so that a large output error survives the verifier's rounding at every step. The honest prover needs only complex operations. We also obtain zero-knowledge proofs from one-way functions, one-round arguments from private information retrieval, and interactive PCPs whose proof length is polynomial in the witness length.

Resultado principalLimitación que admiten los autores

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.