On Computing Discrete Logarithms in Bulk and Randomness Extractors

• Autorzy: Durnoga K. , Źrałek B.

Identyfikatory

DOI

10.3233/FI-2015-1279

• Języki publikacji: EN

Abstrakty

EN

We prove several results of independent interest related to the problem of computing deterministically discrete logarithms in a finite field. The motivation was to give a number-theoretic construction of a non-malleable extractor improving the solution from the recent paper Privacy Amplification and Non-Malleable Extractors via Character Sums by Dodis et al. There, the authors provide the first explicit example of a non-malleable extractor – a cryptographic primitive that significantly strengthens the notion of a classical randomness extractor. In order to make the extractor robust, so that it runs in polynomial time and outputs a linear number of bits, they rely on a certain conjecture on the least prime in a residue class. In this work we present a modification of their construction that allows to remove that dependency and address an issue we identified in the original development. Namely, it required an additional assumption about feasibility of finding a primitive element of a finite field. As an auxiliary result, we show an efficiently computable bijection between any order M subgroup of the multiplicative group of a finite field and a set of integers modulo M with the provision that M is a smooth number. Also, we provide a version of the baby-step giantstep method for solving multiple instances of the discrete logarithm problem in the multiplicative group of a prime field. It performs better than the generic algorithm when run on a machine without constant-time access to each memory cell, e.g., on a classical Turing machine.

Słowa kluczowe

EN

logarithm; mathematical proofs; finite fields; number theory; cryptography; polynomial time algorithm; integers

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 141, nr 4
• Strony: 345--366
• Opis fizyczny: Bibliogr. 35 poz., rys.

Twórcy

autor

Durnoga K.

• Institute of Informatics, University of Warsaw Banacha 2, 02-097 Warszawa, Poland

autor

Źrałek B.

• Institute of Informatics, University of Warsaw Banacha 2, 02-097 Warszawa, Poland

Bibliografia

