pith. sign in

arxiv: 1907.04302 · v1 · pith:TNGR6VC3new · submitted 2019-07-09 · 💻 cs.CC · cs.CR· cs.IT· math.IT

Interactive Verifiable Polynomial Evaluation

Saeid Sahraei , Mohammad Ali Maddah-Ali , Salman Avestimehr This is my paper

Pith reviewed 2026-05-24 23:47 UTC · model grok-4.3

classification 💻 cs.CC cs.CRcs.ITmath.IT
keywords verifiable computationinteractive proofspolynomial evaluationinformation-theoretic soundnesserror-correcting codesdelegated computationcloud computing
0
0 comments X

The pith

An interactive protocol lets a weak client verify a degree-d polynomial evaluation in O(d^ε) time after O(log d) rounds with information-theoretic soundness.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs an interactive protocol that lets a computationally limited client delegate evaluation of a degree-d polynomial to an untrusted server and check the result efficiently. The protocol uses properties of error-correcting codes to convert any false server answer into a false claim about a simpler instance of the same problem. This reduction repeats for roughly log d rounds until the claim reaches a size where it can be checked directly against a precomputed lookup table. The resulting complexities are O(d^ε) for the client, O(d^{1+ε}) for the server, and O(d^{1+ε}) for the one-time initialization, all with soundness that cannot be broken by an unbounded adversary.

Core claim

The central claim is that basic properties of error-correcting codes suffice to build a doubly-efficient interactive proof for polynomial evaluation: any dishonest server response is forced into a sequence of progressively smaller verification problems that terminate at a trusted lookup table after O(log d) rounds, delivering sublinear client work while preserving information-theoretic soundness.

What carries the argument

The iterative reduction step that applies error-correcting code properties to map a false claim on a degree-d polynomial evaluation into a false claim on a lower-degree or smaller instance.

If this is right

  • Client verification cost is O(d^ε) for any ε > 0.
  • Server computation cost remains O(d^{1+ε}).
  • The protocol terminates after O(log d) rounds of interaction.
  • Initialization requires O(d^{1+ε}) work to build the lookup table.
  • Soundness holds against computationally unbounded servers without cryptographic assumptions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction idea may apply to verification of other algebraic functions whose evaluation can be expressed via error-correcting code relations.
  • The lookup table produced in initialization could support repeated queries to the same polynomial without re-initialization.
  • The protocol structure separates the expensive setup from the per-query interaction, which may suit scenarios with infrequent polynomial changes.

Load-bearing premise

The initialization phase produces a correct lookup table that the client can trust.

What would settle it

A concrete polynomial of degree d together with a server strategy that returns an incorrect evaluation value yet produces responses accepted by the client in all rounds and consistent with the lookup table.

Figures

Figures reproduced from arXiv: 1907.04302 by Mohammad Ali Maddah-Ali, Saeid Sahraei, Salman Avestimehr.

