nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Proof of Space from Stacked Expanders

verfasst von : Ling Ren, Srinivas Devadas

Erschienen in: Theory of Cryptography

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Recently, proof of space (PoS) has been suggested as a more egalitarian alternative to the traditional hash-based proof of work. In PoS, a prover proves to a verifier that it has dedicated some specified amount of space. A closely related notion is memory-hard functions (MHF), functions that require a lot of memory/space to compute. While making promising progress, existing PoS and MHF have several problems. First, there are large gaps between the desired space-hardness and what can be proven. Second, it has been pointed out that PoS and MHF should require a lot of space not just at some point, but throughout the entire computation/protocol; few proposals considered this issue. Third, the two existing PoS constructions are both based on a class of graphs called superconcentrators, which are either hard to construct or add a logarithmic factor overhead to efficiency. In this paper, we construct PoS from stacked expander graphs. Our constructions are simpler, more efficient and have tighter provable space-hardness than prior works. Our results also apply to a recent MHF called Balloon hash. We show Balloon hash has tighter space-hardness than previously believed and consistent space-hardness throughout its computation.

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 Simultaneous Secrecy and Reliability Amplification for a General Channel Model

Nächstes Kapitel Perfectly Secure Message Transmission in Two Rounds

Zoom Hash Scrypt ASIC. http://zoomhash.com/collections/asics. Accessed: 20 May 2016

Abadi, M., Burrows, M., Manasse, M., Wobber, T.: Moderately hard, memory-bound functions. ACM Trans. Internet Technol. 5(2), 299–327 (2005)CrossRef

Almeida, L.C., Andrade, E.R., Barreto, P.S.L.M., Marcos, A., Simplicio Jr., M.A.: Lyra: password-based key derivation with tunable memory and processing costs. J. Crypt. Eng. 4(2), 75–89 (2014)CrossRef

Alon, N., Capalbo, M.: Smaller explicit superconcentrators. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 340–346. Society for Industrial and Applied Mathematics (2003)

Alwen, J., Blocki, J.: Efficiently computing data-independent memory-hard functions. Cryptology ePrint Archive, Report 2016/115 (2016)

Alwen, J., Blocki, J.: Towards practical attacks on argon2i and balloon hashing. Cryptology ePrint Archive, Report 2016/759 (2016)

Alwen, J., Chen, B., Kamath, C., Kolmogorov, V., Pietrzak, K., Tessaro, S.: On the complexity of scrypt and proofs of space in the parallel random oracle model. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 358–387. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49896-5_13 CrossRef

Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 595–603. ACM (2015)

Andersen, D.G.: Exploiting time-memory tradeoffs in cuckoo cycle (2014). https://www.cs.cmu.edu/~dga/crypto/cuckoo/analysis.pdf. Accessed Aug 2016

10.

Asanovic, K., Bodik, R., Catanzaro, B.C., Gebis, J.J., Husbands, P., Keutzer, K., Patterson, D.A., Plishker, W.L., Shalf, J., Williams, S.W.: The landscape of parallel computing research: a view from berkeley. Technical Report UCB/EECS-2006-183, EECS Department, University of California, Berkeley (2006)

11.

Ateniese, G., Bonacina, I., Faonio, A., Galesi, N.: Proofs of space: when space is of the essence. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 538–557. Springer, Heidelberg (2014)

12.

Ateniese, G., Burns, R., Curtmola, R., Herring, J., Kissner, L., Peterson, Z., Song, D.: Provable data possession at untrusted stores. In: Proceedings of the 14th ACM Conference on Computer and Communications Security, pp. 598–609. ACM (2007)

13.

Back, A.: Hashcash-a denial of service counter-measure (2002)

14.

Leonid Alexandrovich Bassalygo: Asymptotically optimal switching circuits. Problemy Peredachi Informatsii 17(3), 81–88 (1981)MathSciNet

15.

Biryukov, A., Dinu, D., Khovratovich, D.: Fast and tradeoff-resilient memory-hard functions for cryptocurrencies and password hashing (2015)

16.

Biryukov, A., Khovratovich, D.: Tradeoff cryptanalysis of memory-hard functions. Cryptology ePrint Archive, Report 2015/227 (2015)

17.

Biryukov, A., Khovratovich, D.: Equihash: asymmetric proof-of-work based on the generalized birthday problem. In: NDSS (2016)

18.

Chung, F.R.K.: On concentrators, superconcentrators, generalizers, and nonblocking networks. Bell Syst. Techn. J. 58(8), 1765–1777 (1979)MathSciNetCrossRefMATH

19.

Cook, S.A.: An observation on time-storage trade off. In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, pp. 29–33. ACM (1973)

20.

