Najnowszy Numer
Archiwum
O Nas
Międzynarodowa Rada Naukowa
Rada Redakcyjna
Kontakt
Recenzenci
Standardy etyczne
Standardy etyczne czasopisma (COPE)
Polityka Open Access
Procedura zabezpieczająca oryginalność publikacji
Dla Autorów
Wymagania Edytorskie
Wytyczne Merytoryczne
Proces Recenzji
Dla Recenzentów
ARTYKUŁ PRZEGLĄDOWY
NIEKOWALNE EKSTRAKTORY LOSOWOŚCI
1
Uniwersytet Warszawski
Data publikacji: 05-12-2014
SBN 2014;6(2): 227-238
SŁOWA KLUCZOWE
STRESZCZENIE
Ekstraktory losowości należą do jednego z głównych nurtów badań współ-
czesnej kryptografii teoretycznej. Zadaniem tych deterministycznych funkcji jest przekształcenie źródeł słabej losowości w takie, których rozkład jest bliski rozkładowi jednostajnemu. W pracy przedstawiona jest teorioliczbowa konstrukcja ekstraktora o pewnych
szczególnych własnościach – ekstraktora niekowalnego. Wynik ten stanowi udoskonalenie warunkowego rezultatu Y. Dodisa i in. opublikowanego na prestiżowej konferencji
FOCS’11.
REFERENCJE (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.
Udostępnij
| ISSN: | 2082-2677 |
Przetwarzamy dane osobowe zbierane podczas odwiedzania serwisu. Realizacja funkcji pozyskiwania informacji o użytkownikach i ich zachowaniu odbywa się poprzez dobrowolnie wprowadzone w formularzach informacje oraz zapisywanie w urządzeniach końcowych plików cookies (tzw. ciasteczka). Dane, w tym pliki cookies, wykorzystywane są w celu realizacji usług, zapewnienia wygodnego korzystania ze strony oraz w celu monitorowania ruchu zgodnie z Polityką prywatności. Dane są także zbierane i przetwarzane przez narzędzie Google Analytics (więcej).
Możesz zmienić ustawienia cookies w swojej przeglądarce. Ograniczenie stosowania plików cookies w konfiguracji przeglądarki może wpłynąć na niektóre funkcjonalności dostępne na stronie.
Możesz zmienić ustawienia cookies w swojej przeglądarce. Ograniczenie stosowania plików cookies w konfiguracji przeglądarki może wpłynąć na niektóre funkcjonalności dostępne na stronie.
