nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

How to Extract Useful Randomness from Unreliable Sources

verfasst von : Divesh Aggarwal, Maciej Obremski, João Ribeiro, Luisa Siniscalchi, Ivan Visconti

Erschienen in: Advances in Cryptology – EUROCRYPT 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

For more than 30 years, cryptographers have been looking for public sources of uniform randomness in order to use them as a set-up to run appealing cryptographic protocols without relying on trusted third parties. Unfortunately, nowadays it is fair to assess that assuming the existence of physical phenomena producing public uniform randomness is far from reality.

It is known that uniform randomness cannot be extracted from a single weak source. A well-studied way to overcome this is to consider several independent weak sources. However, this means we must trust the various sampling processes of weak randomness from physical processes.

Motivated by the above state of affairs, this work considers a set-up where players can access multiple potential sources of weak randomness, several of which may be jointly corrupted by a computationally unbounded adversary. We introduce SHELA (Somewhere Honest Entropic Look Ahead) sources to model this situation.

We show that there is no hope of extracting uniform randomness from a SHELA source. Instead, we focus on the task of Somewhere-Extraction (i.e., outputting several candidate strings, some of which are uniformly distributed – yet we do not know which). We give explicit constructions of Somewhere-Extractors for SHELA sources with good parameters.

Then, we present applications of the above somewhere-extractor where the public uniform randomness can be replaced by the output of such extraction from corruptible sources, greatly outperforming trivial solutions. The output of somewhere-extraction is also useful in other settings, such as a suitable source of random coins for many randomized algorithms.

In another front, we comprehensively study the problem of Somewhere-Extraction from a weak source, resulting in a series of bounds. Our bounds highlight the fact that, in most regimes of parameters (including those relevant for applications), SHELA sources significantly outperform weak sources of comparable parameters both when it comes to the process of Somewhere-Extraction, and in the task of amplification of success probability in randomized algorithms. Moreover, the low quality of somewhere-extraction from weak sources excludes its use in various efficient applications.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Extracting Randomness from Extractor-Dependent Sources

Nächstes Kapitel Low Error Efficient Computational Extractors in the CRS Model

Given blocks of different sizes, one can always fill out the shorter blocks with zeros, similarly given blocks of different min-entropy we can assume k to be the minimum of min-entropies of honest blocks.

In this example we are assuming that when using a blockchain as a SHELA source, the adversary of the sampling procedure from a SHELA source has no control over the choices of the honest blocks posted permanently in the blockchain (i.e., the adversary does not decide which honest block is selected and remains permanently in the blockchain out of multiple candidates).

We will show how to start from any public-coin 2-round WI proof system in the standard model which in turn means any non-interactive zero-knowledge proof system in the common random string model [34].

Notice that we are considering generic weak sources and it is unknown whether such distributions can all be efficiently simulatable. Consequently we cannot obtain a non-interactive zero knowledge proof.

We recall that obviously a SHELA source is also a high min-entropy source.

In reality, we are able to use strong seeded extractors (for which we know much better explicit constructions) in place of two-source extractors. This is due to the disproportion in the size of the sources. In fact, the size of one of the sources given to the extractor grows linearly with the total number of blocks.

The set of \((\tilde{n},k)\)-sources consists of all weak sources over \(\{0, 1\}^{\tilde{n}}\) with min-entropy at least k. We use \(\tilde{n}\) to avoid confusion with the block length of SHELA sources.

When biasing the next coordinates, we have to be careful not to ‘spoil’ biases of previous coordinates. This results in the \(\log \) factor in the bound.

By seed we mean i in \(F_i(X^\star )\).

For a SHELA source, a good blocks correspond to honest blocks, while they correspond to jointly uniform blocks in \(\mathsf {conv}\mathsf {SR}\)-sources.

With high min-entropy we set \(L=\ell -1\), while with low min-entropy we set \(L=O(\ell )\).

We set L precisely as specified in the previous footnote.

Aggarwal, D., Obremski, M., Ribeiro, J., Siniscalchi, L., Visconti, I.: How to extract useful randomness from unreliable sources. Cryptology ePrint Archive, Report 2019/1156 (2019). https://eprint.iacr.org/2019/1156

Barak, B., Kindler, G., Shaltiel, R., Sudakov, B., Wigderson, A.: Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors. J. ACM 57(4) (2010). https://doi.org/10.1145/1734213.1734214

Barak, B., Rao, A., Shaltiel, R., Wigderson, A.: 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction. Ann. Math. 176(3), 1483–1543 (2012)MathSciNetMATHCrossRef

