Extractors for varieties. (English) Zbl 1280.68293
Summary: We study the task of randomness extraction from sources that are distributed uniformly on an unknown algebraic variety. In other words, we are interested in constructing a function (an extractor) whose output is close to uniform even if the input is drawn uniformly from the set of solutions of an unknown system of low degree polynomials. This problem generalizes the problem of extraction from affine sources which has drawn a considerable amount of interest lately.
We present two constructions of explicit extractors for varieties. The first works for varieties of any size (including one-dimensional varieties or curves) and requires field size that is exponential in the overall dimension of the space. Our second extractor allows the field size to be polynomial in the degree of the equations defining the variety, but works only for varieties whose size is at least the square root of the total size of the space.
We present two constructions of explicit extractors for varieties. The first works for varieties of any size (including one-dimensional varieties or curves) and requires field size that is exponential in the overall dimension of the space. Our second extractor allows the field size to be polynomial in the degree of the equations defining the variety, but works only for varieties whose size is at least the square root of the total size of the space.
MSC:
| 68W20 | Randomized algorithms |
| 68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |
References:
| [1] | B. Barak, A. Rao, R. Shaltiel & A. Wigderson (2006). 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, 671–680. ACM Press, New York, NY, USA. ISBN 1-59593-134-1. · Zbl 1301.68191 |
| [2] | Bombieri E. (1966) On Exponential Sums in Finite Fields. American Journal of Mathematics 88: 71–105 · Zbl 0171.41504 · doi:10.2307/2373048 |
| [3] | Bourgain J. (2007) On the construction of affine extractors. Geometric And Functional Analysis 17(1): 33–57 · Zbl 1115.68108 · doi:10.1007/s00039-007-0593-z |
| [4] | O. Chevassut, P. Fouque, P. Gaudry & D. Pointcheval (2006). The Twist-AUgmented Technique for Key Exchange. In Public Key Cryptography, Moti Yung, Yevgeniy Dodis, Aggelos Kiayias & Tal Malkin, editors, volume 3958 of Lecture Notes in Computer Science, 410–426. Springer. ISBN 3-540-33851-9. http://dblp.uni-trier.de/db/conf/pkc/pkc2006.html#ChevassutFGP06 . · Zbl 1151.94495 |
| [5] | B. Chor, O. Goldreich, J. Håstad, J. Friedman, S. Rudich & R. Smolensky (1985). The Bit Extraction Problem of t-Resilient Functions (Preliminary Version). In Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 396–407. |
| [6] | D. Cox, J. Little & D. O’Shea (2007). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3/e (Undergraduate Texts in Mathematics). Springer-Verlag New York, Inc., Secaucus, NJ, USA. ISBN 0387356509. · Zbl 1118.13001 |
| [7] | V. Danilov (1994). Algebraic varieties and schemes. In I. Shafarevich (Ed.), Algebraic Geometry I, Encyclopedia of Mathematical Sciences, Vol. 23, 167–297. Springer, Berlin. |
| [8] | Deligne P. (1974) La conjecture de Weil. I , Inst. Hautes Etudes Sci. Publ. Math. 43: 273–307 · Zbl 0287.14001 · doi:10.1007/BF02684373 |
| [9] | Z. Dvir, A. Gabizon & A. Wigderson (2009). Extractors And Rank Extractors For Polynomial Sources. Comput. Complex. 18, 1–58. ISSN 1016-3328. http://portal.acm.org/citation.cfm?id=1536240.1536241 . · Zbl 1210.68136 |
| [10] | A. Gabizon & R. Raz (2008). Deterministic extractors for affine sources over large fields. Combinatorica 28, 415–440. ISSN 0209-9683. http://portal.acm.org/citation.cfm?id=1459886.1459887 . · Zbl 1174.05117 |
| [11] | A. Gabizon, R. Raz & R. Shaltiel (2006). Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. SIAM J. Comput. 36, 1072–1094. ISSN 0097-5397. http://portal.acm.org/citation.cfm?id=1328008.1328010 . · Zbl 1118.68096 |
| [12] | O. Goldreich (1995). Three XOR-Lemmas - An Exposition. Electronic Colloquium on Computational Complexity (ECCC) 2(056). http://citeseer.ist.psu.edu/goldreich95three.html . · Zbl 1343.68112 |
| [13] | N. Gurel (2005). Extracting bits from coordinates of a point of an elliptic curve. Technical report. Cryptology ePrint Archive, Report 2005/324, http://eprint.iacr.org/ . |
| [14] | J. Harris (1992). Algebraic Geometry - A First Course. Springer. · Zbl 0779.14001 |
| [15] | R. Hartshorne (1977). Algebraic Geometry. Number 52 in Graduate Texts in Mathematics. Springer. |
| [16] | J. Kamp & D. Zuckerman (2006). Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. SIAM J. Comput. 36, 1231–1247. ISSN 0097-5397. http://dx.doi.org/10.1137/S0097539705446846 . · Zbl 1124.68036 |
| [17] | J. Kamp, A. Rao, S. Vadhan & D. Zuckerman (2011). Deterministic extractors for small-space sources. J. Comput. Syst. Sci. 77, 191–220. ISSN 0022-0000. http://dx.doi.org/10.1016/j.jcss.2010.06.014 . · Zbl 1232.68094 |
| [18] | MorenoO. Kumar P. (1993) Minimum distance bounds for cyclic codes and Deligne’s theorem. IEEE Transactions on Information Theory 39(5): 1524–1534 · Zbl 0798.94011 · doi:10.1109/18.259637 |
| [19] | A. Rao (2007). An Exposition of Bourgain’s 2-Source Extractor. Technical Report TR07-034, ECCC. |
| [20] | W. M. Schmidt (1976). Equations over Finite Fields: An Elementary Approach, volume 536. Springer-Verlag, Lecture Notes in Mathematics. · Zbl 0329.12001 |
| [21] | J. T. Schwartz (1980). Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM 27(4), 701–717. ISSN 0004-5411. · Zbl 0452.68050 |
| [22] | I. R. Shafarevich (1994). Basic algebraic geometry. Springer-Verlag New York, Inc., New York, NY, USA. ISBN 0-387-54812-2. · Zbl 0797.14001 |
| [23] | R. Shaltiel (2008). How to get more mileage from randomness extractors. Random Struct. Algorithms 33, 157–186. ISSN 1042-9832. http://portal.acm.org/citation.cfm?id=1400123.1400124 . · Zbl 1181.68170 |
| [24] | M. Sombra (1997). Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz. Journal of Pure and Applied Algebra 117-118, 565–599. ISSN 0022-4049. http://www.sciencedirect.com/science/article/B6V0K-3SP2C65-1P/2/6d4a177ce4576c10ad7dd8db8c0213d8 . · Zbl 0928.14002 |
| [25] | L. Trevisan & S. Vadhan (2000). Extracting randomness from samplable distributions. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 32. IEEE Computer Society, Washington, DC, USA. ISBN 0-7695-0850-2. |
| [26] | Wooley T. (1996) A Note on Simultaneous Congruences. J. Number Theory 58: 288–297 · Zbl 0852.11017 · doi:10.1006/jnth.1996.0078 |
| [27] | R. Zippel (1979). Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, 216–226. Springer-Verlag. ISBN 3-540-09519-5. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
