[{"year":"2019","citation":{"chicago":"Fuchsbauer, Georg, Chethan Kamath Hosdurg, Karen Klein, and Krzysztof Z Pietrzak. “Adaptively Secure Proxy Re-Encryption,” 11443:317–46. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-17259-6_11.","ieee":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “Adaptively secure proxy re-encryption,” presented at the PKC: Public-Key Cryptograhy, Beijing, China, 2019, vol. 11443, pp. 317–346.","apa":"Fuchsbauer, G., Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2019). Adaptively secure proxy re-encryption (Vol. 11443, pp. 317–346). Presented at the PKC: Public-Key Cryptograhy, Beijing, China: Springer Nature. https://doi.org/10.1007/978-3-030-17259-6_11","ama":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. Adaptively secure proxy re-encryption. In: Vol 11443. Springer Nature; 2019:317-346. doi:10.1007/978-3-030-17259-6_11","ista":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. 2019. Adaptively secure proxy re-encryption. PKC: Public-Key Cryptograhy, LNCS, vol. 11443, 317–346.","mla":"Fuchsbauer, Georg, et al. Adaptively Secure Proxy Re-Encryption. Vol. 11443, Springer Nature, 2019, pp. 317–46, doi:10.1007/978-3-030-17259-6_11.","short":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, Springer Nature, 2019, pp. 317–346."},"date_updated":"2023-09-08T11:33:20Z","day":"06","doi":"10.1007/978-3-030-17259-6_11","abstract":[{"lang":"eng","text":"A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key 𝑝𝑘′. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under 𝑝𝑘′ without having to know the underlying message, while transformations from 𝑝𝑘′ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.\r\n\r\nAll existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in Open image in new window , rendering the result meaningless already for moderate Open image in new window .\r\n\r\nJafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.\r\n\r\nOur results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14)."}],"volume":11443,"scopus_import":"1","_id":"6430","author":[{"id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","last_name":"Fuchsbauer","full_name":"Fuchsbauer, Georg"},{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}],"article_processing_charge":"No","department":[{"_id":"KrPi"}],"date_created":"2019-05-13T08:13:46Z","publication_status":"published","intvolume":" 11443","alternative_title":["LNCS"],"title":"Adaptively secure proxy re-encryption","quality_controlled":"1","ec_funded":1,"page":"317-346","publisher":"Springer Nature","type":"conference","date_published":"2019-04-06T00:00:00Z","publication_identifier":{"isbn":["9783030172589"],"eissn":["16113349"],"issn":["03029743"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/426"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","related_material":{"record":[{"status":"public","id":"10035","relation":"dissertation_contains"}]},"status":"public","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"oa_version":"Preprint","month":"04","language":[{"iso":"eng"}],"conference":{"end_date":"2019-04-17","location":"Beijing, China","name":"PKC: Public-Key Cryptograhy","start_date":"2019-04-14"}},{"alternative_title":["LIPIcs"],"title":"Simple verifiable delay functions","intvolume":" 124","publication_status":"published","date_created":"2019-06-06T14:12:36Z","department":[{"_id":"KrPi"}],"article_processing_charge":"No","author":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"}],"_id":"6528","scopus_import":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2020-07-14T12:47:33Z","ec_funded":1,"quality_controlled":"1","abstract":[{"lang":"eng","text":"We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod N) where the prover doesn’t know the factorization of N and its running time is dominated by solving the puzzle, that is, compute x2T, which is conjectured to require T sequential squarings. To get a VDF we make this protocol non-interactive using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia blockchain design, which uses a VDF as akey ingredient. For typical parameters (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around three RSA exponentiations and computing the proof is 8000 times faster than solving the puzzle even without any parallelism."}],"doi":"10.4230/LIPICS.ITCS.2019.60","day":"10","date_updated":"2021-01-12T08:07:53Z","citation":{"apa":"Pietrzak, K. Z. (2019). Simple verifiable delay functions. In 10th Innovations in Theoretical Computer Science Conference (Vol. 124). San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2019.60","ama":"Pietrzak KZ. Simple verifiable delay functions. In: 10th Innovations in Theoretical Computer Science Conference. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.ITCS.2019.60","chicago":"Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” In 10th Innovations in Theoretical Computer Science Conference, Vol. 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ITCS.2019.60.","ieee":"K. Z. Pietrzak, “Simple verifiable delay functions,” in 10th Innovations in Theoretical Computer Science Conference, San Diego, CA, United States, 2019, vol. 124.","mla":"Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” 10th Innovations in Theoretical Computer Science Conference, vol. 124, 60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.ITCS.2019.60.","short":"K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","ista":"Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in Theoretical Computer Science Conference. ITCS 2019: Innovations in Theoretical Computer Science, LIPIcs, vol. 124, 60."},"year":"2019","ddc":["000"],"volume":124,"month":"01","article_number":"60","oa_version":"Published Version","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"publication":"10th Innovations in Theoretical Computer Science Conference","has_accepted_license":"1","conference":{"start_date":"2019-01-10","name":"ITCS 2019: Innovations in Theoretical Computer Science","end_date":"2019-01-12","location":"San Diego, CA, United States"},"language":[{"iso":"eng"}],"oa":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-095-8"]},"date_published":"2019-01-10T00:00:00Z","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://eprint.iacr.org/2018/627","open_access":"1"}],"file":[{"relation":"main_file","access_level":"open_access","file_id":"6529","creator":"dernst","date_created":"2019-06-06T14:22:04Z","file_size":558770,"checksum":"f0ae1bb161431d9db3dea5ace082bfb5","date_updated":"2020-07-14T12:47:33Z","content_type":"application/pdf","file_name":"2019_LIPIcs_Pietrzak.pdf"}]},{"volume":10821,"date_updated":"2023-09-19T09:59:30Z","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.","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.","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","ista":"Alwen JF, Blocki J, Pietrzak KZ. 2018. Sustained space complexity. Eurocrypt 2018: Advances in Cryptology, LNCS, vol. 10821, 99–130.","short":"J.F. Alwen, J. Blocki, K.Z. Pietrzak, in:, Springer, 2018, pp. 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."},"year":"2018","isi":1,"external_id":{"arxiv":["1705.05313"],"isi":["000517098700004"]},"arxiv":1,"doi":"10.1007/978-3-319-78375-8_4","day":"31","abstract":[{"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⋅","lang":"eng"}],"page":"99 - 130","ec_funded":1,"quality_controlled":"1","publisher":"Springer","_id":"298","scopus_import":"1","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"first_name":"Jeremiah","last_name":"Blocki","full_name":"Blocki, Jeremiah"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","article_processing_charge":"No","department":[{"_id":"KrPi"}],"date_created":"2018-12-11T11:45:41Z","alternative_title":["LNCS"],"title":"Sustained space complexity","intvolume":" 10821","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1705.05313"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","date_published":"2018-03-31T00:00:00Z","type":"conference","oa":1,"publist_id":"7583","language":[{"iso":"eng"}],"conference":{"start_date":"2018-04-29","name":"Eurocrypt 2018: Advances in Cryptology","location":"Tel Aviv, Israel","end_date":"2018-05-03"},"oa_version":"Preprint","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"month":"03"},{"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/077"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","publist_id":"7581","oa":1,"date_published":"2018-03-31T00:00:00Z","type":"conference","conference":{"location":"Tel Aviv, Israel","end_date":"2018-05-03","start_date":"2018-04-29","name":"Eurocrypt: Advances in Cryptology"},"language":[{"iso":"eng"}],"oa_version":"Submitted Version","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"month":"03","acknowledgement":"Research supported in part by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under the SafeWare program. Opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views, position or policy of the Government. The second author was also supported by the European Research Council, ERC consolidator grant (682815 - TOCNeT).","volume":10820,"doi":"10.1007/978-3-319-78381-9_1","day":"31","abstract":[{"lang":"eng","text":"We introduce a formal quantitative notion of “bit security” for a general type of cryptographic games (capturing both decision and search problems), aimed at capturing the intuition that a cryptographic primitive with k-bit security is as hard to break as an ideal cryptographic function requiring a brute force attack on a k-bit key space. Our new definition matches the notion of bit security commonly used by cryptographers and cryptanalysts when studying search (e.g., key recovery) problems, where the use of the traditional definition is well established. However, it produces a quantitatively different metric in the case of decision (indistinguishability) problems, where the use of (a straightforward generalization of) the traditional definition is more problematic and leads to a number of paradoxical situations or mismatches between theoretical/provable security and practical/common sense intuition. Key to our new definition is to consider adversaries that may explicitly declare failure of the attack. We support and justify the new definition by proving a number of technical results, including tight reductions between several standard cryptographic problems, a new hybrid theorem that preserves bit security, and an application to the security analysis of indistinguishability primitives making use of (approximate) floating point numbers. This is the first result showing that (standard precision) 53-bit floating point numbers can be used to achieve 100-bit security in the context of cryptographic primitives with general indistinguishability-based security definitions. Previous results of this type applied only to search problems, or special types of decision problems."}],"date_updated":"2023-09-13T09:12:04Z","year":"2018","citation":{"ista":"Micciancio D, Walter M. 2018. On the bit security of cryptographic primitives. Eurocrypt: Advances in Cryptology, LNCS, vol. 10820, 3–28.","mla":"Micciancio, Daniele, and Michael Walter. On the Bit Security of Cryptographic Primitives. Vol. 10820, Springer, 2018, pp. 3–28, doi:10.1007/978-3-319-78381-9_1.","short":"D. Micciancio, M. Walter, in:, Springer, 2018, pp. 3–28.","ieee":"D. Micciancio and M. Walter, “On the bit security of cryptographic primitives,” presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10820, pp. 3–28.","chicago":"Micciancio, Daniele, and Michael Walter. “On the Bit Security of Cryptographic Primitives,” 10820:3–28. Springer, 2018. https://doi.org/10.1007/978-3-319-78381-9_1.","ama":"Micciancio D, Walter M. On the bit security of cryptographic primitives. In: Vol 10820. Springer; 2018:3-28. doi:10.1007/978-3-319-78381-9_1","apa":"Micciancio, D., & Walter, M. (2018). On the bit security of cryptographic primitives (Vol. 10820, pp. 3–28). Presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78381-9_1"},"isi":1,"external_id":{"isi":["000517097500001"]},"publisher":"Springer","page":"3 - 28","quality_controlled":"1","ec_funded":1,"publication_status":"published","date_created":"2018-12-11T11:45:42Z","department":[{"_id":"KrPi"}],"article_processing_charge":"No","title":"On the bit security of cryptographic primitives","alternative_title":["LNCS"],"intvolume":" 10820","_id":"300","scopus_import":"1","author":[{"full_name":"Micciancio, Daniele","last_name":"Micciancio","first_name":"Daniele"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","last_name":"Walter","first_name":"Michael"}]},{"quality_controlled":"1","ec_funded":1,"page":"451 - 467","publisher":"Springer","author":[{"last_name":"Cohen","first_name":"Bram","full_name":"Cohen, Bram"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z"}],"scopus_import":"1","_id":"302","intvolume":" 10821","alternative_title":["LNCS"],"title":"Simple proofs of sequential work","department":[{"_id":"KrPi"}],"article_processing_charge":"No","date_created":"2018-12-11T11:45:42Z","publication_status":"published","volume":10821,"external_id":{"isi":["000517098700015"]},"isi":1,"year":"2018","citation":{"ista":"Cohen B, Pietrzak KZ. 2018. Simple proofs of sequential work. Eurocrypt: Advances in Cryptology, LNCS, vol. 10821, 451–467.","short":"B. Cohen, K.Z. Pietrzak, in:, Springer, 2018, pp. 451–467.","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.","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.","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.","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"},"date_updated":"2023-09-18T09:29:33Z","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"}],"day":"29","doi":"10.1007/978-3-319-78375-8_15","language":[{"iso":"eng"}],"conference":{"end_date":"2018-05-03","location":"Tel Aviv, Israel","name":"Eurocrypt: Advances in Cryptology","start_date":"2018-04-29"},"month":"05","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"oa_version":"Submitted Version","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/183.pdf"}],"type":"conference","date_published":"2018-05-29T00:00:00Z","oa":1,"publist_id":"7579"},{"oa":1,"publist_id":"7947","type":"journal_article","date_published":"2018-08-01T00:00:00Z","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","main_file_link":[{"url":"https://eprint.iacr.org/2009/608","open_access":"1"}],"article_number":"20","month":"08","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"grant_number":"259668","name":"Provable Security for Physical Cryptography","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"}],"oa_version":"Preprint","publication":"Journal of the ACM","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We introduce the notion of “non-malleable codes” which relaxes the notion of error correction and error detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In contrast to error correction and error detection, non-malleability can be achieved for very rich classes of modifications. We construct an efficient code that is non-malleable with respect to modifications that affect each bit of the codeword arbitrarily (i.e., leave it untouched, flip it, or set it to either 0 or 1), but independently of the value of the other bits of the codeword. Using the probabilistic method, we also show a very strong and general statement: there exists a non-malleable code for every “small enough” family F of functions via which codewords can be modified. Although this probabilistic method argument does not directly yield efficient constructions, it gives us efficient non-malleable codes in the random-oracle model for very general classes of tampering functions—e.g., functions where every bit in the tampered codeword can depend arbitrarily on any 99% of the bits in the original codeword. As an application of non-malleable codes, we show that they provide an elegant algorithmic solution to the task of protecting functionalities implemented in hardware (e.g., signature cards) against “tampering attacks.” In such attacks, the secret state of a physical system is tampered, in the hopes that future interaction with the modified system will reveal some secret information. This problem was previously studied in the work of Gennaro et al. in 2004 under the name “algorithmic tamper proof security” (ATP). We show that non-malleable codes can be used to achieve important improvements over the prior work. In particular, we show that any functionality can be made secure against a large class of tampering attacks, simply by encoding the secret state with a non-malleable code while it is stored in memory."}],"day":"01","doi":"10.1145/3178432","external_id":{"isi":["000442938200004"]},"isi":1,"citation":{"chicago":"Dziembowski, Stefan, Krzysztof Z Pietrzak, and Daniel Wichs. “Non-Malleable Codes.” Journal of the ACM. ACM, 2018. https://doi.org/10.1145/3178432.","ieee":"S. Dziembowski, K. Z. Pietrzak, and D. Wichs, “Non-malleable codes,” Journal of the ACM, vol. 65, no. 4. ACM, 2018.","apa":"Dziembowski, S., Pietrzak, K. Z., & Wichs, D. (2018). Non-malleable codes. Journal of the ACM. ACM. https://doi.org/10.1145/3178432","ama":"Dziembowski S, Pietrzak KZ, Wichs D. Non-malleable codes. Journal of the ACM. 2018;65(4). doi:10.1145/3178432","ista":"Dziembowski S, Pietrzak KZ, Wichs D. 2018. Non-malleable codes. Journal of the ACM. 65(4), 20.","mla":"Dziembowski, Stefan, et al. “Non-Malleable Codes.” Journal of the ACM, vol. 65, no. 4, 20, ACM, 2018, doi:10.1145/3178432.","short":"S. Dziembowski, K.Z. Pietrzak, D. Wichs, Journal of the ACM 65 (2018)."},"year":"2018","date_updated":"2023-09-13T09:05:17Z","volume":65,"intvolume":" 65","title":"Non-malleable codes","article_processing_charge":"No","department":[{"_id":"KrPi"}],"date_created":"2018-12-11T11:44:40Z","publication_status":"published","issue":"4","author":[{"full_name":"Dziembowski, Stefan","last_name":"Dziembowski","first_name":"Stefan"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak"},{"last_name":"Wichs","first_name":"Daniel","full_name":"Wichs, Daniel"}],"scopus_import":"1","_id":"107","article_type":"original","publisher":"ACM","quality_controlled":"1","ec_funded":1},{"conference":{"start_date":"2018-06-17 ","name":"ISIT: International Symposium on Information Theory","location":"Vail, CO, USA","end_date":"2018-06-22"},"language":[{"iso":"eng"}],"oa_version":"Submitted Version","month":"08","main_file_link":[{"url":"https://eprint.iacr.org/2017/507","open_access":"1"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","oa":1,"publist_id":"7946","date_published":"2018-08-16T00:00:00Z","type":"conference","publisher":"IEEE","quality_controlled":"1","publication_status":"published","department":[{"_id":"KrPi"}],"date_created":"2018-12-11T11:44:40Z","article_processing_charge":"No","alternative_title":["ISIT Proceedings"],"title":"Inverted leftover hash lemma","intvolume":" 2018","_id":"108","scopus_import":"1","author":[{"last_name":"Obremski","first_name":"Marciej","full_name":"Obremski, Marciej"},{"id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","full_name":"Skorski, Maciej","first_name":"Maciej","last_name":"Skorski"}],"volume":2018,"doi":"10.1109/ISIT.2018.8437654","day":"16","abstract":[{"text":"Universal hashing found a lot of applications in computer science. In cryptography the most important fact about universal families is the so called Leftover Hash Lemma, proved by Impagliazzo, Levin and Luby. In the language of modern cryptography it states that almost universal families are good extractors. In this work we provide a somewhat surprising characterization in the opposite direction. Namely, every extractor with sufficiently good parameters yields a universal family on a noticeable fraction of its inputs. Our proof technique is based on tools from extremal graph theory applied to the \\'collision graph\\' induced by the extractor, and may be of independent interest. We discuss possible applications to the theory of randomness extractors and non-malleable codes.","lang":"eng"}],"date_updated":"2023-09-13T08:23:18Z","year":"2018","citation":{"chicago":"Obremski, Marciej, and Maciej Skórski. “Inverted Leftover Hash Lemma,” Vol. 2018. IEEE, 2018. https://doi.org/10.1109/ISIT.2018.8437654.","ieee":"M. Obremski and M. Skórski, “Inverted leftover hash lemma,” presented at the ISIT: International Symposium on Information Theory, Vail, CO, USA, 2018, vol. 2018.","ama":"Obremski M, Skórski M. Inverted leftover hash lemma. In: Vol 2018. IEEE; 2018. doi:10.1109/ISIT.2018.8437654","apa":"Obremski, M., & Skórski, M. (2018). Inverted leftover hash lemma (Vol. 2018). Presented at the ISIT: International Symposium on Information Theory, Vail, CO, USA: IEEE. https://doi.org/10.1109/ISIT.2018.8437654","ista":"Obremski M, Skórski M. 2018. Inverted leftover hash lemma. ISIT: International Symposium on Information Theory, ISIT Proceedings, vol. 2018.","mla":"Obremski, Marciej, and Maciej Skórski. Inverted Leftover Hash Lemma. Vol. 2018, IEEE, 2018, doi:10.1109/ISIT.2018.8437654.","short":"M. Obremski, M. Skórski, in:, IEEE, 2018."},"isi":1,"external_id":{"isi":["000448139300368"]}},{"has_accepted_license":"1","project":[{"call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425","name":"Provable Security for Physical Cryptography","grant_number":"259668"},{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"oa_version":"Published Version","month":"09","language":[{"iso":"eng"}],"type":"dissertation","date_published":"2018-09-05T00:00:00Z","publication_identifier":{"issn":["2663-337X"]},"publist_id":"7971","oa":1,"supervisor":[{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"file":[{"date_created":"2019-04-09T06:43:41Z","file_size":876241,"checksum":"c4b5f7d111755d1396787f41886fc674","date_updated":"2020-07-14T12:48:11Z","file_name":"2018_Thesis_Abusalah.pdf","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"6245","creator":"dernst"},{"date_created":"2019-04-09T06:43:41Z","file_size":2029190,"checksum":"0f382ac56b471c48fd907d63eb87dafe","date_updated":"2020-07-14T12:48:11Z","content_type":"application/x-gzip","file_name":"2018_Thesis_Abusalah_source.tar.gz","relation":"source_file","access_level":"closed","file_id":"6246","creator":"dernst"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","related_material":{"record":[{"relation":"part_of_dissertation","id":"1229","status":"public"},{"status":"public","id":"1235","relation":"part_of_dissertation"},{"status":"public","relation":"part_of_dissertation","id":"1236"},{"id":"559","relation":"part_of_dissertation","status":"public"}]},"status":"public","_id":"83","author":[{"id":"40297222-F248-11E8-B48F-1D18A9856A87","full_name":"Abusalah, Hamza M","last_name":"Abusalah","first_name":"Hamza M"}],"department":[{"_id":"KrPi"}],"article_processing_charge":"No","date_created":"2018-12-11T11:44:32Z","publication_status":"published","pubrep_id":"1046","title":"Proof systems for sustainable decentralized cryptocurrencies","alternative_title":["ISTA Thesis"],"ec_funded":1,"page":"59","file_date_updated":"2020-07-14T12:48:11Z","publisher":"Institute of Science and Technology Austria","citation":{"ieee":"H. M. Abusalah, “Proof systems for sustainable decentralized cryptocurrencies,” Institute of Science and Technology Austria, 2018.","chicago":"Abusalah, Hamza M. “Proof Systems for Sustainable Decentralized Cryptocurrencies.” Institute of Science and Technology Austria, 2018. https://doi.org/10.15479/AT:ISTA:TH_1046.","apa":"Abusalah, H. M. (2018). Proof systems for sustainable decentralized cryptocurrencies. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:TH_1046","ama":"Abusalah HM. Proof systems for sustainable decentralized cryptocurrencies. 2018. doi:10.15479/AT:ISTA:TH_1046","ista":"Abusalah HM. 2018. Proof systems for sustainable decentralized cryptocurrencies. Institute of Science and Technology Austria.","mla":"Abusalah, Hamza M. Proof Systems for Sustainable Decentralized Cryptocurrencies. Institute of Science and Technology Austria, 2018, doi:10.15479/AT:ISTA:TH_1046.","short":"H.M. Abusalah, Proof Systems for Sustainable Decentralized Cryptocurrencies, Institute of Science and Technology Austria, 2018."},"year":"2018","date_updated":"2023-09-07T12:30:23Z","day":"05","doi":"10.15479/AT:ISTA:TH_1046","degree_awarded":"PhD","abstract":[{"text":"A proof system is a protocol between a prover and a verifier over a common input in which an honest prover convinces the verifier of the validity of true statements. Motivated by the success of decentralized cryptocurrencies, exemplified by Bitcoin, the focus of this thesis will be on proof systems which found applications in some sustainable alternatives to Bitcoin, such as the Spacemint and Chia cryptocurrencies. In particular, we focus on proofs of space and proofs of sequential work.\r\nProofs of space (PoSpace) were suggested as more ecological, economical, and egalitarian alternative to the energy-wasteful proof-of-work mining of Bitcoin. However, the state-of-the-art constructions of PoSpace are based on sophisticated graph pebbling lower bounds, and are therefore complex. Moreover, when these PoSpace are used in cryptocurrencies like Spacemint, miners can only start mining after ensuring that a commitment to their space is already added in a special transaction to the blockchain. Proofs of sequential work (PoSW) are proof systems in which a prover, upon receiving a statement x and a time parameter T, computes a proof which convinces the verifier that T time units had passed since x was received. Whereas Spacemint assumes synchrony to retain some interesting Bitcoin dynamics, Chia requires PoSW with unique proofs, i.e., PoSW in which it is hard to come up with more than one accepting proof for any true statement. In this thesis we construct simple and practically-efficient PoSpace and PoSW. When using our PoSpace in cryptocurrencies, miners can start mining on the fly, like in Bitcoin, and unlike current constructions of PoSW, which either achieve efficient verification of sequential work, or faster-than-recomputing verification of correctness of proofs, but not both at the same time, ours achieve the best of these two worlds.","lang":"eng"}],"ddc":["004"]},{"oa_version":"Submitted Version","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"},{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"month":"06","publication":"Proceedings of the 2018 on Asia Conference on Computer and Communication Security","conference":{"start_date":"2018-06-04","name":"ASIACCS: Asia Conference on Computer and Communications Security ","location":"Incheon, Republic of Korea","end_date":"2018-06-08"},"language":[{"iso":"eng"}],"publist_id":"7723","oa":1,"date_published":"2018-06-01T00:00:00Z","type":"conference","main_file_link":[{"url":"https://eprint.iacr.org/2016/783","open_access":"1"}],"status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"published","date_created":"2018-12-11T11:45:07Z","department":[{"_id":"KrPi"},{"_id":"HeEd"},{"_id":"VlKo"}],"article_processing_charge":"No","title":"On the memory hardness of data independent password hashing functions","_id":"193","scopus_import":"1","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","first_name":"Joel F","full_name":"Alwen, Joel F"},{"full_name":"Gazi, Peter","first_name":"Peter","last_name":"Gazi"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","first_name":"Chethan"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen"},{"orcid":"0000-0002-8882-5116","full_name":"Osang, Georg F","first_name":"Georg F","last_name":"Osang","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Reyzin","first_name":"Lenoid","full_name":"Reyzin, Lenoid"},{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","last_name":"Rolinek","first_name":"Michal","full_name":"Rolinek, Michal"},{"id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87","first_name":"Michal","last_name":"Rybar","full_name":"Rybar, Michal"}],"publisher":"ACM","page":"51 - 65","quality_controlled":"1","ec_funded":1,"doi":"10.1145/3196494.3196534","day":"01","abstract":[{"text":"We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition (PHC). Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower hardware and/or energy cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks. Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC. Ideally, one would like the complexity of a DAG underlying an iMHF to be as close to quadratic in the number of nodes of the graph as possible. Instead, we show that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial property of each underlying DAG (called its depth-robustness. By establishing upper bounds on this property we are then able to apply the general technique of [Alwen-Block'16] for analyzing the hardware costs of an iMHF.","lang":"eng"}],"date_updated":"2023-09-13T09:13:12Z","year":"2018","citation":{"chicago":"Alwen, Joel F, Peter Gazi, Chethan Kamath Hosdurg, Karen Klein, Georg F Osang, Krzysztof Z Pietrzak, Lenoid Reyzin, Michal Rolinek, and Michal Rybar. “On the Memory Hardness of Data Independent Password Hashing Functions.” In Proceedings of the 2018 on Asia Conference on Computer and Communication Security, 51–65. ACM, 2018. https://doi.org/10.1145/3196494.3196534.","ieee":"J. F. Alwen et al., “On the memory hardness of data independent password hashing functions,” in Proceedings of the 2018 on Asia Conference on Computer and Communication Security, Incheon, Republic of Korea, 2018, pp. 51–65.","ama":"Alwen JF, Gazi P, Kamath Hosdurg C, et al. On the memory hardness of data independent password hashing functions. In: Proceedings of the 2018 on Asia Conference on Computer and Communication Security. ACM; 2018:51-65. doi:10.1145/3196494.3196534","apa":"Alwen, J. F., Gazi, P., Kamath Hosdurg, C., Klein, K., Osang, G. F., Pietrzak, K. Z., … Rybar, M. (2018). On the memory hardness of data independent password hashing functions. In Proceedings of the 2018 on Asia Conference on Computer and Communication Security (pp. 51–65). Incheon, Republic of Korea: ACM. https://doi.org/10.1145/3196494.3196534","ista":"Alwen JF, Gazi P, Kamath Hosdurg C, Klein K, Osang GF, Pietrzak KZ, Reyzin L, Rolinek M, Rybar M. 2018. On the memory hardness of data independent password hashing functions. Proceedings of the 2018 on Asia Conference on Computer and Communication Security. ASIACCS: Asia Conference on Computer and Communications Security , 51–65.","short":"J.F. Alwen, P. Gazi, C. Kamath Hosdurg, K. Klein, G.F. Osang, K.Z. Pietrzak, L. Reyzin, M. Rolinek, M. Rybar, in:, Proceedings of the 2018 on Asia Conference on Computer and Communication Security, ACM, 2018, pp. 51–65.","mla":"Alwen, Joel F., et al. “On the Memory Hardness of Data Independent Password Hashing Functions.” Proceedings of the 2018 on Asia Conference on Computer and Communication Security, ACM, 2018, pp. 51–65, doi:10.1145/3196494.3196534."},"isi":1,"external_id":{"isi":["000516620100005"]},"acknowledgement":"Leonid Reyzin was supported in part by IST Austria and by US NSF grants 1012910, 1012798, and 1422965; this research was performed while he was visiting IST Austria."},{"month":"12","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"oa_version":"Submitted Version","publication":"22nd International Conference on Financial Cryptography and Data Security","conference":{"end_date":"2018-03-02","location":"Nieuwpoort, Curacao","name":"FC: Financial Cryptography and Data Security","start_date":"2018-02-26"},"language":[{"iso":"eng"}],"oa":1,"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783662583869","9783662583876"]},"type":"conference","date_published":"2018-12-07T00:00:00Z","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2015/528"}],"intvolume":" 10957","alternative_title":["LNCS"],"title":"SpaceMint: A cryptocurrency based on proofs of space","article_processing_charge":"No","department":[{"_id":"KrPi"}],"date_created":"2019-10-14T06:35:38Z","publication_status":"published","author":[{"last_name":"Park","first_name":"Sunoo","full_name":"Park, Sunoo"},{"full_name":"Kwon, Albert","first_name":"Albert","last_name":"Kwon"},{"id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","last_name":"Fuchsbauer","first_name":"Georg","full_name":"Fuchsbauer, Georg"},{"first_name":"Peter","last_name":"Gazi","full_name":"Gazi, Peter","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87"},{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","last_name":"Alwen","first_name":"Joel F"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":"1","_id":"6941","publisher":"Springer Nature","ec_funded":1,"quality_controlled":"1","page":"480-499","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"}],"day":"07","doi":"10.1007/978-3-662-58387-6_26","external_id":{"isi":["000540656400026"]},"isi":1,"year":"2018","citation":{"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.","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.","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","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","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.","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.","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."},"date_updated":"2023-09-19T15:02:13Z","volume":10957},{"conference":{"location":"San Diego, CA, United States","end_date":"2019-01-12","name":"ITCS: Innovations in theoretical Computer Science Conference","start_date":"2019-01-10"},"language":[{"iso":"eng"}],"month":"12","oa_version":"Published Version","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"publication":"10th Innovations in Theoretical Computer Science Conference (ITCS 2019)","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","file":[{"date_updated":"2020-07-14T12:47:57Z","content_type":"application/pdf","file_name":"2018_LIPIcs_Pietrzak.pdf","date_created":"2020-02-04T08:17:52Z","checksum":"5cebb7f7849a3beda898f697d755dd96","file_size":822884,"file_id":"7443","creator":"dernst","access_level":"open_access","relation":"main_file"}],"main_file_link":[{"url":"https://eprint.iacr.org/2018/194","open_access":"1"}],"oa":1,"publication_identifier":{"isbn":["978-3-95977-095-8"],"issn":["1868-8969"]},"date_published":"2018-12-31T00:00:00Z","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2020-07-14T12:47:57Z","page":"59:1-59:25","ec_funded":1,"quality_controlled":"1","alternative_title":["LIPIcs"],"title":"Proofs of catalytic space","intvolume":" 124","publication_status":"published","department":[{"_id":"KrPi"}],"date_created":"2020-01-30T09:16:05Z","article_processing_charge":"No","author":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"}],"_id":"7407","scopus_import":1,"ddc":["000"],"volume":124,"abstract":[{"lang":"eng","text":"Proofs of space (PoS) [Dziembowski et al., CRYPTO'15] are proof systems where a prover can convince a verifier that he \"wastes\" disk space. PoS were introduced as a more ecological and economical replacement for proofs of work which are currently used to secure blockchains like Bitcoin. In this work we investigate extensions of PoS which allow the prover to embed useful data into the dedicated space, which later can be recovered. Our first contribution is a security proof for the original PoS from CRYPTO'15 in the random oracle model (the original proof only applied to a restricted class of adversaries which can store a subset of the data an honest prover would store). When this PoS is instantiated with recent constructions of maximally depth robust graphs, our proof implies basically optimal security. As a second contribution we show three different extensions of this PoS where useful data can be embedded into the space required by the prover. Our security proof for the PoS extends (non-trivially) to these constructions. We discuss how some of these variants can be used as proofs of catalytic space (PoCS), a notion we put forward in this work, and which basically is a PoS where most of the space required by the prover can be used to backup useful data. Finally we discuss how one of the extensions is a candidate construction for a proof of replication (PoR), a proof system recently suggested in the Filecoin whitepaper. "}],"doi":"10.4230/LIPICS.ITCS.2019.59","day":"31","date_updated":"2021-01-12T08:13:26Z","year":"2018","citation":{"chicago":"Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), 124:59:1-59:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ITCS.2019.59.","ieee":"K. Z. Pietrzak, “Proofs of catalytic space,” in 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), San Diego, CA, United States, 2018, vol. 124, p. 59:1-59:25.","apa":"Pietrzak, K. Z. (2018). Proofs of catalytic space. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) (Vol. 124, p. 59:1-59:25). San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2019.59","ama":"Pietrzak KZ. Proofs of catalytic space. In: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Vol 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:59:1-59:25. doi:10.4230/LIPICS.ITCS.2019.59","ista":"Pietrzak KZ. 2018. Proofs of catalytic space. 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). ITCS: Innovations in theoretical Computer Science Conference, LIPIcs, vol. 124, 59:1-59:25.","mla":"Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), vol. 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25, doi:10.4230/LIPICS.ITCS.2019.59.","short":"K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25."}},{"author":[{"last_name":"Chatterjee","first_name":"Sanjit","full_name":"Chatterjee, Sanjit"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg"},{"last_name":"Kumar","first_name":"Vikas","full_name":"Kumar, Vikas"}],"issue":"1","_id":"5980","publication":"American Institute of Mathematical Sciences","scopus_import":"1","title":"Private set-intersection with common set-up","month":"02","intvolume":" 12","oa_version":"None","publication_status":"published","department":[{"_id":"KrPi"}],"date_created":"2019-02-13T13:49:41Z","article_processing_charge":"No","language":[{"iso":"eng"}],"page":"17-47","quality_controlled":"1","publisher":"AIMS","date_published":"2018-02-01T00:00:00Z","isi":1,"type":"journal_article","external_id":{"isi":["000430950400002"]},"date_updated":"2023-09-19T14:27:59Z","citation":{"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","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.","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.","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.","short":"S. Chatterjee, C. Kamath Hosdurg, V. Kumar, American Institute of Mathematical Sciences 12 (2018) 17–47.","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."},"year":"2018","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."}],"doi":"10.3934/amc.2018002","day":"01","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","volume":12},{"date_updated":"2021-11-15T10:48:49Z","year":"2018","citation":{"chicago":"Allini, Elie Noumon, Maciej Skórski, Oto Petura, Florent Bernard, Marek Laban, and Viktor Fischer. “Evaluation and Monitoring of Free Running Oscillators Serving as Source of Randomness.” IACR Transactions on Cryptographic Hardware and Embedded Systems. International Association for Cryptologic Research, 2018. https://doi.org/10.13154/tches.v2018.i3.214-242.","ieee":"E. N. Allini, M. Skórski, O. Petura, F. Bernard, M. Laban, and V. Fischer, “Evaluation and monitoring of free running oscillators serving as source of randomness,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2018, no. 3. International Association for Cryptologic Research, pp. 214–242, 2018.","apa":"Allini, E. N., Skórski, M., Petura, O., Bernard, F., Laban, M., & Fischer, V. (2018). Evaluation and monitoring of free running oscillators serving as source of randomness. IACR Transactions on Cryptographic Hardware and Embedded Systems. International Association for Cryptologic Research. https://doi.org/10.13154/tches.v2018.i3.214-242","ama":"Allini EN, Skórski M, Petura O, Bernard F, Laban M, Fischer V. Evaluation and monitoring of free running oscillators serving as source of randomness. IACR Transactions on Cryptographic Hardware and Embedded Systems. 2018;2018(3):214-242. doi:10.13154/tches.v2018.i3.214-242","ista":"Allini EN, Skórski M, Petura O, Bernard F, Laban M, Fischer V. 2018. Evaluation and monitoring of free running oscillators serving as source of randomness. IACR Transactions on Cryptographic Hardware and Embedded Systems. 2018(3), 214–242.","short":"E.N. Allini, M. Skórski, O. Petura, F. Bernard, M. Laban, V. Fischer, IACR Transactions on Cryptographic Hardware and Embedded Systems 2018 (2018) 214–242.","mla":"Allini, Elie Noumon, et al. “Evaluation and Monitoring of Free Running Oscillators Serving as Source of Randomness.” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2018, no. 3, International Association for Cryptologic Research, 2018, pp. 214–42, doi:10.13154/tches.v2018.i3.214-242."},"doi":"10.13154/tches.v2018.i3.214-242","day":"01","abstract":[{"lang":"eng","text":"In this paper, we evaluate clock signals generated in ring oscillators and self-timed rings and the way their jitter can be transformed into random numbers. We show that counting the periods of the jittery clock signal produces random numbers of significantly better quality than the methods in which the jittery signal is simply sampled (the case in almost all current methods). Moreover, we use the counter values to characterize and continuously monitor the source of randomness. However, instead of using the widely used statistical variance, we propose to use Allan variance to do so. There are two main advantages: Allan variance is insensitive to low frequency noises such as flicker noise that are known to be autocorrelated and significantly less circuitry is required for its computation than that used to compute commonly used variance. We also show that it is essential to use a differential principle of randomness extraction from the jitter based on the use of two identical oscillators to avoid autocorrelations originating from external and internal global jitter sources and that this fact is valid for both kinds of rings. Last but not least, we propose a method of statistical testing based on high order Markov model to show the reduced dependencies when the proposed randomness extraction is applied."}],"volume":2018,"ddc":["000"],"_id":"10286","scopus_import":"1","author":[{"last_name":"Allini","first_name":"Elie Noumon","full_name":"Allini, Elie Noumon"},{"full_name":"Skórski, Maciej","last_name":"Skórski","first_name":"Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"},{"last_name":"Petura","first_name":"Oto","full_name":"Petura, Oto"},{"first_name":"Florent","last_name":"Bernard","full_name":"Bernard, Florent"},{"full_name":"Laban, Marek","first_name":"Marek","last_name":"Laban"},{"first_name":"Viktor","last_name":"Fischer","full_name":"Fischer, Viktor"}],"issue":"3","publication_status":"published","article_processing_charge":"No","department":[{"_id":"KrPi"}],"date_created":"2021-11-14T23:01:25Z","title":"Evaluation and monitoring of free running oscillators serving as source of randomness","intvolume":" 2018","page":"214-242","quality_controlled":"1","file_date_updated":"2021-11-15T10:27:29Z","publisher":"International Association for Cryptologic Research","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2018-01-01T00:00:00Z","type":"journal_article","publication_identifier":{"eissn":["2569-2925"]},"oa":1,"file":[{"creator":"cchlebak","file_id":"10289","relation":"main_file","success":1,"access_level":"open_access","content_type":"application/pdf","file_name":"2018_IACR_Allini.pdf","date_updated":"2021-11-15T10:27:29Z","file_size":955755,"checksum":"b816b848f046c48a8357700d9305dce5","date_created":"2021-11-15T10:27:29Z"}],"status":"public","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publication":"IACR Transactions on Cryptographic Hardware and Embedded Systems","has_accepted_license":"1","oa_version":"Published Version","month":"01","language":[{"iso":"eng"}]},{"main_file_link":[{"url":"http://drops.dagstuhl.de/opus/volltexte/2017/6976","open_access":"1"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","date_published":"2017-03-01T00:00:00Z","type":"conference","publication_identifier":{"issn":["18688969"]},"publist_id":"6180","oa":1,"language":[{"iso":"eng"}],"conference":{"end_date":"2017-03-11","location":"Hannover, Germany","start_date":"2017-03-08","name":"STACS: Symposium on Theoretical Aspects of Computer Science"},"oa_version":"Submitted Version","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"month":"03","article_number":"57","volume":66,"date_updated":"2023-09-20T11:23:15Z","citation":{"ama":"Skórski M. Lower bounds on key derivation for square-friendly applications. In: Vol 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.STACS.2017.57","apa":"Skórski, M. (2017). Lower bounds on key derivation for square-friendly applications (Vol. 66). Presented at the STACS: Symposium on Theoretical Aspects of Computer Science, Hannover, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2017.57","chicago":"Skórski, Maciej. “Lower Bounds on Key Derivation for Square-Friendly Applications,” Vol. 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.STACS.2017.57.","ieee":"M. Skórski, “Lower bounds on key derivation for square-friendly applications,” presented at the STACS: Symposium on Theoretical Aspects of Computer Science, Hannover, Germany, 2017, vol. 66.","short":"M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Skórski, Maciej. Lower Bounds on Key Derivation for Square-Friendly Applications. Vol. 66, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.STACS.2017.57.","ista":"Skórski M. 2017. Lower bounds on key derivation for square-friendly applications. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 66, 57."},"year":"2017","isi":1,"external_id":{"isi":["000521077300057"]},"doi":"10.4230/LIPIcs.STACS.2017.57","day":"01","abstract":[{"lang":"eng","text":"Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for key derivation. Barak et al. observed that for square-friendly applications one can beat the "RT-bound", extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a "weak" key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for "weak" keys. We show that any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, must be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC\\'13, CRYPTO\\'11) Hence, they can be understood as a general characterization of squared-friendly applications. While the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices."}],"ec_funded":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"1174","scopus_import":"1","author":[{"id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","full_name":"Skórski, Maciej","last_name":"Skórski","first_name":"Maciej"}],"publication_status":"published","date_created":"2018-12-11T11:50:32Z","department":[{"_id":"KrPi"}],"article_processing_charge":"No","alternative_title":["LIPIcs"],"title":"Lower bounds on key derivation for square-friendly applications","intvolume":" 66"},{"language":[{"iso":"eng"}],"conference":{"location":"Berkeley, CA, United States","end_date":"2017-01-11","name":"ITCS: Innovations in Theoretical Computer Science","start_date":"2017-01-09"},"has_accepted_license":"1","month":"01","oa_version":"Published Version","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"system","file_id":"5263","access_level":"open_access","relation":"main_file","file_name":"IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:44:37Z","checksum":"dbc94810be07c2fb1945d5c2a6130e6c","file_size":557769,"date_created":"2018-12-12T10:17:11Z"}],"type":"conference","date_published":"2017-01-01T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"publist_id":"6179","oa":1,"publication_identifier":{"issn":["18688969"]},"file_date_updated":"2020-07-14T12:44:37Z","quality_controlled":"1","page":"38:1-38-21","editor":[{"last_name":"Papadimitriou","first_name":"Christos","full_name":"Papadimitriou, Christos"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"full_name":"De Rezende, Susanna","first_name":"Susanna","last_name":"De Rezende"},{"last_name":"Nordstrom","first_name":"Jakob","full_name":"Nordstrom, Jakob"},{"last_name":"Vinyals","first_name":"Marc","full_name":"Vinyals, Marc"}],"scopus_import":1,"_id":"1175","intvolume":" 67","title":"Cumulative space in black-white pebbling and resolution","pubrep_id":"927","alternative_title":["LIPIcs"],"date_created":"2018-12-11T11:50:33Z","department":[{"_id":"KrPi"}],"publication_status":"published","ddc":["005","600"],"volume":67,"year":"2017","citation":{"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.","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","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.","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.","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."},"date_updated":"2021-01-12T06:48:51Z","abstract":[{"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.","lang":"eng"}],"day":"01","doi":"10.4230/LIPIcs.ITCS.2017.38"},{"month":"07","article_number":"7961977","oa_version":"Submitted Version","language":[{"iso":"eng"}],"conference":{"name":"EuroS&P: European Symposium on Security and Privacy","start_date":"2017-04-26","end_date":"2017-04-28","location":"Paris, France"},"date_published":"2017-07-03T00:00:00Z","type":"conference","oa":1,"publist_id":"6178","publication_identifier":{"isbn":["978-150905761-0"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","main_file_link":[{"url":"https://eprint.iacr.org/2016/759","open_access":"1"}],"author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","first_name":"Joel F","full_name":"Alwen, Joel F"},{"full_name":"Blocki, Jeremiah","first_name":"Jeremiah","last_name":"Blocki"}],"_id":"1176","scopus_import":"1","title":"Towards practical attacks on Argon2i and balloon hashing","publication_status":"published","article_processing_charge":"No","department":[{"_id":"KrPi"}],"date_created":"2018-12-11T11:50:33Z","quality_controlled":"1","publisher":"IEEE","isi":1,"external_id":{"isi":["000424197300011"]},"date_updated":"2023-09-20T11:22:25Z","citation":{"short":"J.F. Alwen, J. Blocki, in:, IEEE, 2017.","mla":"Alwen, Joel F., and Jeremiah Blocki. Towards Practical Attacks on Argon2i and Balloon Hashing. 7961977, IEEE, 2017, doi:10.1109/EuroSP.2017.47.","ista":"Alwen JF, Blocki J. 2017. Towards practical attacks on Argon2i and balloon hashing. EuroS&P: European Symposium on Security and Privacy, 7961977.","ama":"Alwen JF, Blocki J. Towards practical attacks on Argon2i and balloon hashing. In: IEEE; 2017. doi:10.1109/EuroSP.2017.47","apa":"Alwen, J. F., & Blocki, J. (2017). Towards practical attacks on Argon2i and balloon hashing. Presented at the EuroS&P: European Symposium on Security and Privacy, Paris, France: IEEE. https://doi.org/10.1109/EuroSP.2017.47","ieee":"J. F. Alwen and J. Blocki, “Towards practical attacks on Argon2i and balloon hashing,” presented at the EuroS&P: European Symposium on Security and Privacy, Paris, France, 2017.","chicago":"Alwen, Joel F, and Jeremiah Blocki. “Towards Practical Attacks on Argon2i and Balloon Hashing.” IEEE, 2017. https://doi.org/10.1109/EuroSP.2017.47."},"year":"2017","abstract":[{"text":"The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being considered by the IRTF (Internet Research Task Force) as a new de-facto standard for password hashing. An older version (Argon2i-A) of the same algorithm was chosen as the winner of the recent Password Hashing Competition. An important competitor to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs, Boneh and Schechter. A key security desiderata for any such algorithm is that evaluating it (even using a custom device) requires a large amount of memory amortized across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of theoretical attacks against Argon2i-A and BH. While these attacks yield large asymptotic reductions in the amount of memory, it was not, a priori, clear if (1) they can be extended to the newer Argon2i-B, (2) the attacks are effective on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3) if they can be effectively instantiated against any algorithm under realistic hardware constrains. In this work we answer all three of these questions in the affirmative for all three algorithms. This is also the first work to analyze the security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe asymptotic deficiencies in its security. Next we introduce several novel heuristics for improving the attack's concrete memory efficiency even when on-chip memory bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A, Argon2i-B and BH instances and measure the resulting memory consumption for various practical parameter ranges and for a variety of upperbounds on the amount of parallelism available to the attacker. Finally we describe, implement, and test a new heuristic for applying the Alwen-Blocki attack to functions employing a technique developed by Corrigan-Gibs et al. for improving concrete security of memory-hard functions. We analyze the collected data and show the effects various parameters have on the memory consumption of the attack. In particular, we can draw several interesting conclusions about the level of security provided by these functions. · For the Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must be instantiated with more than 10 passes on memory - beyond the \"paranoid\" parameter setting in the current IRTF proposal. · The technique of Corrigan-Gibs for improving security can also be overcome by the Alwen-Blocki attack under realistic hardware constraints. · On a positive note, both the asymptotic and concrete security of Argon2i-B seem to improve on that of Argon2i-A.","lang":"eng"}],"doi":"10.1109/EuroSP.2017.47","day":"03"},{"has_accepted_license":"1","oa_version":"Published Version","month":"06","language":[{"iso":"eng"}],"type":"dissertation","date_published":"2017-06-26T00:00:00Z","publication_identifier":{"issn":["2663-337X"]},"publist_id":"6810","oa":1,"file":[{"content_type":"application/pdf","file_name":"IST-2017-828-v1+3_2017_Rybar_thesis.pdf","date_updated":"2020-07-14T12:48:12Z","file_size":847400,"checksum":"ff8639ec4bded6186f44c7bd3ee26804","date_created":"2018-12-12T10:10:13Z","creator":"system","file_id":"4799","access_level":"open_access","relation":"main_file"},{"content_type":"application/zip","file_name":"2017_Thesis_Rybar_source.zip","date_updated":"2020-07-14T12:48:12Z","checksum":"3462101745ce8ad199c2d0f75dae4a7e","file_size":26054879,"date_created":"2019-04-05T08:24:11Z","creator":"dernst","file_id":"6202","access_level":"closed","relation":"source_file"}],"related_material":{"record":[{"id":"2082","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","id":"6196","status":"public"}]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","_id":"838","author":[{"last_name":"Rybar","first_name":"Michal","full_name":"Rybar, Michal","id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87"}],"department":[{"_id":"KrPi"}],"article_processing_charge":"No","date_created":"2018-12-11T11:48:46Z","publication_status":"published","pubrep_id":"828","title":"(The exact security of) Message authentication codes","alternative_title":["ISTA Thesis"],"page":"86","file_date_updated":"2020-07-14T12:48:12Z","publisher":"Institute of Science and Technology Austria","year":"2017","citation":{"mla":"Rybar, Michal. (The Exact Security of) Message Authentication Codes. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_828.","short":"M. Rybar, (The Exact Security of) Message Authentication Codes, Institute of Science and Technology Austria, 2017.","ista":"Rybar M. 2017. (The exact security of) Message authentication codes. Institute of Science and Technology Austria.","ama":"Rybar M. (The exact security of) Message authentication codes. 2017. doi:10.15479/AT:ISTA:th_828","apa":"Rybar, M. (2017). (The exact security of) Message authentication codes. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_828","ieee":"M. Rybar, “(The exact security of) Message authentication codes,” Institute of Science and Technology Austria, 2017.","chicago":"Rybar, Michal. “(The Exact Security of) Message Authentication Codes.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_828."},"date_updated":"2023-09-07T12:02:28Z","day":"26","degree_awarded":"PhD","doi":"10.15479/AT:ISTA:th_828","abstract":[{"text":"In this thesis we discuss the exact security of message authentications codes HMAC , NMAC , and PMAC . NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). PMAC is a block-cipher based mode of operation, which also happens to be the most famous fully parallel MAC. NMAC was introduced by Bellare, Canetti and Krawczyk Crypto’96, who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, under two assumptions. Unfortunately, for many instantiations of HMAC one of them has been found to be wrong. To restore the provable guarantees for NMAC , Bellare [Crypto’06] showed its security without this assumption. PMAC was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a pseudorandom permutation over n -bit strings, PMAC constitutes a provably secure variable input-length PRF. For adversaries making q queries, each of length at most ` (in n -bit blocks), and of total length σ ≤ q` , the original paper proves an upper bound on the distinguishing advantage of O ( σ 2 / 2 n ), while the currently best bound is O ( qσ/ 2 n ). In this work we show that this bound is tight by giving an attack with advantage Ω( q 2 `/ 2 n ). In the PMAC construction one initially XORs a mask to every message block, where the mask for the i th block is computed as τ i := γ i · L , where L is a (secret) random value, and γ i is the i -th codeword of the Gray code. Our attack applies more generally to any sequence of γ i ’s which contains a large coset of a subgroup of GF (2 n ). As for NMAC , our first contribution is a simpler and uniform proof: If f is an ε -secure PRF (against q queries) and a δ - non-adaptively secure PRF (against q queries), then NMAC f is an ( ε + `qδ )-secure PRF against q queries of length at most ` blocks each. We also show that this ε + `qδ bound is basically tight by constructing an f for which an attack with advantage `qδ exists. Moreover, we analyze the PRF-security of a modification of NMAC called NI by An and Bellare that avoids the constant rekeying on multi-block messages in NMAC and allows for an information-theoretic analysis. We carry out such an analysis, obtaining a tight `q 2 / 2 c bound for this step, improving over the trivial bound of ` 2 q 2 / 2 c . Finally, we investigate, if the security of PMAC can be further improved by using τ i ’s that are k -wise independent, for k > 1 (the original has k = 1). We observe that the security of PMAC will not increase in general if k = 2, and then prove that the security increases to O ( q 2 / 2 n ), if the k = 4. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether k = 3 is already sufficient to get this level of security is left as an open problem. Keywords: Message authentication codes, Pseudorandom functions, HMAC, PMAC. ","lang":"eng"}],"ddc":["000"]},{"doi":"10.4230/LIPIcs.ICALP.2017.39","day":"01","abstract":[{"lang":"eng","text":"De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over n-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping n-1 to n bit strings), can be distinguished from the uniform distribution with advantage epsilon by a circuit of size O( 2^n epsilon^2). We generalize this result, showing that a distribution which has less than k bits of min-entropy, can be distinguished from any distribution with k bits of delta-smooth min-entropy with advantage epsilon by a circuit of size O(2^k epsilon^2/delta^2). As a special case, this implies that any distribution with support at most 2^k (e.g., the output of a pseudoentropy generator mapping k to n bit strings) can be distinguished from any given distribution with min-entropy k+1 with advantage epsilon by a circuit of size O(2^k epsilon^2). Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions. "}],"date_updated":"2021-01-12T08:11:15Z","year":"2017","citation":{"mla":"Pietrzak, Krzysztof Z., and Maciej Skórski. Non Uniform Attacks against Pseudoentropy. Vol. 80, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.ICALP.2017.39.","short":"K.Z. Pietrzak, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ista":"Pietrzak KZ, Skórski M. 2017. Non uniform attacks against pseudoentropy. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 80, 39.","ama":"Pietrzak KZ, Skórski M. Non uniform attacks against pseudoentropy. In: Vol 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.ICALP.2017.39","apa":"Pietrzak, K. Z., & Skórski, M. (2017). Non uniform attacks against pseudoentropy (Vol. 80). Presented at the ICALP: International Colloquium on Automata, Languages, and Programming, Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2017.39","ieee":"K. Z. Pietrzak and M. Skórski, “Non uniform attacks against pseudoentropy,” presented at the ICALP: International Colloquium on Automata, Languages, and Programming, Warsaw, Poland, 2017, vol. 80.","chicago":"Pietrzak, Krzysztof Z, and Maciej Skórski. “Non Uniform Attacks against Pseudoentropy,” Vol. 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.ICALP.2017.39."},"volume":80,"ddc":["005"],"publication_status":"published","date_created":"2018-12-11T11:47:59Z","department":[{"_id":"KrPi"}],"alternative_title":["LIPIcs"],"title":"Non uniform attacks against pseudoentropy","pubrep_id":"893","intvolume":" 80","_id":"697","scopus_import":1,"author":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"},{"full_name":"Skórski, Maciej","last_name":"Skórski","first_name":"Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","ec_funded":1,"file_date_updated":"2020-07-14T12:47:46Z","publication_identifier":{"issn":["18688969"]},"oa":1,"publist_id":"7003","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2017-07-01T00:00:00Z","type":"conference","file":[{"relation":"main_file","access_level":"open_access","file_id":"4701","creator":"system","date_created":"2018-12-12T10:08:40Z","checksum":"e95618a001692f1af2d68f5fde43bc1f","file_size":601004,"date_updated":"2020-07-14T12:47:46Z","file_name":"IST-2017-893-v1+1_LIPIcs-ICALP-2017-39.pdf","content_type":"application/pdf"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","oa_version":"Published Version","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"month":"07","article_number":"39","has_accepted_license":"1","conference":{"start_date":"2017-07-10","name":"ICALP: International Colloquium on Automata, Languages, and Programming","end_date":"2017-07-14","location":"Warsaw, Poland"},"language":[{"iso":"eng"}]},{"ec_funded":1,"quality_controlled":"1","file_date_updated":"2020-07-14T12:47:49Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"710","scopus_import":1,"author":[{"full_name":"Obremski, Maciej","first_name":"Maciej","last_name":"Obremski"},{"last_name":"Skórski","first_name":"Maciej","full_name":"Skórski, Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"publication_status":"published","department":[{"_id":"KrPi"}],"date_created":"2018-12-11T11:48:04Z","pubrep_id":"888","alternative_title":["LIPIcs"],"title":"Renyi entropy estimation revisited","intvolume":" 81","volume":81,"ddc":["005","600"],"date_updated":"2021-01-12T08:11:50Z","year":"2017","citation":{"short":"M. Obremski, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Obremski, Maciej, and Maciej Skórski. Renyi Entropy Estimation Revisited. Vol. 81, 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.APPROX-RANDOM.2017.20.","ista":"Obremski M, Skórski M. 2017. Renyi entropy estimation revisited. 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, LIPIcs, vol. 81, 20.","ama":"Obremski M, Skórski M. Renyi entropy estimation revisited. In: Vol 81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.20","apa":"Obremski, M., & Skórski, M. (2017). Renyi entropy estimation revisited (Vol. 81). Presented at the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, Berkeley, USA: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20","ieee":"M. Obremski and M. Skórski, “Renyi entropy estimation revisited,” presented at the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, Berkeley, USA, 2017, vol. 81.","chicago":"Obremski, Maciej, and Maciej Skórski. “Renyi Entropy Estimation Revisited,” Vol. 81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20."},"doi":"10.4230/LIPIcs.APPROX-RANDOM.2017.20","day":"01","abstract":[{"lang":"eng","text":"We revisit the problem of estimating entropy of discrete distributions from independent samples, studied recently by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015), improving their upper and lower bounds on the necessary sample size n. For estimating Renyi entropy of order alpha, up to constant accuracy and error probability, we show the following * Upper bounds n = O(1) 2^{(1-1/alpha)H_alpha} for integer alpha>1, as the worst case over distributions with Renyi entropy equal to H_alpha. * Lower bounds n = Omega(1) K^{1-1/alpha} for any real alpha>1, with the constant being an inverse polynomial of the accuracy, as the worst case over all distributions on K elements. Our upper bounds essentially replace the alphabet size by a factor exponential in the entropy, which offers improvements especially in low or medium entropy regimes (interesting for example in anomaly detection). As for the lower bounds, our proof explicitly shows how the complexity depends on both alphabet and accuracy, partially solving the open problem posted in previous works. The argument for upper bounds derives a clean identity for the variance of falling-power sum of a multinomial distribution. Our approach for lower bounds utilizes convex optimization to find a distribution with possibly worse estimation performance, and may be of independent interest as a tool to work with Le Cam’s two point method. "}],"language":[{"iso":"eng"}],"conference":{"location":"Berkeley, USA","end_date":"2017-08-18","start_date":"2017-08-18","name":"20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX"},"has_accepted_license":"1","oa_version":"Published Version","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"month":"08","article_number":"20","file":[{"date_created":"2018-12-12T10:13:10Z","checksum":"89225c7dcec2c93838458c9102858985","file_size":604813,"date_updated":"2020-07-14T12:47:49Z","file_name":"IST-2017-888-v1+1_LIPIcs-APPROX-RANDOM-2017-20.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"4991","creator":"system"}],"status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2017-08-01T00:00:00Z","type":"conference","publication_identifier":{"issn":["18688969"]},"publist_id":"6979","oa":1},{"type":"conference","date_published":"2017-11-18T00:00:00Z","publist_id":"7257","oa":1,"publication_identifier":{"isbn":["978-331970696-2"]},"related_material":{"record":[{"status":"public","id":"83","relation":"dissertation_contains"}]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2017/893.pdf"}],"month":"11","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"oa_version":"Submitted Version","language":[{"iso":"eng"}],"conference":{"start_date":"2017-12-03","name":"ASIACRYPT: Theory and Applications of Cryptology and Information Security","end_date":"2017-12-07","location":"Hong Kong, China"},"year":"2017","citation":{"ista":"Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. 2017. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. ASIACRYPT: Theory and Applications of Cryptology and Information Security, LNCS, vol. 10625, 357–379.","mla":"Abusalah, Hamza M., et al. Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space. Vol. 10625, Springer, 2017, pp. 357–79, doi:10.1007/978-3-319-70697-9_13.","short":"H.M. Abusalah, J.F. Alwen, B. Cohen, D. Khilko, K.Z. Pietrzak, L. Reyzin, in:, Springer, 2017, pp. 357–379.","ieee":"H. M. Abusalah, J. F. Alwen, B. Cohen, D. Khilko, K. Z. Pietrzak, and L. Reyzin, “Beyond Hellman’s time-memory trade-offs with applications to proofs of space,” presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017, vol. 10625, pp. 357–379.","chicago":"Abusalah, Hamza M, Joel F Alwen, Bram Cohen, Danylo Khilko, Krzysztof Z Pietrzak, and Leonid Reyzin. “Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space,” 10625:357–79. Springer, 2017. https://doi.org/10.1007/978-3-319-70697-9_13.","apa":"Abusalah, H. M., Alwen, J. F., Cohen, B., Khilko, D., Pietrzak, K. Z., & Reyzin, L. (2017). Beyond Hellman’s time-memory trade-offs with applications to proofs of space (Vol. 10625, pp. 357–379). Presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China: Springer. https://doi.org/10.1007/978-3-319-70697-9_13","ama":"Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. In: Vol 10625. Springer; 2017:357-379. doi:10.1007/978-3-319-70697-9_13"},"date_updated":"2023-09-07T12:30:22Z","abstract":[{"lang":"eng","text":"Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don’t give meaningful security guarantees due to existing time-memory trade-offs. In particular, Hellman showed that any permutation over a domain of size N can be inverted in time T by an algorithm that is given S bits of auxiliary information whenever (Formula presented). For functions Hellman gives a weaker attack with S2· T≈ N2 (e.g., S= T≈ N2/3). To prove lower bounds, one considers an adversary who has access to an oracle f: [ N] → [N] and can make T oracle queries. The best known lower bound is S· T∈ Ω(N) and holds for random functions and permutations. We construct functions that provably require more time and/or space to invert. Specifically, for any constant k we construct a function [N] → [N] that cannot be inverted unless Sk· T∈ Ω(Nk) (in particular, S= T≈ (Formula presented). Our construction does not contradict Hellman’s time-memory trade-off, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in N, which is sufficient for the PoS application. Our simplest construction is built from a random function oracle g: [N] × [N] → [ N] and a random permutation oracle f: [N] → N] and is defined as h(x) = g(x, x′) where f(x) = π(f(x′)) with π being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets S bits of auxiliary information, makes at most T oracle queries, and inverts h on an ϵ fraction of outputs must satisfy S2· T∈ Ω(ϵ2N2)."}],"day":"18","doi":"10.1007/978-3-319-70697-9_13","volume":10625,"author":[{"full_name":"Abusalah, Hamza M","first_name":"Hamza M","last_name":"Abusalah","id":"40297222-F248-11E8-B48F-1D18A9856A87"},{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F","last_name":"Alwen","full_name":"Alwen, Joel F"},{"last_name":"Cohen","first_name":"Bram","full_name":"Cohen, Bram"},{"first_name":"Danylo","last_name":"Khilko","full_name":"Khilko, Danylo"},{"first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Reyzin","first_name":"Leonid","full_name":"Reyzin, Leonid"}],"scopus_import":1,"_id":"559","intvolume":" 10625","alternative_title":["LNCS"],"title":"Beyond Hellman’s time-memory trade-offs with applications to proofs of space","date_created":"2018-12-11T11:47:10Z","department":[{"_id":"KrPi"}],"publication_status":"published","ec_funded":1,"quality_controlled":"1","page":"357 - 379","publisher":"Springer"}]