Beigi, S., Bogdanov, A., Etesami, O., Guo, S.: Optimal deterministic extractors for generalized Santha-Vazirani sources. In: APPROX/RANDOM 2018. LIPIcs, vol. 116, pp. 30:1–30:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2018). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.30

Beigi, S., Etesami, O., Gohari, A.: Deterministic randomness extraction from generalized and distributed Santha-Vazirani sources. SIAM J. Comput. 46(1), 1–36 (2017). https://doi.org/10.1137/15M1027206MathSciNetMATHCrossRef

Bellare, M., Fuchsbauer, G., Scafuro, A.: NIZKs with an untrusted CRS: security in the face of parameter subversion. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 777–804. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_26MATHCrossRef

Ben-Aroya, A., Chattopadhyay, E., Doron, D., Li, X., Ta-Shma, A.: A new approach for constructing low-error, two-source extractors. In: CCC 2018, pp. 3:1–3:19. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Germany (2018)

Bennett, C.H., Brassard, G., Robert, J.-M.: How to reduce your enemy’s information (extended abstract). In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 468–476. Springer, Heidelberg (1986). https://doi.org/10.1007/3-540-39799-X_37CrossRef

Bentov, I., Gabizon, A., Zuckerman, D.: Bitcoin beacon. arXiv e-prints arXiv:1605.04559, May 2016

10.

Bitansky, N., Paneth, O.: Point obfuscation and 3-round zero-knowledge. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 190–208. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_11CrossRef

11.

Blum, M.: Independent unbiased coin flips from a correlated biased source—a finite state Markov chain. Combinatorica 6(2), 97–108 (1986). https://doi.org/10.1007/BF02579167MathSciNetMATHCrossRef

12.

Bourgain, J.: More on the sum-product phenomenon in prime fields and its applications. Int. J. Number Theory 01(01), 1–32 (2005)MathSciNetMATHCrossRef

13.

Bourgain, J.: On the construction of affine extractors. GAFA Geom. Funct. Anal. 17(1), 33–57 (2007)MathSciNetMATHCrossRef

14.

Bourgain, J., Dvir, Z., Leeman, E.: Affine extractors over large fields with exponential error. Comput. Complex. 25(4), 921–931 (2016). https://doi.org/10.1007/s00037-015-0108-5MathSciNetMATHCrossRef

15.

Canetti, R., Pass, R., Shelat, A.: Cryptography from sunspots: how to use an imperfect reference string. In: FOCS 2007, pp. 249–259, October 2007. https://doi.org/10.1109/FOCS.2007.70

16.

Chattopadhyay, E., Goodman, J., Goyal, V., Li, X.: Extractors for adversarial sources via extremal hypergraphs. Cryptology ePrint Archive, Report 2019/1450 (2019, to appear in STOC 2020). https://eprint.iacr.org/2019/1450

17.

Chattopadhyay, E., Goyal, V., Li, X.: Non-malleable extractors and codes, with their many tampered extensions. In: STOC 2016, pp. 285–298. ACM, New York (2016). https://doi.org/10.1145/2897518.2897547

18.

Chattopadhyay, E., Zuckerman, D.: Explicit two-source extractors and resilient functions. Ann. Math. 189(3), 653–705 (2019)MathSciNetMATHCrossRef

19.

Chor, B., Goldreich, O., Hasted, J., Freidmann, J., Rudich, S., Smolensky, R.: The bit extraction problem or t-resilient functions. In: FOCS 1985, pp. 396–407, October 1985. https://doi.org/10.1109/SFCS.1985.55

20.

Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput. 17(2), 230–261 (1988). https://doi.org/10.1137/0217015MathSciNetMATHCrossRef

21.

Clark, J., Hengartner, U.: On the use of financial data as a random beacon. In: EVT/WOTE 2010, pp. 1–8. USENIX Association, Berkeley (2010)

22.

Cohen, G., Schulman, L.J.: Extractors for near logarithmic min-entropy. In: FOCS 2016, pp. 178–187, October 2016. https://doi.org/10.1109/FOCS.2016.27

23.

Cohen, G.: Local correlation breakers and applications to three-source extractors and mergers. SIAM J. Comput. 45(4), 1297–1338 (2016). https://doi.org/10.1137/15M1029837MathSciNetMATHCrossRef

24.

Cohen, G., Shinkar, I.: Zero-fixing extractors for sub-logarithmic entropy. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 343–354. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47672-7_28CrossRef