Figure 1
Figure 1. Figure 1: Efficient computation of the look-up table. Each box [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of the proposed algorithm. The blu [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
read the original abstract

Cloud computing platforms have created the possibility for computationally limited users to delegate demanding tasks to strong but untrusted servers. Verifiable computing algorithms help build trust in such interactions by enabling the server to provide a proof of correctness of his results which the user can check very efficiently. In this paper, we present a doubly-efficient interactive algorithm for verifiable polynomial evaluation. Unlike the mainstream literature on verifiable computing, the soundness of our algorithm is information-theoretic and cannot be broken by a computationally unbounded server. By relying on basic properties of error correcting codes, our algorithm enforces a dishonest server to provide false results to problems which become progressively easier to verify. After roughly $\log d$ rounds, the user can verify the response of the server against a look-up table that has been pre-computed during an initialization phase. For a polynomial of degree $d$, we achieve a user complexity of $O(d^{\epsilon})$, a server complexity of $O(d^{1+\epsilon})$, a round complexity of $O(\log d)$ and an initialization complexity of $O(d^{1+\epsilon})$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper presents a doubly-efficient interactive protocol for verifiable polynomial evaluation with information-theoretic soundness. Relying on properties of error-correcting codes, a dishonest server is forced into progressively simpler false claims until verification reduces to a lookup in a precomputed table after O(log d) rounds. For a degree-d polynomial the claimed complexities are O(d^ε) user work, O(d^{1+ε}) server work, O(log d) rounds, and O(d^{1+ε}) initialization.

Significance. If the initialization cost can be amortized or removed without compromising information-theoretic soundness, the result would supply a non-cryptographic alternative to existing verifiable-computation schemes for polynomial evaluation, with sublinear client work after setup. The reliance on standard ECC properties rather than cryptographic assumptions is a potential strength.

major comments (2)
  1. [Abstract] Abstract: the stated user complexity O(d^ε) excludes the initialization phase that costs the client O(d^{1+ε}) to produce the trusted lookup table. For a single evaluation (or any number of evaluations smaller than roughly d), this initialization dominates and exceeds the cost of direct O(d) evaluation, contradicting the claim that the protocol is useful for computationally limited clients.
  2. [Abstract] Abstract (paragraph on the algorithm): the central soundness argument assumes the initialization phase produces a correct lookup table that the client can trust without further verification. No mechanism (trusted dealer, public setup, or amortization argument) is described that removes this cost while preserving information-theoretic soundness for a single evaluation; if the client must compute the table itself, the overall complexity is no longer sublinear.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will revise the paper to improve clarity on the role of initialization.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the stated user complexity O(d^ε) excludes the initialization phase that costs the client O(d^{1+ε}) to produce the trusted lookup table. For a single evaluation (or any number of evaluations smaller than roughly d), this initialization dominates and exceeds the cost of direct O(d) evaluation, contradicting the claim that the protocol is useful for computationally limited clients.

    Authors: We agree that the abstract would benefit from greater precision. The stated O(d^ε) user complexity refers exclusively to the cost of the interactive verification phase after the lookup table has already been computed during initialization. The manuscript already reports the initialization cost separately as O(d^{1+ε}). We will revise the abstract to explicitly distinguish the per-evaluation verification cost from the one-time initialization cost and to note that amortization over multiple evaluations is required for the total client work to remain sublinear. revision: yes

  2. Referee: [Abstract] Abstract (paragraph on the algorithm): the central soundness argument assumes the initialization phase produces a correct lookup table that the client can trust without further verification. No mechanism (trusted dealer, public setup, or amortization argument) is described that removes this cost while preserving information-theoretic soundness for a single evaluation; if the client must compute the table itself, the overall complexity is no longer sublinear.

    Authors: The protocol explicitly requires a trusted initialization phase in which the client computes the lookup table; this table is then used for verification in subsequent interactions. Information-theoretic soundness for a single evaluation does require the client to perform this initialization, and the paper does not claim a mechanism (such as a trusted dealer or public setup) that eliminates the cost. We will revise the abstract and add a clarifying paragraph in the introduction to state this assumption explicitly and to discuss amortization over multiple queries as the setting in which sublinear client work is achieved. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external ECC properties

full rationale

The paper states its protocol reduces verification after O(log d) rounds to a lookup table produced in an explicit initialization phase whose cost is separately reported. It invokes only 'basic properties of error correcting codes' (standard external facts) with no equations or steps shown to reduce by construction to fitted parameters, self-definitions, or self-citation chains. The claimed per-evaluation complexities are presented as consequences of the interactive reduction, not as renamings or statistical artifacts of the inputs. This is the normal case of a self-contained protocol description against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The protocol rests on standard properties of error-correcting codes and the correctness of a one-time initialization table; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption Basic properties of error-correcting codes force dishonest responses into progressively easier verification problems
    Invoked in the abstract as the mechanism that reduces verification effort after log d rounds.

pith-pipeline@v0.9.0 · 5721 in / 1128 out tokens · 24376 ms · 2026-05-24T23:47:36.765820+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · 1 internal anchor

  1. [1]

    Proof verification and the hardness of approximation problems

    Arora, S., Lund, C., Motw ani, R., Sudan, M., and Szegedy, M. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM) 45 , 3 (1998), 501–555

    work page 1998

  2. [2]

    Probabilistic checking of proofs: A new characterization o f np

    Arora, S., and Safra, S. Probabilistic checking of proofs: A new characterization o f np. Journal of the ACM (JACM) 45 , 1 (1998), 70–122

    work page 1998

  3. [3]

    Checking computations in polylogarithmic time

    aszl o Babai, L., Fortnow, L., Levin, L., and Szegedy, M. Checking computations in polylogarithmic time. In 23rd Annual ACM Symposium on Theory of Computing (1991), ACM, pp. 21–31

    work page 1991

  4. [4]

    Trading group theory for randomness

    Babai, L. Trading group theory for randomness. In Proceedings of the seventeenth annual ACM symposium on Theory of computing (1985), ACM, pp. 421–429

    work page 1985

  5. [5]

    Backes, M., Fiore, D., and Reischuk, R. M. Verifiable delegation of computation on outsourced data. In Proceedings of the 2013 ACM SIGSAC conference on Computer & co mmunications security (2013), ACM, pp. 863–874

    work page 2013

  6. [6]

    Fast Reed-Solomon interactive oracle proofs of proximity

    Ben-Sasson, E., Bentov, I., Horesh, Y., and Riabzev, M. Fast Reed-Solomon interactive oracle proofs of proximity. In 45th International Colloquium on Automata, Languages, and Pr ogramming (ICALP

    work page

  7. [7]

    (2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informati k

    work page 2018

  8. [8]

    Interactive oracle proofs

    Ben-Sasson, E., Chiesa, A., and Spooner, N. Interactive oracle proofs. In Theory of Cryptography Conference (2016), Springer, pp. 31–60

    work page 2016

  9. [9]

    Short PCPs with polylog query complexity

    Ben-Sasson, E., and Sudan, M. Short PCPs with polylog query complexity. SIAM Journal on Computing 38, 2 (2008), 551–607

    work page 2008

  10. [10]

    Verifiable delegation of computation over large datasets

    Benabbas, S., Gennaro, R., and V ahlis, Y. Verifiable delegation of computation over large datasets. In Annual Cryptology Conference (2011), Springer, pp. 111–131

    work page 2011

  11. [11]

    Succinct non-interactive arguments via linear interactive proofs

    Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., and Ostrovsky, R. Succinct non-interactive arguments via linear interactive proofs. In Theory of Cryptography Conference (2013), Springer, pp. 315– 333

    work page 2013

  12. [12]

    New algorithms for secure outsourcing of modular exponentiations

    Chen, X., Li, J., Ma, J., Tang, Q., and Lou, W. New algorithms for secure outsourcing of modular exponentiations. IEEE Transactions on Parallel and Distributed Systems 25 , 9 (2014), 2386–2396

    work page 2014

  13. [13]

    Efficient techniques for publicly verifiable delegation of computation

    Elkhiyaoui, K., Önen, M., Azraoui, M., and Mol v a, R. Efficient techniques for publicly verifiable delegation of computation. In Proceedings of the 11th ACM on Asia Conference on Computer an d Communications Security (2016), ACM, pp. 119–128

    work page 2016

  14. [14]

    Publicly verifiable delegation of large polynomials and mat rix computations, with applications

    Fiore, D., and Gennaro, R. Publicly verifiable delegation of large polynomials and mat rix computations, with applications. In Proceedings of the 2012 ACM conference on Computer and commu nications security (2012), ACM, pp. 501–512

    work page 2012

  15. [15]

    Non-interactive verifiable computing: Outsourcing computation to untrusted workers

    Gennaro, R., Gentry, C., and Parno, B. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In Annual Cryptology Conference (2010), Springer, pp. 465–482

    work page 2010

  16. [16]

    Quadratic span programs and succinct NIZKs without PCPs

    Gennaro, R., Gentry, C., Parno, B., and Raykov a, M. Quadratic span programs and succinct NIZKs without PCPs. In Annual International Conference on the Theory and Application s of Cryptographic Techniques (2013), Springer, pp. 626–645

    work page 2013

  17. [17]

    T., and Rothblum, G

    Goldw asser, S., Kalai, Y. T., and Rothblum, G. N. Delegating computation: interactive proofs for muggles. Journal of the ACM (JACM) 62 , 4 (2015), 27

    work page 2015

  18. [18]

    The knowledge complexity of interactive proof systems

    Goldw asser, S., Micali, S., and Rackoff, C. The knowledge complexity of interactive proof systems. SIAM Journal on computing 18 , 1 (1989), 186–208

    work page 1989

  19. [19]

    On the size of pairing-based non-interactive arguments

    Groth, J. On the size of pairing-based non-interactive arguments. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2016), Springer, pp. 305–326

    work page 2016

  20. [20]

    Founding cryptography on oblivious transfer

    Kilian, J. Founding cryptography on oblivious transfer. In Proceedings of the twentieth annual ACM symposium on Theory of computing (1988), ACM, pp. 20–31

    work page 1988

  21. [21]

    PolyShard: Coded sharding achieves linearly scaling efficiency and security simultaneously

    Li, S., Yu, M., A vestimehr, S., Kannan, S., and Visw anath, P. PolyShard: Coded sharding achieves linearly scaling efficiency and security simultaneously. arXiv preprint arXiv:1809.10361 (2018)

    work page arXiv 2018

  22. [22]

    A proof of security of YaoâĂŹs protocol for two-party comput ation

    Lindell, Y., and Pinkas, B. A proof of security of YaoâĂŹs protocol for two-party comput ation. Journal of Cryptology 22 , 2 (2009), 161–188

    work page 2009

  23. [23]

    Succinct non-interactive zero knowledge arguments from sp an programs and linear error- correcting codes

    Lipmaa, H. Succinct non-interactive zero knowledge arguments from sp an programs and linear error- correcting codes. In International Conference on the Theory and Application of Crypt ology and Information Security (2013), Springer, pp. 41–60

    work page 2013

  24. [24]

    Algebraic methods for interactive proof systems

    Lund, C., Fortnow, L., Karloff, H., and Nisan, N. Algebraic methods for interactive proof systems. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science (1990), IEEE, pp. 2–10

    work page 1990

  25. [25]

    Computationally Sound proofs

    Micali, S. Computationally Sound proofs. In Proceedings 35th Annual Symposium on Foundations of Computer Science (1994), IEEE, pp. 436–453

    work page 1994

  26. [26]

    Pinocchio: Nearly practical verifiable computation

    Parno, B., Howell, J., Gentry, C., and Raykov a, M. Pinocchio: Nearly practical verifiable computation. In 2013 IEEE Symposium on Security and Privacy (2013), IEEE, pp. 238–252

    work page 2013

  27. [27]

    Polishchuk, A., and Spielman, D. A. Nearly-linear size holographic proofs. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (1994), ACM, pp. 194–203

    work page 1994

  28. [28]

    N., and Rothblum, R

    Reingold, O., Rothblum, G. N., and Rothblum, R. D. Constant-round interactive proofs for delegating computation. In Proceedings of the forty-eighth annual ACM symposium on Theo ry of Computing (2016), ACM, pp. 49–62

    work page 2016

  29. [29]

    N., V adhan, S., and Wigderson, A

    Rothblum, G. N., V adhan, S., and Wigderson, A. Interactive proofs of proximity: delegating computation in sublinear time. In Proceedings of the forty-fifth annual ACM symposium on Theory o f computing (2013), ACM, pp. 793–802

    work page 2013

  30. [30]

    Sahraei, S., and A vestimehr, A. S. INTERPOL: Information theoretically verifiable polynomia l evaluation. arXiv preprint arXiv:1901.03379 (2019)

    work page internal anchor Pith review Pith/arXiv arXiv 1901

  31. [31]

    B., Chiesa, A., Garman, C., Green, M., Miers, I., Trome r, E., and Virza, M

    Sasson, E. B., Chiesa, A., Garman, C., Green, M., Miers, I., Trome r, E., and Virza, M. Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy (2014), IEEE, pp. 459–474

    work page 2014

  32. [32]

    IP= PSPACE (interactive proof= polynomial space)

    Shamir, A. IP= PSPACE (interactive proof= polynomial space). In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science (1990), IEEE, pp. 11–15

    work page 1990

  33. [33]

    Yao, A. C. Protocols for secure computations. In Foundations of Computer Science, 1982. SFCS’08. 23rd Annual Symposium on (1982), IEEE, pp. 160–164

    work page 1982

  34. [34]

    New publicly verifiable computation for batch matrix multiplication

    Zhang, X., Jiang, T., Li, K.-C., Castiglione, A., and Chen, X. New publicly verifiable computation for batch matrix multiplication. Information Sciences (2017)

    work page 2017