[{"page":"451 - 467","date_created":"2018-12-11T11:45:42Z","doi":"10.1007/978-3-319-78375-8_15","date_published":"2018-05-29T00:00:00Z","year":"2018","isi":1,"day":"29","oa":1,"publisher":"Springer","quality_controlled":"1","external_id":{"isi":["000517098700015"]},"article_processing_charge":"No","author":[{"first_name":"Bram","last_name":"Cohen","full_name":"Cohen, Bram"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"publist_id":"7579","title":"Simple proofs of sequential work","citation":{"ieee":"B. Cohen and K. Z. Pietrzak, “Simple proofs of sequential work,” presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10821, pp. 451–467.","short":"B. Cohen, K.Z. Pietrzak, in:, Springer, 2018, pp. 451–467.","apa":"Cohen, B., & Pietrzak, K. Z. (2018). Simple proofs of sequential work (Vol. 10821, pp. 451–467). Presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78375-8_15","ama":"Cohen B, Pietrzak KZ. Simple proofs of sequential work. In: Vol 10821. Springer; 2018:451-467. doi:10.1007/978-3-319-78375-8_15","mla":"Cohen, Bram, and Krzysztof Z. Pietrzak. Simple Proofs of Sequential Work. Vol. 10821, Springer, 2018, pp. 451–67, doi:10.1007/978-3-319-78375-8_15.","ista":"Cohen B, Pietrzak KZ. 2018. Simple proofs of sequential work. Eurocrypt: Advances in Cryptology, LNCS, vol. 10821, 451–467.","chicago":"Cohen, Bram, and Krzysztof Z Pietrzak. “Simple Proofs of Sequential Work,” 10821:451–67. Springer, 2018. https://doi.org/10.1007/978-3-319-78375-8_15."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"ec_funded":1,"volume":10821,"publication_status":"published","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://eprint.iacr.org/2018/183.pdf","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":"1","intvolume":" 10821","month":"05","abstract":[{"text":"At ITCS 2013, Mahmoody, Moran and Vadhan [MMV13] introduce and construct publicly verifiable proofs of sequential work, which is a protocol for proving that one spent sequential computational work related to some statement. The original motivation for such proofs included non-interactive time-stamping and universally verifiable CPU benchmarks. A more recent application, and our main motivation, are blockchain designs, where proofs of sequential work can be used – in combination with proofs of space – as a more ecological and economical substitute for proofs of work which are currently used to secure Bitcoin and other cryptocurrencies. The construction proposed by [MMV13] is based on a hash function and can be proven secure in the random oracle model, or assuming inherently sequential hash-functions, which is a new standard model assumption introduced in their work. In a proof of sequential work, a prover gets a “statement” χ, a time parameter N and access to a hash-function H, which for the security proof is modelled as a random oracle. Correctness requires that an honest prover can make a verifier accept making only N queries to H, while soundness requires that any prover who makes the verifier accept must have made (almost) N sequential queries to H. Thus a solution constitutes a proof that N time passed since χ was received. Solutions must be publicly verifiable in time at most polylogarithmic in N. The construction of [MMV13] is based on “depth-robust” graphs, and as a consequence has rather poor concrete parameters. But the major drawback is that the prover needs not just N time, but also N space to compute a proof. In this work we propose a proof of sequential work which is much simpler, more efficient and achieves much better concrete bounds. Most importantly, the space required can be as small as log (N) (but we get better soundness using slightly more memory than that). An open problem stated by [MMV13] that our construction does not solve either is achieving a “unique” proof, where even a cheating prover can only generate a single accepting proof. This property would be extremely useful for applications to blockchains.","lang":"eng"}],"oa_version":"Submitted Version","department":[{"_id":"KrPi"}],"date_updated":"2023-09-18T09:29:33Z","conference":{"end_date":"2018-05-03","location":"Tel Aviv, Israel","start_date":"2018-04-29","name":"Eurocrypt: Advances in Cryptology"},"type":"conference","status":"public","_id":"302"},{"oa":1,"quality_controlled":"1","publisher":"Springer","date_created":"2018-12-11T11:45:41Z","doi":"10.1007/978-3-319-78375-8_4","date_published":"2018-03-31T00:00:00Z","page":"99 - 130","day":"31","year":"2018","isi":1,"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"title":"Sustained space complexity","external_id":{"isi":["000517098700004"],"arxiv":["1705.05313"]},"article_processing_charge":"No","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F","last_name":"Alwen","full_name":"Alwen, Joel F"},{"full_name":"Blocki, Jeremiah","last_name":"Blocki","first_name":"Jeremiah"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}],"publist_id":"7583","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Alwen, Joel F, Jeremiah Blocki, and Krzysztof Z Pietrzak. “Sustained Space Complexity,” 10821:99–130. Springer, 2018. https://doi.org/10.1007/978-3-319-78375-8_4.","ista":"Alwen JF, Blocki J, Pietrzak KZ. 2018. Sustained space complexity. Eurocrypt 2018: Advances in Cryptology, LNCS, vol. 10821, 99–130.","mla":"Alwen, Joel F., et al. Sustained Space Complexity. Vol. 10821, Springer, 2018, pp. 99–130, doi:10.1007/978-3-319-78375-8_4.","ama":"Alwen JF, Blocki J, Pietrzak KZ. Sustained space complexity. In: Vol 10821. Springer; 2018:99-130. doi:10.1007/978-3-319-78375-8_4","apa":"Alwen, J. F., Blocki, J., & Pietrzak, K. Z. (2018). Sustained space complexity (Vol. 10821, pp. 99–130). Presented at the Eurocrypt 2018: Advances in Cryptology, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78375-8_4","short":"J.F. Alwen, J. Blocki, K.Z. Pietrzak, in:, Springer, 2018, pp. 99–130.","ieee":"J. F. Alwen, J. Blocki, and K. Z. Pietrzak, “Sustained space complexity,” presented at the Eurocrypt 2018: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10821, pp. 99–130."},"intvolume":" 10821","month":"03","main_file_link":[{"url":"https://arxiv.org/abs/1705.05313","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":"1","oa_version":"Preprint","abstract":[{"lang":"eng","text":"Memory-hard functions (MHF) are functions whose evaluation cost is dominated by memory cost. MHFs are egalitarian, in the sense that evaluating them on dedicated hardware (like FPGAs or ASICs) is not much cheaper than on off-the-shelf hardware (like x86 CPUs). MHFs have interesting cryptographic applications, most notably to password hashing and securing blockchains.\r\n\r\nAlwen and Serbinenko [STOC’15] define the cumulative memory complexity (cmc) of a function as the sum (over all time-steps) of the amount of memory required to compute the function. They advocate that a good MHF must have high cmc. Unlike previous notions, cmc takes into account that dedicated hardware might exploit amortization and parallelism. Still, cmc has been critizised as insufficient, as it fails to capture possible time-memory trade-offs; as memory cost doesn’t scale linearly, functions with the same cmc could still have very different actual hardware cost.\r\n\r\nIn this work we address this problem, and introduce the notion of sustained-memory complexity, which requires that any algorithm evaluating the function must use a large amount of memory for many steps. We construct functions (in the parallel random oracle model) whose sustained-memory complexity is almost optimal: our function can be evaluated using n steps and O(n/log(n)) memory, in each step making one query to the (fixed-input length) random oracle, while any algorithm that can make arbitrary many parallel queries to the random oracle, still needs Ω(n/log(n)) memory for Ω(n) steps.\r\n\r\nAs has been done for various notions (including cmc) before, we reduce the task of constructing an MHFs with high sustained-memory complexity to proving pebbling lower bounds on DAGs. Our main technical contribution is the construction is a family of DAGs on n nodes with constant indegree with high “sustained-space complexity”, meaning that any parallel black-pebbling strategy requires Ω(n/log(n)) pebbles for at least Ω(n) steps.\r\n\r\nAlong the way we construct a family of maximally “depth-robust” DAGs with maximum indegree O(logn) , improving upon the construction of Mahmoody et al. [ITCS’13] which had maximum indegree O(log2n⋅"}],"ec_funded":1,"volume":10821,"language":[{"iso":"eng"}],"publication_status":"published","status":"public","conference":{"name":"Eurocrypt 2018: Advances in Cryptology","start_date":"2018-04-29","location":"Tel Aviv, Israel","end_date":"2018-05-03"},"type":"conference","_id":"298","department":[{"_id":"KrPi"}],"date_updated":"2023-09-19T09:59:30Z"},{"day":"01","publication":"American Institute of Mathematical Sciences","language":[{"iso":"eng"}],"isi":1,"year":"2018","publication_status":"published","issue":"1","doi":"10.3934/amc.2018002","volume":12,"date_published":"2018-02-01T00:00:00Z","date_created":"2019-02-13T13:49:41Z","page":"17-47","oa_version":"None","abstract":[{"lang":"eng","text":"The problem of private set-intersection (PSI) has been traditionally treated as an instance of the more general problem of multi-party computation (MPC). Consequently, in order to argue security, or compose these protocols one has to rely on the general theory that was developed for the purpose of MPC. The pursuit of efficient protocols, however, has resulted in designs that exploit properties pertaining to PSI. In almost all practical applications where a PSI protocol is deployed, it is expected to be executed multiple times, possibly on related inputs. In this work we initiate a dedicated study of PSI in the multi-interaction (MI) setting. In this model a server sets up the common system parameters and executes set-intersection multiple times with potentially different clients. We discuss a few attacks that arise when protocols are naïvely composed in this manner and, accordingly, craft security definitions for the MI setting and study their inter-relation. Finally, we suggest a set of protocols that are MI-secure, at the same time almost as efficient as their parent, stand-alone, protocols."}],"month":"02","intvolume":" 12","scopus_import":"1","quality_controlled":"1","publisher":"AIMS","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Chatterjee S, Kamath Hosdurg C, Kumar V. 2018. Private set-intersection with common set-up. American Institute of Mathematical Sciences. 12(1), 17–47.","chicago":"Chatterjee, Sanjit, Chethan Kamath Hosdurg, and Vikas Kumar. “Private Set-Intersection with Common Set-Up.” American Institute of Mathematical Sciences. AIMS, 2018. https://doi.org/10.3934/amc.2018002.","short":"S. Chatterjee, C. Kamath Hosdurg, V. Kumar, American Institute of Mathematical Sciences 12 (2018) 17–47.","ieee":"S. Chatterjee, C. Kamath Hosdurg, and V. Kumar, “Private set-intersection with common set-up,” American Institute of Mathematical Sciences, vol. 12, no. 1. AIMS, pp. 17–47, 2018.","apa":"Chatterjee, S., Kamath Hosdurg, C., & Kumar, V. (2018). Private set-intersection with common set-up. American Institute of Mathematical Sciences. AIMS. https://doi.org/10.3934/amc.2018002","ama":"Chatterjee S, Kamath Hosdurg C, Kumar V. Private set-intersection with common set-up. American Institute of Mathematical Sciences. 2018;12(1):17-47. doi:10.3934/amc.2018002","mla":"Chatterjee, Sanjit, et al. “Private Set-Intersection with Common Set-Up.” American Institute of Mathematical Sciences, vol. 12, no. 1, AIMS, 2018, pp. 17–47, doi:10.3934/amc.2018002."},"date_updated":"2023-09-19T14:27:59Z","department":[{"_id":"KrPi"}],"title":"Private set-intersection with common set-up","author":[{"full_name":"Chatterjee, Sanjit","last_name":"Chatterjee","first_name":"Sanjit"},{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan"},{"last_name":"Kumar","full_name":"Kumar, Vikas","first_name":"Vikas"}],"external_id":{"isi":["000430950400002"]},"article_processing_charge":"No","_id":"5980","status":"public","type":"journal_article"},{"title":"SpaceMint: A cryptocurrency based on proofs of space","external_id":{"isi":["000540656400026"]},"article_processing_charge":"No","author":[{"full_name":"Park, Sunoo","last_name":"Park","first_name":"Sunoo"},{"last_name":"Kwon","full_name":"Kwon, Albert","first_name":"Albert"},{"id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","full_name":"Fuchsbauer, Georg","last_name":"Fuchsbauer"},{"last_name":"Gazi","full_name":"Gazi, Peter","first_name":"Peter","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"mla":"Park, Sunoo, et al. “SpaceMint: A Cryptocurrency Based on Proofs of Space.” 22nd International Conference on Financial Cryptography and Data Security, vol. 10957, Springer Nature, 2018, pp. 480–99, doi:10.1007/978-3-662-58387-6_26.","ama":"Park S, Kwon A, Fuchsbauer G, Gazi P, Alwen JF, Pietrzak KZ. SpaceMint: A cryptocurrency based on proofs of space. In: 22nd International Conference on Financial Cryptography and Data Security. Vol 10957. Springer Nature; 2018:480-499. doi:10.1007/978-3-662-58387-6_26","apa":"Park, S., Kwon, A., Fuchsbauer, G., Gazi, P., Alwen, J. F., & Pietrzak, K. Z. (2018). SpaceMint: A cryptocurrency based on proofs of space. In 22nd International Conference on Financial Cryptography and Data Security (Vol. 10957, pp. 480–499). Nieuwpoort, Curacao: Springer Nature. https://doi.org/10.1007/978-3-662-58387-6_26","ieee":"S. Park, A. Kwon, G. Fuchsbauer, P. Gazi, J. F. Alwen, and K. Z. Pietrzak, “SpaceMint: A cryptocurrency based on proofs of space,” in 22nd International Conference on Financial Cryptography and Data Security, Nieuwpoort, Curacao, 2018, vol. 10957, pp. 480–499.","short":"S. Park, A. Kwon, G. Fuchsbauer, P. Gazi, J.F. Alwen, K.Z. Pietrzak, in:, 22nd International Conference on Financial Cryptography and Data Security, Springer Nature, 2018, pp. 480–499.","chicago":"Park, Sunoo, Albert Kwon, Georg Fuchsbauer, Peter Gazi, Joel F Alwen, and Krzysztof Z Pietrzak. “SpaceMint: A Cryptocurrency Based on Proofs of Space.” In 22nd International Conference on Financial Cryptography and Data Security, 10957:480–99. Springer Nature, 2018. https://doi.org/10.1007/978-3-662-58387-6_26.","ista":"Park S, Kwon A, Fuchsbauer G, Gazi P, Alwen JF, Pietrzak KZ. 2018. SpaceMint: A cryptocurrency based on proofs of space. 22nd International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 10957, 480–499."},"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"date_created":"2019-10-14T06:35:38Z","date_published":"2018-12-07T00:00:00Z","doi":"10.1007/978-3-662-58387-6_26","page":"480-499","publication":"22nd International Conference on Financial Cryptography and Data Security","day":"07","year":"2018","isi":1,"oa":1,"quality_controlled":"1","publisher":"Springer Nature","department":[{"_id":"KrPi"}],"date_updated":"2023-09-19T15:02:13Z","status":"public","conference":{"start_date":"2018-02-26","location":"Nieuwpoort, Curacao","end_date":"2018-03-02","name":"FC: Financial Cryptography and Data Security"},"type":"conference","_id":"6941","ec_funded":1,"volume":10957,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["0302-9743"],"isbn":["9783662583869","9783662583876"],"eissn":["1611-3349"]},"intvolume":" 10957","month":"12","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2015/528"}],"scopus_import":"1","alternative_title":["LNCS"],"oa_version":"Submitted Version","abstract":[{"text":"Bitcoin has become the most successful cryptocurrency ever deployed, and its most distinctive feature is that it is decentralized. Its underlying protocol (Nakamoto consensus) achieves this by using proof of work, which has the drawback that it causes the consumption of vast amounts of energy to maintain the ledger. Moreover, Bitcoin mining dynamics have become less distributed over time.\r\n\r\nTowards addressing these issues, we propose SpaceMint, a cryptocurrency based on proofs of space instead of proofs of work. Miners in SpaceMint dedicate disk space rather than computation. We argue that SpaceMint’s design solves or alleviates several of Bitcoin’s issues: most notably, its large energy consumption. SpaceMint also rewards smaller miners fairly according to their contribution to the network, thus incentivizing more distributed participation.\r\n\r\nThis paper adapts proof of space to enable its use in cryptocurrency, studies the attacks that can arise against a Bitcoin-like blockchain that uses proof of space, and proposes a new blockchain format and transaction types to address these attacks. Our prototype shows that initializing 1 TB for mining takes about a day (a one-off setup cost), and miners spend on average just a fraction of a second per block mined. Finally, we provide a game-theoretic analysis modeling SpaceMint as an extensive game (the canonical game-theoretic notion for games that take place over time) and show that this stylized game satisfies a strong equilibrium notion, thereby arguing for SpaceMint ’s stability and consensus.","lang":"eng"}]},{"ddc":["005","600"],"date_updated":"2021-01-12T06:48:51Z","file_date_updated":"2020-07-14T12:44:37Z","department":[{"_id":"KrPi"}],"_id":"1175","pubrep_id":"927","status":"public","conference":{"name":"ITCS: Innovations in Theoretical Computer Science","end_date":"2017-01-11","location":"Berkeley, CA, United States","start_date":"2017-01-09"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"conference","language":[{"iso":"eng"}],"file":[{"file_id":"5263","checksum":"dbc94810be07c2fb1945d5c2a6130e6c","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2018-12-12T10:17:11Z","file_name":"IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf","creator":"system","date_updated":"2020-07-14T12:44:37Z","file_size":557769}],"publication_status":"published","publication_identifier":{"issn":["18688969"]},"volume":67,"oa_version":"Published Version","abstract":[{"lang":"eng","text":"We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko ’15] as a tool for obtaining results in cryptography. We consider instead the non- deterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10–15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström ’08, ’11] we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure."}],"intvolume":" 67","month":"01","alternative_title":["LIPIcs"],"scopus_import":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Alwen JF, De Rezende S, Nordstrom J, Vinyals M. 2017. Cumulative space in black-white pebbling and resolution. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 67, 38:1-38-21.","chicago":"Alwen, Joel F, Susanna De Rezende, Jakob Nordstrom, and Marc Vinyals. “Cumulative Space in Black-White Pebbling and Resolution.” edited by Christos Papadimitriou, 67:38:1-38-21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.ITCS.2017.38.","short":"J.F. Alwen, S. De Rezende, J. Nordstrom, M. Vinyals, in:, C. Papadimitriou (Ed.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21.","ieee":"J. F. Alwen, S. De Rezende, J. Nordstrom, and M. Vinyals, “Cumulative space in black-white pebbling and resolution,” presented at the ITCS: Innovations in Theoretical Computer Science, Berkeley, CA, United States, 2017, vol. 67, p. 38:1-38-21.","ama":"Alwen JF, De Rezende S, Nordstrom J, Vinyals M. Cumulative space in black-white pebbling and resolution. In: Papadimitriou C, ed. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017:38:1-38-21. doi:10.4230/LIPIcs.ITCS.2017.38","apa":"Alwen, J. F., De Rezende, S., Nordstrom, J., & Vinyals, M. (2017). Cumulative space in black-white pebbling and resolution. In C. Papadimitriou (Ed.) (Vol. 67, p. 38:1-38-21). Presented at the ITCS: Innovations in Theoretical Computer Science, Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2017.38","mla":"Alwen, Joel F., et al. Cumulative Space in Black-White Pebbling and Resolution. Edited by Christos Papadimitriou, vol. 67, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21, doi:10.4230/LIPIcs.ITCS.2017.38."},"title":"Cumulative space in black-white pebbling and resolution","editor":[{"last_name":"Papadimitriou","full_name":"Papadimitriou, Christos","first_name":"Christos"}],"publist_id":"6179","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F","last_name":"Alwen","full_name":"Alwen, Joel F"},{"first_name":"Susanna","full_name":"De Rezende, Susanna","last_name":"De Rezende"},{"full_name":"Nordstrom, Jakob","last_name":"Nordstrom","first_name":"Jakob"},{"first_name":"Marc","last_name":"Vinyals","full_name":"Vinyals, Marc"}],"day":"01","year":"2017","has_accepted_license":"1","date_created":"2018-12-11T11:50:33Z","doi":"10.4230/LIPIcs.ITCS.2017.38","date_published":"2017-01-01T00:00:00Z","page":"38:1-38-21","oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"status":"public","conference":{"name":"TCC: Theory of Cryptography Conference","end_date":"2017-11-15","location":"Baltimore, MD, United States","start_date":"2017-11-12"},"type":"conference","_id":"605","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T08:05:53Z","intvolume":" 10677","month":"11","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/536"}],"scopus_import":1,"alternative_title":["LNCS"],"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"Position based cryptography (PBC), proposed in the seminal work of Chandran, Goyal, Moriarty, and Ostrovsky (SIAM J. Computing, 2014), aims at constructing cryptographic schemes in which the identity of the user is his geographic position. Chandran et al. construct PBC schemes for secure positioning and position-based key agreement in the bounded-storage model (Maurer, J. Cryptology, 1992). Apart from bounded memory, their security proofs need a strong additional restriction on the power of the adversary: he cannot compute joint functions of his inputs. Removing this assumption is left as an open problem. We show that an answer to this question would resolve a long standing open problem in multiparty communication complexity: finding a function that is hard to compute with low communication complexity in the simultaneous message model, but easy to compute in the fully adaptive model. On a more positive side: we also show some implications in the other direction, i.e.: we prove that lower bounds on the communication complexity of certain multiparty problems imply existence of PBC primitives. Using this result we then show two attractive ways to “bypass” our hardness result: the first uses the random oracle model, the second weakens the locality requirement in the bounded-storage model to online computability. The random oracle construction is arguably one of the simplest proposed so far in this area. Our results indicate that constructing improved provably secure protocols for PBC requires a better understanding of multiparty communication complexity. This is yet another example where negative results in one area (in our case: lower bounds in multiparty communication complexity) can be used to construct secure cryptographic schemes."}],"ec_funded":1,"volume":10677,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["978-331970499-9"]},"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"title":"Position based cryptography and multiparty communication complexity","editor":[{"first_name":"Yael","last_name":"Kalai","full_name":"Kalai, Yael"},{"full_name":"Reyzin, Leonid","last_name":"Reyzin","first_name":"Leonid"}],"publist_id":"7200","author":[{"full_name":"Brody, Joshua","last_name":"Brody","first_name":"Joshua"},{"first_name":"Stefan","full_name":"Dziembowski, Stefan","last_name":"Dziembowski"},{"first_name":"Sebastian","full_name":"Faust, Sebastian","last_name":"Faust"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Brody J, Dziembowski S, Faust S, Pietrzak KZ. 2017. Position based cryptography and multiparty communication complexity. TCC: Theory of Cryptography Conference, LNCS, vol. 10677, 56–81.","chicago":"Brody, Joshua, Stefan Dziembowski, Sebastian Faust, and Krzysztof Z Pietrzak. “Position Based Cryptography and Multiparty Communication Complexity.” edited by Yael Kalai and Leonid Reyzin, 10677:56–81. Springer, 2017. https://doi.org/10.1007/978-3-319-70500-2_3.","ama":"Brody J, Dziembowski S, Faust S, Pietrzak KZ. Position based cryptography and multiparty communication complexity. In: Kalai Y, Reyzin L, eds. Vol 10677. Springer; 2017:56-81. doi:10.1007/978-3-319-70500-2_3","apa":"Brody, J., Dziembowski, S., Faust, S., & Pietrzak, K. Z. (2017). Position based cryptography and multiparty communication complexity. In Y. Kalai & L. Reyzin (Eds.) (Vol. 10677, pp. 56–81). Presented at the TCC: Theory of Cryptography Conference, Baltimore, MD, United States: Springer. https://doi.org/10.1007/978-3-319-70500-2_3","ieee":"J. Brody, S. Dziembowski, S. Faust, and K. Z. Pietrzak, “Position based cryptography and multiparty communication complexity,” presented at the TCC: Theory of Cryptography Conference, Baltimore, MD, United States, 2017, vol. 10677, pp. 56–81.","short":"J. Brody, S. Dziembowski, S. Faust, K.Z. Pietrzak, in:, Y. Kalai, L. Reyzin (Eds.), Springer, 2017, pp. 56–81.","mla":"Brody, Joshua, et al. Position Based Cryptography and Multiparty Communication Complexity. Edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer, 2017, pp. 56–81, doi:10.1007/978-3-319-70500-2_3."},"oa":1,"quality_controlled":"1","publisher":"Springer","date_created":"2018-12-11T11:47:27Z","date_published":"2017-11-05T00:00:00Z","doi":"10.1007/978-3-319-70500-2_3","page":"56 - 81","day":"05","year":"2017"},{"year":"2017","day":"05","page":"493 - 526","date_published":"2017-11-05T00:00:00Z","doi":"10.1007/978-3-319-70500-2_17","date_created":"2018-12-11T11:47:28Z","quality_controlled":"1","publisher":"Springer","oa":1,"citation":{"mla":"Alwen, Joel F., and Björn Tackmann. Moderately Hard Functions: Definition, Instantiations, and Applications. Edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer, 2017, pp. 493–526, doi:10.1007/978-3-319-70500-2_17.","short":"J.F. Alwen, B. Tackmann, in:, Y. Kalai, L. Reyzin (Eds.), Springer, 2017, pp. 493–526.","ieee":"J. F. Alwen and B. Tackmann, “Moderately hard functions: Definition, instantiations, and applications,” presented at the TCC: Theory of Cryptography, Baltimore, MD, United States, 2017, vol. 10677, pp. 493–526.","ama":"Alwen JF, Tackmann B. Moderately hard functions: Definition, instantiations, and applications. In: Kalai Y, Reyzin L, eds. Vol 10677. Springer; 2017:493-526. doi:10.1007/978-3-319-70500-2_17","apa":"Alwen, J. F., & Tackmann, B. (2017). Moderately hard functions: Definition, instantiations, and applications. In Y. Kalai & L. Reyzin (Eds.) (Vol. 10677, pp. 493–526). Presented at the TCC: Theory of Cryptography, Baltimore, MD, United States: Springer. https://doi.org/10.1007/978-3-319-70500-2_17","chicago":"Alwen, Joel F, and Björn Tackmann. “Moderately Hard Functions: Definition, Instantiations, and Applications.” edited by Yael Kalai and Leonid Reyzin, 10677:493–526. Springer, 2017. https://doi.org/10.1007/978-3-319-70500-2_17.","ista":"Alwen JF, Tackmann B. 2017. Moderately hard functions: Definition, instantiations, and applications. TCC: Theory of Cryptography, LNCS, vol. 10677, 493–526."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"7196","author":[{"last_name":"Alwen","full_name":"Alwen, Joel F","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Tackmann, Björn","last_name":"Tackmann","first_name":"Björn"}],"title":"Moderately hard functions: Definition, instantiations, and applications","editor":[{"first_name":"Yael","last_name":"Kalai","full_name":"Kalai, Yael"},{"first_name":"Leonid","last_name":"Reyzin","full_name":"Reyzin, Leonid"}],"publication_identifier":{"isbn":["978-331970499-9"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":10677,"abstract":[{"text":"Several cryptographic schemes and applications are based on functions that are both reasonably efficient to compute and moderately hard to invert, including client puzzles for Denial-of-Service protection, password protection via salted hashes, or recent proof-of-work blockchain systems. Despite their wide use, a definition of this concept has not yet been distilled and formalized explicitly. Instead, either the applications are proven directly based on the assumptions underlying the function, or some property of the function is proven, but the security of the application is argued only informally. The goal of this work is to provide a (universal) definition that decouples the efforts of designing new moderately hard functions and of building protocols based on them, serving as an interface between the two. On a technical level, beyond the mentioned definitions, we instantiate the model for four different notions of hardness. We extend the work of Alwen and Serbinenko (STOC 2015) by providing a general tool for proving security for the first notion of memory-hard functions that allows for provably secure applications. The tool allows us to recover all of the graph-theoretic techniques developed for proving security under the older, non-composable, notion of security used by Alwen and Serbinenko. As an application of our definition of moderately hard functions, we prove the security of two different schemes for proofs of effort (PoE). We also formalize and instantiate the concept of a non-interactive proof of effort (niPoE), in which the proof is not bound to a particular communication context but rather any bit-string chosen by the prover.","lang":"eng"}],"oa_version":"Submitted Version","scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"url":"https://eprint.iacr.org/2017/945","open_access":"1"}],"month":"11","intvolume":" 10677","date_updated":"2021-01-12T08:06:04Z","department":[{"_id":"KrPi"}],"_id":"609","type":"conference","conference":{"start_date":"2017-11-12","location":"Baltimore, MD, United States","end_date":"2017-11-15","name":"TCC: Theory of Cryptography"},"status":"public"},{"author":[{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","last_name":"Alwen"},{"full_name":"Chen, Binchi","last_name":"Chen","first_name":"Binchi"},{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"first_name":"Leonid","last_name":"Reyzin","full_name":"Reyzin, Leonid"},{"first_name":"Stefano","last_name":"Tessaro","full_name":"Tessaro, Stefano"}],"publist_id":"7154","title":"Scrypt is maximally memory hard","editor":[{"first_name":"Jean-Sébastien","full_name":"Coron, Jean-Sébastien","last_name":"Coron"},{"first_name":"Jesper","full_name":"Buus Nielsen, Jesper","last_name":"Buus Nielsen"}],"citation":{"mla":"Alwen, Joel F., et al. Scrypt Is Maximally Memory Hard. Edited by Jean-Sébastien Coron and Jesper Buus Nielsen, vol. 10212, Springer, 2017, pp. 33–62, doi:10.1007/978-3-319-56617-7_2.","short":"J.F. Alwen, B. Chen, K.Z. Pietrzak, L. Reyzin, S. Tessaro, in:, J.-S. Coron, J. Buus Nielsen (Eds.), Springer, 2017, pp. 33–62.","ieee":"J. F. Alwen, B. Chen, K. Z. Pietrzak, L. Reyzin, and S. Tessaro, “Scrypt is maximally memory hard,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France, 2017, vol. 10212, pp. 33–62.","ama":"Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. Scrypt is maximally memory hard. In: Coron J-S, Buus Nielsen J, eds. Vol 10212. Springer; 2017:33-62. doi:10.1007/978-3-319-56617-7_2","apa":"Alwen, J. F., Chen, B., Pietrzak, K. Z., Reyzin, L., & Tessaro, S. (2017). Scrypt is maximally memory hard. In J.-S. Coron & J. Buus Nielsen (Eds.) (Vol. 10212, pp. 33–62). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France: Springer. https://doi.org/10.1007/978-3-319-56617-7_2","chicago":"Alwen, Joel F, Binchi Chen, Krzysztof Z Pietrzak, Leonid Reyzin, and Stefano Tessaro. “Scrypt Is Maximally Memory Hard.” edited by Jean-Sébastien Coron and Jesper Buus Nielsen, 10212:33–62. Springer, 2017. https://doi.org/10.1007/978-3-319-56617-7_2.","ista":"Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. 2017. Scrypt is maximally memory hard. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 10212, 33–62."},"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"page":"33 - 62","date_created":"2018-12-11T11:47:37Z","date_published":"2017-01-01T00:00:00Z","doi":"10.1007/978-3-319-56617-7_2","year":"2017","day":"01","oa":1,"quality_controlled":"1","publisher":"Springer","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T08:07:10Z","conference":{"end_date":"2017-05-04","location":"Paris, France","start_date":"2017-04-30","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"type":"conference","status":"public","_id":"635","ec_funded":1,"volume":10212,"publication_status":"published","publication_identifier":{"isbn":["978-331956616-0"]},"language":[{"iso":"eng"}],"main_file_link":[{"url":"https://eprint.iacr.org/2016/989","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":1,"intvolume":" 10212","month":"01","abstract":[{"text":"Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is dominated by memory cost. As memory, unlike computation, costs about the same across different platforms, MHFs cannot be evaluated at significantly lower cost on dedicated hardware like ASICs. MHFs have found widespread applications including password hashing, key derivation, and proofs-of-work. This paper focuses on scrypt, a simple candidate MHF designed by Percival, and described in RFC 7914. It has been used within a number of cryptocurrencies (e.g., Litecoin and Dogecoin) and has been an inspiration for Argon2d, one of the winners of the recent password-hashing competition. Despite its popularity, no rigorous lower bounds on its memory complexity are known. We prove that scrypt is optimally memory-hard, i.e., its cumulative memory complexity (cmc) in the parallel random oracle model is Ω(n2w), where w and n are the output length and number of invocations of the underlying hash function, respectively. High cmc is a strong security target for MHFs introduced by Alwen and Serbinenko (STOC’15) which implies high memory cost even for adversaries who can amortize the cost over many evaluations and evaluate the underlying hash functions many times in parallel. Our proof is the first showing optimal memory-hardness for any MHF. Our result improves both quantitatively and qualitatively upon the recent work by Alwen et al. (EUROCRYPT’16) who proved a weaker lower bound of Ω(n2w/ log2 n) for a restricted class of adversaries.","lang":"eng"}],"oa_version":"Submitted Version"},{"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["978-331956616-0"]},"ec_funded":1,"volume":10212,"oa_version":"Submitted Version","abstract":[{"text":"Data-independent Memory Hard Functions (iMHFS) are finding a growing number of applications in security; especially in the domain of password hashing. An important property of a concrete iMHF is specified by fixing a directed acyclic graph (DAG) Gn on n nodes. The quality of that iMHF is then captured by the following two pebbling complexities of Gn: – The parallel cumulative pebbling complexity Π∥cc(Gn) must be as high as possible (to ensure that the amortized cost of computing the function on dedicated hardware is dominated by the cost of memory). – The sequential space-time pebbling complexity Πst(Gn) should be as close as possible to Π∥cc(Gn) (to ensure that using many cores in parallel and amortizing over many instances does not give much of an advantage). In this paper we construct a family of DAGs with best possible parameters in an asymptotic sense, i.e., where Π∥cc(Gn) = Ω(n2/ log(n)) (which matches a known upper bound) and Πst(Gn) is within a constant factor of Π∥cc(Gn). Our analysis relies on a new connection between the pebbling complexity of a DAG and its depth-robustness (DR) – a well studied combinatorial property. We show that high DR is sufficient for high Π∥cc. Alwen and Blocki (CRYPTO’16) showed that high DR is necessary and so, together, these results fully characterize DAGs with high Π∥cc in terms of DR. Complementing these results, we provide new upper and lower bounds on the Π∥cc of several important candidate iMHFs from the literature. We give the first lower bounds on the memory hardness of the Catena and Balloon Hashing functions in a parallel model of computation and we give the first lower bounds of any kind for (a version) of Argon2i. Finally we describe a new class of pebbling attacks improving on those of Alwen and Blocki (CRYPTO’16). By instantiating these attacks we upperbound the Π∥cc of the Password Hashing Competition winner Argon2i and one of the Balloon Hashing functions by O (n1.71). We also show an upper bound of O(n1.625) for the Catena functions and the two remaining Balloon Hashing functions.","lang":"eng"}],"intvolume":" 10212","month":"04","main_file_link":[{"url":"https://eprint.iacr.org/2016/875","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":1,"date_updated":"2021-01-12T08:07:22Z","department":[{"_id":"KrPi"}],"_id":"640","status":"public","conference":{"start_date":"2017-04-30","location":"Paris, France","end_date":"2017-05-04","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"type":"conference","day":"01","year":"2017","date_created":"2018-12-11T11:47:39Z","date_published":"2017-04-01T00:00:00Z","doi":"10.1007/978-3-319-56617-7_1","page":"3 - 32","oa":1,"quality_controlled":"1","publisher":"Springer","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Alwen JF, Blocki J, Pietrzak KZ. 2017. Depth-robust graphs and their cumulative memory complexity. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 10212, 3–32.","chicago":"Alwen, Joel F, Jeremiah Blocki, and Krzysztof Z Pietrzak. “Depth-Robust Graphs and Their Cumulative Memory Complexity.” edited by Jean-Sébastien Coron and Jesper Buus Nielsen, 10212:3–32. Springer, 2017. https://doi.org/10.1007/978-3-319-56617-7_1.","ama":"Alwen JF, Blocki J, Pietrzak KZ. Depth-robust graphs and their cumulative memory complexity. In: Coron J-S, Buus Nielsen J, eds. Vol 10212. Springer; 2017:3-32. doi:10.1007/978-3-319-56617-7_1","apa":"Alwen, J. F., Blocki, J., & Pietrzak, K. Z. (2017). Depth-robust graphs and their cumulative memory complexity. In J.-S. Coron & J. Buus Nielsen (Eds.) (Vol. 10212, pp. 3–32). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France: Springer. https://doi.org/10.1007/978-3-319-56617-7_1","ieee":"J. F. Alwen, J. Blocki, and K. Z. Pietrzak, “Depth-robust graphs and their cumulative memory complexity,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France, 2017, vol. 10212, pp. 3–32.","short":"J.F. Alwen, J. Blocki, K.Z. Pietrzak, in:, J.-S. Coron, J. Buus Nielsen (Eds.), Springer, 2017, pp. 3–32.","mla":"Alwen, Joel F., et al. Depth-Robust Graphs and Their Cumulative Memory Complexity. Edited by Jean-Sébastien Coron and Jesper Buus Nielsen, vol. 10212, Springer, 2017, pp. 3–32, doi:10.1007/978-3-319-56617-7_1."},"title":"Depth-robust graphs and their cumulative memory complexity","editor":[{"full_name":"Coron, Jean-Sébastien","last_name":"Coron","first_name":"Jean-Sébastien"},{"first_name":"Jesper","full_name":"Buus Nielsen, Jesper","last_name":"Buus Nielsen"}],"publist_id":"7148","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F","full_name":"Alwen, Joel F","last_name":"Alwen"},{"first_name":"Jeremiah","last_name":"Blocki","full_name":"Blocki, Jeremiah"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}],"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}]},{"intvolume":" 10185","month":"04","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/1186.pdf"}],"scopus_import":1,"alternative_title":["LNCS"],"oa_version":"Submitted Version","abstract":[{"text":"Pseudoentropy has found a lot of important applications to cryptography and complexity theory. In this paper we focus on the foundational problem that has not been investigated so far, namely by how much pseudoentropy (the amount seen by computationally bounded attackers) differs from its information-theoretic counterpart (seen by unbounded observers), given certain limits on attacker’s computational power? We provide the following answer for HILL pseudoentropy, which exhibits a threshold behavior around the size exponential in the entropy amount:– If the attacker size (s) and advantage () satisfy s (formula presented) where k is the claimed amount of pseudoentropy, then the pseudoentropy boils down to the information-theoretic smooth entropy. – If s (formula presented) then pseudoentropy could be arbitrarily bigger than the information-theoretic smooth entropy. Besides answering the posted question, we show an elegant application of our result to the complexity theory, namely that it implies the clas-sical result on the existence of functions hard to approximate (due to Pippenger). In our approach we utilize non-constructive techniques: the duality of linear programming and the probabilistic method.","lang":"eng"}],"volume":10185,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["978-331955910-0"]},"status":"public","conference":{"name":"TAMC: Theory and Applications of Models of Computation","start_date":"2017-04-20","end_date":"2017-04-22","location":"Bern, Switzerland"},"type":"conference","_id":"648","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T08:07:39Z","oa":1,"publisher":"Springer","quality_controlled":"1","date_created":"2018-12-11T11:47:42Z","date_published":"2017-04-01T00:00:00Z","doi":"10.1007/978-3-319-55911-7_43","page":"600 - 613","day":"01","year":"2017","editor":[{"last_name":"Jäger","full_name":"Jäger, Gerhard","first_name":"Gerhard"},{"last_name":"Steila","full_name":"Steila, Silvia","first_name":"Silvia"}],"title":"On the complexity of breaking pseudoentropy","publist_id":"7125","author":[{"id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","first_name":"Maciej","last_name":"Skórski","full_name":"Skórski, Maciej"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Skórski M. 2017. On the complexity of breaking pseudoentropy. TAMC: Theory and Applications of Models of Computation, LNCS, vol. 10185, 600–613.","chicago":"Skórski, Maciej. “On the Complexity of Breaking Pseudoentropy.” edited by Gerhard Jäger and Silvia Steila, 10185:600–613. Springer, 2017. https://doi.org/10.1007/978-3-319-55911-7_43.","apa":"Skórski, M. (2017). On the complexity of breaking pseudoentropy. In G. Jäger & S. Steila (Eds.) (Vol. 10185, pp. 600–613). Presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland: Springer. https://doi.org/10.1007/978-3-319-55911-7_43","ama":"Skórski M. On the complexity of breaking pseudoentropy. In: Jäger G, Steila S, eds. Vol 10185. Springer; 2017:600-613. doi:10.1007/978-3-319-55911-7_43","ieee":"M. Skórski, “On the complexity of breaking pseudoentropy,” presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland, 2017, vol. 10185, pp. 600–613.","short":"M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 600–613.","mla":"Skórski, Maciej. On the Complexity of Breaking Pseudoentropy. Edited by Gerhard Jäger and Silvia Steila, vol. 10185, Springer, 2017, pp. 600–13, doi:10.1007/978-3-319-55911-7_43."}}]