25.

De, A., Watson, T.: Extractors and lower bounds for locally samplable sources. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) APPROX/RANDOM 2011. LNCS, vol. 6845, pp. 483–494. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22935-0_41CrossRef

26.

DeVos, M., Gabizon, A.: Simple affine extractors using dimension expansion. In: CCC 2010, pp. 50–57. IEEE Computer Society, USA (2010). https://doi.org/10.1109/CCC.2010.14

27.

Dodis, Y.: New imperfect random source with applications to coin-flipping. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 297–309. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-48224-5_25CrossRef

28.

Dodis, Y., Vaikuntanathan, V., Wichs, D.: Extracting randomness from extractor-dependent sources. Cryptology ePrint Archive, Report 2019/1339 (2019). https://eprint.iacr.org/2019/1339

29.

Dvir, Z., Kopparty, S., Saraf, S., Sudan, M.: Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. SIAM J. Comput. 42(6), 2305–2328 (2013)MathSciNetMATHCrossRef

30.

Dvir, Z., Gabizon, A., Wigderson, A.: Extractors and rank extractors for polynomial sources. Comput. Complex. 18(1), 1–58 (2009). https://doi.org/10.1007/s00037-009-0258-4MathSciNetMATHCrossRef

31.

Dvir, Z., Raz, R.: Analyzing linear mergers. Random Struct. Algorithms 32(3), 334–345 (2008)MathSciNetMATHCrossRef

32.

Dvir, Z., Shpilka, A.: An improved analysis of linear mergers. Comput. Complex. 16(1), 34–59 (2007). https://doi.org/10.1007/s00037-007-0223-zMathSciNetMATHCrossRef

33.

Dvir, Z., Wigderson, A.: Kakeya sets, new mergers, and old extractors. SIAM J. Comput. 40(3), 778–792 (2011). https://doi.org/10.1137/090748731MathSciNetMATHCrossRef

34.

Dwork, C., Naor, M.: Zaps and their applications. In: FOCS 2000, pp. 283–293, November 2000. https://doi.org/10.1109/SFCS.2000.892117

35.

Elias, P.: The efficient construction of an unbiased random sequence. Ann. Math. Stat. 43(3), 865–870 (1972)MATHCrossRef

36.

Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1–28 (1999)MathSciNetMATHCrossRef

37.

Fuchsbauer, G., Orrù, M.: Non-interactive zaps of knowledge. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 44–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93387-0_3CrossRef

38.

Gabizon, A., Raz, R.: Deterministic extractors for affine sources over large fields. In: FOCS 2005, pp. 407–416, October 2005. https://doi.org/10.1109/SFCS.2005.31

39.

Gabizon, A., Raz, R., Shaltiel, R.: Deterministic extractors for bit-fixing sources by obtaining an independent seed. SIAM J. Comput. 36(4), 1072–1094 (2006)MathSciNetMATHCrossRef

40.

Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 281–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_10CrossRef

41.

Goyal, R., Goyal, V.: Overcoming cryptographic impossibility results using blockchains. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 529–561. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_18CrossRef

42.

Groth, J., Ostrovsky, R., Sahai, A.: Non-interactive zaps and new techniques for NIZK. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 97–111. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_6CrossRef

43.

Guruswami, V., Umans, C., Vadhan, S.: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM 56(4), 20:1–20:34 (2009)MathSciNetMATHCrossRef

44.

Kamp, J., Rao, A., Vadhan, S., Zuckerman, D.: Deterministic extractors for small-space sources. J. Comput. Syst. Sci. 77(1), 191–220 (2011)MathSciNetMATHCrossRef

45.

Kamp, J., Zuckerman, D.: Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. SIAM J. Comput. 36(5), 1231–1247 (2007)MathSciNetMATHCrossRef

46.

Lewko, M.: An explicit two-source extractor with min-entropy rate near \(4/9\). Mathematika 65(4), 950–957 (2019)MathSciNetMATHCrossRef

47.

Li, F., Zuckerman, D.: Improved extractors for recognizable and algebraic sources. Electronic Colloquium on Computational Complexity (ECCC) 25, 110 (2018)

48.

Li, X.: Improved constructions of three source extractors. In: CCC 2011, pp. 126–136, June 2011. https://doi.org/10.1109/CCC.2011.26

49.

Li, X.: A new approach to affine extractors and dispersers. In: CCC 2011, pp. 137–147, June 2011. https://doi.org/10.1109/CCC.2011.27

