Next: Honest Verifier vs Dishonest
Up: The First 1.5 Years
Previous: Incremental Cryptography: the Case
The lemma asserts conditions under which one may test
by a constant number of queries whether a function applied to
a sequence of arguments is consistent with any function that is
applied to a single argument.
Comments:
Authored by O. Goldreich and S. Safra. Appeared in
- Random97, Springer LNCS, Vol. 1269, pp. 67-84.
- SIAM Jour. on Comp., Volume 29, Number 4, pages 1132-1154, 1999.
Oded Goldreich
2003-07-30