Corrigan-Gibbs, H., Boneh, D., Schechter, S.: Balloon hashing: a provably memory-hard function with a data-independent access pattern. Cryptology ePrint Archive, Report 2016/027 (2016)

21.

Dwork, C., Goldberg, A., Naor, M.: On memory-bound functions for fighting spam. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 426–444. Springer, Heidelberg (2003). doi:10.1007/978-3-540-45146-4_25 CrossRef

22.

Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993)CrossRef

23.

Dwork, C., Naor, M., Wee, H.M.: Pebbling and proofs of work. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 37–54. Springer, Heidelberg (2005)CrossRef

24.

Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs of space. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 585–605. Springer, Heidelberg (2015)CrossRef

25.

Dziembowski, S., Kazana, T., Wichs, D.: Key-evolution schemes resilient to space-bounded leakage. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 335–353. Springer, Heidelberg (2011)CrossRef

26.

Dziembowski, S., Kazana, T., Wichs, D.: One-time computable self-erasing functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 125–143. Springer, Heidelberg (2011)CrossRef

27.

Forler, C., List, E., Lucks, S., Wenzel, J.: Overview of the candidates for the password hashing competition (2015)

28.

Forler, C., Lucks, S., Wenzel, J.: Catena: a memory-consuming password-scrambling framework. Cryptology ePrint Archive, Report 2013/525 (2013)

29.

Hopcroft, J., Paul, W., Valiant, L.: On time versus space and related problems. In: 16th Annual Symposium on Foundations of Computer Science, pp. 57–64. IEEE (1975)

30.

Juels, A., Kaliski Jr., B.S.: PORs: proofs of retrievability for large files. In: Proceedings of the 14th ACM Conference on Computer and Communications Security, pp. 584–597. ACM (2007)

31.

Karvelas, N.P., Kiayias, A.: Efficient proofs of secure erasure. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 520–537. Springer, Heidelberg (2014)

32.

Lengauer, T., Tarjan, R.E.: Asymptotically tight bounds on time-space trade-offs in a pebble game. J. ACM 29(4), 1087–1130 (1982)MathSciNetCrossRefMATH

33.

Lerner, S.D.: Strict memory hard hashing functions (preliminary v0. 3, 01-19-14)

34.

Mahmoody, M., Moran, T., Vadhan, S.: Publicly verifiable proofs of sequential work. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pp. 373–388. ACM (2013)

35.

Moran, T., Orlov, I.: Proofs of space-time and rational proofs of storage. Cryptology ePrint Archive, Report 2016/035 (2016)

36.

Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)

37.

Paul, W.J., Tarjan, R.E.: Time-space trade-offs in a pebble game. Acta Informatica 10(2), 111–115 (1978)MathSciNetCrossRefMATH

38.

Paul, W.J., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. Math. Syst. Theory 10(1), 239–251 (1976)MathSciNetCrossRefMATH

39.

Percival, C.: Stronger key derivation via sequential memory-hard functions (2009)

40.

Perito, D., Tsudik, G.: Secure code update for embedded devices via proofs of secure erasure. In: Gritzalis, D., Preneel, B., Theoharidou, M. (eds.) ESORICS 2010. LNCS, vol. 6345, pp. 643–662. Springer, Heidelberg (2010)CrossRef

41.

Peslyak, A.: yescrypt - a password hashing competition submission (2014). https://password-hashing.net/submissions/specs/yescrypt-v2.pdf. Accessed Aug 2016

42.

Pinsker, M.S.: On the complexity of a concentrator. In: 7th International Telegraffic Conference, vol. 4 (1973)

43.

Robbins, H.: A remark on Stirling’s formula. Am. Math. Monthly 62(1), 26–29 (1955)CrossRefMATH

44.

Schöning, U.: Better expanders and superconcentrators by Kolmogorov complexity. In: SIROCCO, pp. 138–150 (1997)

45.

Schöning, U.: Smaller superconcentrators of density 28. Inf. Process. Lett. 98(4), 127–129 (2006)MathSciNetCrossRefMATH

46.

Sethi, R.: Complete register allocation problems. SIAM J. Comput. 4(3), 226–248 (1975)MathSciNetCrossRefMATH

47.

Smith, A., Zhang, Y.: Near-linear time, leakage-resilient key evolution schemes from expander graphs. Cryptology ePrint Archive, Report 2013/864 (2013)

48.

Tromp, J.: Cuckoo cycle: a memory-hard proof-of-work system (2014)

Titel: Proof of Space from Stacked Expanders
verfasst von: Ling Ren
Srinivas Devadas
Verlag: Springer Berlin Heidelberg
Buch: Theory of Cryptography
Print ISBN: 978-3-662-53640-7

Electronic ISBN: 978-3-662-53641-4

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-53641-4_11

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"

Premium Partner