Separating the Power of Monotone Span Programs
over Different Fields

Amos Beimel  Enav Weinreb y

Abstract
Monotone span programs are a linearalgebraic model
of computation. They are equivalent to linear secret sharing 
schemes and have various applications in cryptography 
and complexity. A fundamental question is how the
choice of the field in which the algebraic operations are
performed effects the power of the span program. In this
paper we prove that the power of monotone span programs
over finite fields of different characteristics is incomparable; 
we show a superpolynomial separation between any
two fields with different characteristics, answering an open
problem of Pudl ak and Sgall 1998. Using this result we
prove a superpolynomial lower bound for monotone span
programs for a function in uniform NC 2 (and therefore
in P), answering an open problem of Babai, Wigderson,
and G al 1999. (All previous lower bounds for monotone
span programs were for functions not known to be in P.) Finally, 
we show that quasilinear schemes, a generalization
of linear secret sharing schemes introduced in Beimel and
Ishai 2001, are stronger than linear secret sharing schemes.
In particular, this proves, without any assumptions, that
nonlinear secret sharing schemes are more efficient than
linear secret sharing schemes.


References
[BDHM92] G. Buntrock, C. Damm, U. Hertrampf, and
C. Meinel. Structure and importance of the
logspacemod class. Math. Systems Theory,
25:223--237, 1992.
[Ber84] S. J. Berkowitz. On computing the determinant 
in small parallel time using a small
number of processors. Inform. Process. Lett.,
18:147--150, 1984.
[BF92] L. Babai and P. Frankl. Linear Algebra Methods 
in Combinatorics. University of Chicago,
1992. Preliminary Version 2.
[BGP97] A. Beimel, A. Gal, and M. Paterson. Lower
bounds for monotone span programs. Computational Complexity, 6(1):29--45, 1997.
[BGW99] L. Babai, A. Gal, and A. Wigderson. Super
polynomial lower bounds for monotone span
programs. Combinatorica, 19(3):301--319,
1999.
[BI99] E. BenSasson and R. Impagliazzo. Random
CNF's are Hard for the Polynomial Calculus.
In 40th FOCS, pages 415--421, 1999.
[BI01] A. Beimel and Y. Ishai. On the power of non
linear secretsharing. In Conf. on Computational Complexity, pages 188 -- 202, 2001.
[Bla79] G. R. Blakley. Safeguarding cryptographic
keys. In Proc. of the 1979 AFIPS National Computer Conference, volume 48 of
AFIPS Conference proceedings, pages 313--
317. AFIPS Press, 1979.
[BSS89] L. Blum, M. Shub, and S. Smale. On a theory
of computation and complexity over the real
numbers; NP completeness, recursive functions and 
universal machines. Bulletin of the
AMS (new series), 21(1):1--46, 1989.
[CDM00] R. Cramer, I. Damgard, and U. Maurer. General 
secure multiparty computation from any
linear secretsharing scheme. In B. Preneel, 
editor, Advances in Cryptology -- EURO
CRYPT 2000, volume 1807 of LNCS, pages
316--334. Springer, 2000.
[DKMW03] C. Damm, M. Krause, C. Meinel, and
S. Waack. On relations between counting
communication complexity classes. J. of Computer 
and System Sciences, 2003. To ap
pear. Prelimenary version: STACS '92.
[Gal98] A. Gal. A characterization of span program
size and improved lower bounds for monotone
span programs. In 30th STOC, pages 429--
437, 1998.
[GR01] C. Godsil and G. Royle. Algebraic Graph
Theory, volume 207 of Graduate Texts in
Mathematcs. Springer, 2001.
[ISN87] M. Ito, A. Saito, and T. Nishizeki. Secret sharing 
schemes realizing general access structure. 
In Proc. of the IEEE Global Telecommunication Conf., Globecom 87, pages 99--102,
1987. Journal version: Multiple Assignment
Scheme for Sharing Secret. J. of Cryptology,
6(1):1520, 1993.
[Juk01] S. Jukna. Extremal Combinatorics with Applications 
in Computer Science. Texts in Theoretical 
Comp. Sci. SpringerVerlag, 2001.
[KN97] E. Kushilevitz and N. Nisan. Communication
Complexity. Cambridge Univ. Press, 1997.
[KW93] M. Karchmer and A. Wigderson. On span programs. 
In Proc. of the 8th Structure in Com
plexity Theory, pages 102--111, 1993.
[MS82] K. Mehlhorn and E. M. Schmidt. Las vegas is
better than determinism in vlsi and distributed
computing. In Proc. of the 14th STOC, pages
330--337, 1982.
[Mul87] K. Mulmuley. A fast parallel algorithm to
compute the rank of a matrix over an arbitrary
field. Combinatorica, 7:101--104, 1987.
[NPR99] M. Naor, B. Pinkas, and O. Reingold. Distributed 
pseudorandom functions and KDCs.
LNCS, 1592:327--337, 1999.
[PS98] P. Pudlak and J. Sgall. Algebraic models
of computation and interpolation for algebraic 
proof systems. In Proof Complexity and
Feasible Arithmetic, volume 39 of DIMACS
Series in Discrete Mathematics and Theor.
Comp. Sci., pages 279--296. AMS, 1998.
[Raz90] A. A. Razborov. Applications of matrix methods 
to the theory of lower bounds in computational complexity. Combinatorica, 10(1):81--
93, 1990.
[Sha79] A. Shamir. How to share a secret. Communications 
of the ACM, 22(11):612--613, 1979.
[Sim92] G. J. Simmons. An introduction to shared secret 
and/or shared control and their application. 
In G. J. Simmons, editor, Contemporary 
Cryptology, The Science of Information
Integrity, pages 441--497. IEEE Press, 1992.
[Smo87] R. Smolensky. Algebraic methods in the theory 
of lower bounds for boolean circuit complexity. 
In Proceedings of the 19th STOC, pages 77--82, 1987.
[Sti92] D. R. Stinson. An explication of secret sharing
schemes. Designs, Codes and Cryptography,
2:357--390, 1992.

