REVIEW PAPER
NON-MALLEABLE RANDOMNESS EXTRACTORS
1
Uniwersytet Warszawski
Publication date: 2014-12-05
SBN 2014;6(2): 227-238
KEYWORDS
ABSTRACT
We give an unconditional 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. (FOCS’11). 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 paper
we present a modification of their construction that allows to remove that dependency
and address an issue we identified in the original development.
REFERENCES (27)
1.
William R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Annals of Mathematics, 139:703–722, 1994.
2.
Nesmith C. Ankeny, The least quadratic non residue, Annals of Mathematics, 55:65–72, 1952.
3.
Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert, Privacy amplification by public discussion SIAM J. Comput., 17(2):210–229, April 1988.
4.
Jean Bourgain, More on the sum-product phenomenon in prime fields and its applications International Journal of Number Theory, 1(1):1–32, 2005.
5.
Jean Bourgain and Sergei Konyagin, Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order, Comptes Rendus Mathematique, 337(2):75–80, 2003.
6.
Celine Chevalier, Pierre-Alain Fouque, David Pointche- ´ val, and Sbastien Zimmer, Optimal randomness extraction from a Diffie-Hellman element, In Antoine Joux, editor, Advances in Cryptology – Proceedings of EUROCRYPT 09, volume 5479 of Lecture Notes in Computer Science, pages 572–589, Cologne, Germany, 2009. Springer.
7.
Benny Chor and Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM J. Comput., 17(2):230–261, April 1988.
8.
Aviad Cohen and Avi Wigderson, Dispersers, deterministic amplification, and weak random sources (extended abstract), In FOCS, pages 14–19, IEEE Computer Society, 1989.
9.
Gil Cohen, Ran Raz, and Gil Segev, Non-malleable extractors with short seeds and applications to privacy amplification, In IEEE Conference on Computational Complexity, pages 298–308, IEEE, 2012.
10.
Yevgeniy Dodis, Xin Li, Trevor D. Wooley, and David Zuckerman, Privacy amplification and non-malleable extractors via character sums, In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 11, pages 668–677, Washington, DC, USA, 2011, IEEE Computer Society.
11.
Yevgeniy Dodis and Roberto Oliveira, On extracting private randomness over a public channel In Sanjeev Arora, Klaus Jansen, Jos D. P. Rolim, and Amit Sahai, editors, RANDOM-APPROX, volume 2764 of Lecture Notes in Computer Science, pages 252–263, Springer, 2003.
12.
Yevgeniy Dodis and Daniel Wichs, Non-malleable extractors and symmetric key cryptography from weak secrets, IACR Cryptology ePrint Archive, 2008:503, 2008.
13.
Yevgeniy Dodis and Daniel Wichs, Non-malleable extractors and symmetric key cryptography from weak secrets, In Proceedings of the 41st annual ACM symposium on Theory of computing, STOC 09, pages 601610, New York, NY, USA, 2009, ACM.
14.
Konrad Durnoga, Non-malleable Randomness Extractors, PhD thesis, University of Warsaw, 2014.
15.
Konrad Durnoga and Bartosz Zrałek, On randomness extractors and computing discrete logarithms in bulk, 2013, preprint.
16.
Pierre-Alain Fouque, David Pointcheval, Jacques Stern, and Sbastien Zimmer, Hardness of distinguishing the MSB or LSB of secret keys in Diffie-Hellman schemes, In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, volume 4052 of Lecture Notes in Computer Science, pages 240–251. Springer Berlin Heidelberg, 2006.
17.
Andrew Granville and Carl Pomerance, On the least prime in certain arithmetic progressions, Journal of the London Mathematical Society, 2(2):193–200, 1990.
18.
Thomas Holenstein, Pseudorandom generators from one-way functions: A simple construction for any hardness, In Shai Halevi and Tal Rabin, editors, In 3rd Theory of Cryptography Conference – (TCC 06), Lecture Notes in Computer Science. Springer-Verlag, 2006.
19.
Russell Impagliazzo, Leonid A. Levin, and Michael Luby, Pseudo-random generation from one-way functions, In Proceedings of the twenty-first annual ACM symposium on Theory of computing, STOC 89, pages 12–24, New York, NY, USA, 1989. ACM.
20.
Hendrik W. Lenstra. Primality testing with Gaussian periods, In Manindra Agrawal and Anil Seth, editors, FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 22nd Conference Kanpur, India, December 12–14, 2002, Proceedings, volume 2556 of Lecture Notes in Computer Science, page 1, Springer, 2002.
21.
Xin Li, Non-malleable extractors, two-source extractors and privacy amplification, In FOCS, volume 0, pages 688697, Los Alamitos, CA, USA, 2012, IEEE Computer Society.
22.
Ueli M. Maurer and Stefan Wolf, Privacy amplification secure against active adversaries In Burton S. Kaliski Jr., editor, CRYPTO, volume 1294 of Lecture Notes in Computer Science, pages 307–321, Springer, 1997.
23.
Noam Nisan and David Zuckerman, More deterministic simulation in logspace, In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, STOC 93, pages 235–244, New York, NY, USA, 1993, ACM.
24.
Stephen Pohlig and Martin Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Transactions on Information Theory, 24(1):106–110, 1978.
25.
Wolfgang M. Schmidt, Equations over finite fields: an elementary approach, Lecture Notes in Mathematics. Springer-Verlag, 1976.
26.
Triantafyllos Xylouris, Uber die Nullstellen der Dirichletschen ¨ L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression, PhD thesis, Mathematisch-Naturwissenschaftliche Fakult¨at der Universit¨at Bonn, 2011.
| ISSN: | 2082-2677 |
We process personal data collected when visiting the website. The function of obtaining information about users and their behavior is carried out by voluntarily entered information in forms and saving cookies in end devices. Data, including cookies, are used to provide services, improve the user experience and to analyze the traffic in accordance with the Privacy policy. Data are also collected and processed by Google Analytics tool (more).
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