• [1] Alford, W. R., Granville, A., Pomerance, C.: There are infinitely many Carmichael numbers, Annals of Mathematics, 139, 1994, 703–722, ISSN 0003–486X.
• [2] Ankeny, N. C.: The least quadratic non residue, Annals of Mathematics, 55, 1952, 65–72, ISSN 0003–486X.
• [3] Bach, E.: Comments on search procedures for primitive roots, Mathematics of Computation, 66(220), 1997, 1719–1727.
• [4] Bourgain, J.: More on the sum-product phenomenon in prime fields and its applications, International Journal of Number Theory, 1(1), 2005, 1–32.
• [5] Chevalier, C., Fouque, P.-A., Pointcheval, D., Zimmer, S.: Optimal randomness extraction from a Diffie-Hellman element, Advances in Cryptology - Proceedings of EUROCRYPT ’09 (A. Joux, Ed.), 5479, Springer, Cologne, Germany, 2009.
• [6] Chevassut, O., Fouque, P.-A., Gaudry, P., Pointcheval, D.: The twist-augmented technique for key exchange, PKC ’06 (M. Yung, Y. Dodis, A. Kiayias, T. Malkin, Eds.), 3958, Springer-Verlag, 2006.
• [7] Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM J. Comput., 17(2), April 1988, 230–261, ISSN 0097-5397.
• [8] Cohen, A., Wigderson, A.: Dispersers, deterministic amplification, and weak random sources (extended abstract), FOCS, IEEE Computer Society, 1989.
• [9] Cohen, G., Raz, R., Segev, G.: Non-malleable extractors with short seeds and applications to privacy amplification, IEEE Conference on Computational Complexity, IEEE, 2012, ISBN 978-1-4673-1663-7.
• [10] Diem, C.: On the complexity of some computational problems in the Turing model, 2012, Preprint.
• [11] Dodis, Y., Li, X., Wooley, T. D., Zuckerman, D.: Privacy amplification and non-malleable extractors via character sums, Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS ’11, IEEE Computer Society, Washington, DC, USA, 2011, ISBN 978-0-7695-4571-4.
• [12] Dodis, Y., Oliveira, R.: On extracting private randomness over a public channel, RANDOM-APPROX (S. Arora, K. Jansen, J. D. P. Rolim, A. Sahai, Eds.), 2764, Springer, 2003, ISBN 3-540-40770-7.
• [13] Dodis, Y., Wichs, D.: Non-malleable extractors and symmetric key cryptography from weak secrets, Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09, ACM, New York, NY, USA, 2009, ISBN 978-1-60558-506-2.
• [14] Durnoga, K.: Non-malleable randomness extractors, Ph.D. Thesis, University of Warsaw, 2013.
• [15] Fiat, A., Woeginger, G. J., Eds.: Online Algorithms, The State of the Art (the book grow out of a Dagstuhl Seminar, June 1996), vol. 1442 of Lecture Notes in Computer Science, Springer, 1998, ISBN 3-540-64917-4.
• [16] Gao, S.: Elements of provable high orders in finite fields, Proceedings of the American Mathematical Society, 127, 1997, 1615–1623.
• [17] Granville, A., Pomerance, C.: On the least prime in certain arithmetic progressions, Journal of the London Mathematical Society, 2(2), 1990, 193–200.
• [18] Impagliazzo, R., Levin, L. A., Luby, M.: Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on theory of computing, STOC ’89, ACM, New York, NY, USA, 1989, ISBN 0-89791-307-8.
• [19] Konyagin, S., Pomerance, C.: On primes recognizable in deterministic polynomial time, in: The Mathematics of Paul Erdös, vol. 13 of Algorithms Combin., Springer, Berlin, 1996, 176–198.
• [20] Lenstra, H. W.: Primality Testing with Gaussian Periods, FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 22nd Conference Kanpur, India, December 12-14, 2002, Proceedings (M. Agrawal, A. Seth, Eds.), 2556, Springer, 2002, ISBN 3-540-00225-1.
• [21] Li, X.: Non-malleable extractors, two-source extractors and privacy amplification, FOCS, 0, IEEE Computer Society, Los Alamitos, CA, USA, 2012, ISSN 0272-5428.
• [22] Li, X.: Non-malleable condensers for arbitrary min-entropy, and almost optimal protocols for privacy amplification, in: Theory of Cryptography, Springer, 2015, 502–531.
• [23] Nisan, N., Zuckerman, D.: More deterministic simulation in logspace, Proceedings of the twenty-fifth annual ACM symposium on theory of computing, STOC ’93, ACM, New York, NY, USA, 1993, ISBN 0-89791-591-7.
• [24] Petersen, H.: Sorting and element distinctness on one-way Turing machines, LATA (C. Martín-Vide, F. Otto, H. Fernau, Eds.), 5196, Springer, 2008, ISBN 978-3-540-88281-7.
• [25] Pila, J.: Frobenius maps of abelian varieties and finding roots of unity in finite fields, Mathematics of Computation, 55(192), 1990, 745–763, ISSN 00255718.
• [26] Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Transactions on Information Theory, 24(1), 1978, 106–110, ISSN 0018-9448.
• [27] Pomerance, C.: The expected number of random elements to generate a finite abelian group, Periodica Mathematica Hungarica, 43(1-2), 2002, 191–198.
• [28] Pomerance, C., Shparlinski, I.: Smooth orders and cryptographic applications., ANTS (C. Fieker, D. R. Kohel, Eds.), 2369, Springer, 2002, ISBN 3-540-43863-7.
• [29] Shaltiel, R.: Recent Developments in Explicit Constructions of Extractors, Bulletin of the EATCS, 77, 2002, 67–95.
• [30] Shanks, D.: Class number, a theory of factorization, and genera, in: 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969), Amer. Math. Soc., Providence, R.I., 1971, 415–440.
• [31] Shoup, V.: Searching for primitive roots in finite fields, Proceedings of the twenty-second annual ACM symposium on theory of computing, STOC ’90, ACM, New York, NY, USA, 1990, ISBN 0-89791-361-2.
• [32] Trevisan, L.: Construction of extractors using pseudo-random generators (extended abstract), STOC, 1999.
• [33] Wedeniwski, S.: Primality Tests on Commutator Curves, Ph.D. Thesis, Eberhard-Karls-Universität Tübingen, 2001.
• [34] Xylouris, T.: Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression, Ph.D. Thesis, Mathematisch-Naturwissenschaftliche Fakultät der Universität Bonn, 2011.
• [35] Zuckerman, D.: General weak random sources, FOCS, 1990.