50.

Li, X.: Extractors for a constant number of independent sources with polylogarithmic min-entropy. In: FOCS 2013, pp. 100–109, October 2013. https://doi.org/10.1109/FOCS.2013.19

51.

Li, X.: Improved two-source extractors, and affine extractors for polylogarithmic entropy. In: FOCS 2016, pp. 168–177, October 2016. https://doi.org/10.1109/FOCS.2016.26

52.

Li, X.: New independent source extractors with exponential improvement. In: STOC 2013, pp. 783–792. ACM, New York, June 2013

53.

Li, X.: Three-source extractors for polylogarithmic min-entropy. In: FOCS 2015, pp. 863–882, October 2015. https://doi.org/10.1109/FOCS.2015.58

54.

Lichtenstein, D., Linial, N., Saks, M.: Some extremal problems arising from discrete control processes. Combinatorica 9(3), 269–287 (1989). https://doi.org/10.1007/BF02125896MathSciNetMATHCrossRef

55.

Lu, C.J., Reingold, O., Vadhan, S., Wigderson, A.: Extractors: optimal up to constant factors. In: STOC 2003, pp. 602–611. ACM, New York (2003)

56.

Naor, M.: Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151–158 (1991). https://doi.org/10.1007/BF00196774MATHCrossRef

57.

von Neumann, J.: Various techniques used in connection with random digits. In: Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, vol. 12, chap. 13, pp. 36–38. US Government Printing Office, Washington, DC (1951)

58.

Nisan, N., Zuckerman, D.: Randomness is linear in space. J. Comput. Syst. Sci. 52(1), 43–52 (1996)MathSciNetMATHCrossRef

59.

Pass, R., Seeman, L., Shelat, A.: Analysis of the blockchain protocol in asynchronous networks. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 643–673. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_22MATHCrossRef

60.

Pudlak, P., Rodl, V.: Extractors for small zero-fixing sources. arXiv e-prints arXiv:1904.07949, April 2019

61.

Radhakrishnan, J., Ta-Shma, A.: Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discrete Math. 13(1), 2–24 (2000)MathSciNetMATHCrossRef

62.

Rao, A.: Extractors for low-weight affine sources. In: CCC 2009, pp. 95–101, July 2009. https://doi.org/10.1109/CCC.2009.36

63.

Rao, A.: Extractors for a constant number of polynomially small min-entropy independent sources. SIAM J. Comput. 39(1), 168–194 (2009)MathSciNetMATHCrossRef

64.

Raz, R.: Extractors with weak random seeds. In: STOC 2005, pp. 11–20. ACM, New York (2005). https://doi.org/10.1145/1060590.1060593

65.

Santha, M., Vazirani, U.V.: Generating quasi-random sequences from slightly-random sources. In: FOCS 1984, pp. 434–440, October 1984. https://doi.org/10.1109/SFCS.1984.715945

66.

Scafuro, A., Siniscalchi, L., Visconti, I.: Publicly verifiable proofs from blockchains. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11442, pp. 374–401. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17253-4_13CrossRef

67.

Ta-Shma, A.: On extracting randomness from weak random sources (extended abstract). In: STOC 1996, pp. 276–285. ACM, New York (1996)

68.

Trevisan, L., Vadhan, S.: Extracting randomness from samplable distributions. In: FOCS 2000, pp. 32–42. IEEE Computer Society, Washington, DC (2000)

69.

Vazirani, U.V.: Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources. In: STOC 1985, pp. 366–378. ACM, New York (1985)

70.

Viola, E.: Extractors for turing-machine sources. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX/RANDOM 2012. LNCS, vol. 7408, pp. 663–671. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32512-0_56CrossRef

71.

Viola, E.: Extractors for circuit sources. SIAM J. Comput. 43(2), 655–672 (2014)MathSciNetMATHCrossRef

72.

Yehudayoff, A.: Affine extractors over prime fields. Combinatorica 31(2), 245 (2011). https://doi.org/10.1007/s00493-011-2604-9MathSciNetMATHCrossRef

73.

Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: STOC 2006. pp. 681–690. ACM, New York, NY, USA (2006)

Titel: How to Extract Useful Randomness from Unreliable Sources
verfasst von: Divesh Aggarwal
Maciej Obremski
João Ribeiro
Luisa Siniscalchi
Ivan Visconti
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2020
Print ISBN: 978-3-030-45720-4

Electronic ISBN: 978-3-030-45721-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-45721-1_13

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"