[{"publisher":"Springer","status":"public","intvolume":"     10677","department":[{"_id":"KrPi"}],"quality_controlled":"1","page":"56 - 81","date_created":"2018-12-11T11:47:27Z","month":"11","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"doi":"10.1007/978-3-319-70500-2_3","language":[{"iso":"eng"}],"title":"Position based cryptography and multiparty communication complexity","conference":{"end_date":"2017-11-15","start_date":"2017-11-12","name":"TCC: Theory of Cryptography Conference","location":"Baltimore, MD, United States"},"citation":{"apa":"Brody, J., Dziembowski, S., Faust, S., &#38; Pietrzak, K. Z. (2017). Position based cryptography and multiparty communication complexity. In Y. Kalai &#38; L. Reyzin (Eds.) (Vol. 10677, pp. 56–81). Presented at the TCC: Theory of Cryptography Conference, Baltimore, MD, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-319-70500-2_3\">https://doi.org/10.1007/978-3-319-70500-2_3</a>","ama":"Brody J, Dziembowski S, Faust S, Pietrzak KZ. Position based cryptography and multiparty communication complexity. In: Kalai Y, Reyzin L, eds. Vol 10677. Springer; 2017:56-81. doi:<a href=\"https://doi.org/10.1007/978-3-319-70500-2_3\">10.1007/978-3-319-70500-2_3</a>","short":"J. Brody, S. Dziembowski, S. Faust, K.Z. Pietrzak, in:, Y. Kalai, L. Reyzin (Eds.), Springer, 2017, pp. 56–81.","mla":"Brody, Joshua, et al. <i>Position Based Cryptography and Multiparty Communication Complexity</i>. Edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer, 2017, pp. 56–81, doi:<a href=\"https://doi.org/10.1007/978-3-319-70500-2_3\">10.1007/978-3-319-70500-2_3</a>.","ista":"Brody J, Dziembowski S, Faust S, Pietrzak KZ. 2017. Position based cryptography and multiparty communication complexity. TCC: Theory of Cryptography Conference, LNCS, vol. 10677, 56–81.","ieee":"J. Brody, S. Dziembowski, S. Faust, and K. Z. Pietrzak, “Position based cryptography and multiparty communication complexity,” presented at the TCC: Theory of Cryptography Conference, Baltimore, MD, United States, 2017, vol. 10677, pp. 56–81.","chicago":"Brody, Joshua, Stefan Dziembowski, Sebastian Faust, and Krzysztof Z Pietrzak. “Position Based Cryptography and Multiparty Communication Complexity.” edited by Yael Kalai and Leonid Reyzin, 10677:56–81. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-70500-2_3\">https://doi.org/10.1007/978-3-319-70500-2_3</a>."},"ec_funded":1,"author":[{"full_name":"Brody, Joshua","first_name":"Joshua","last_name":"Brody"},{"last_name":"Dziembowski","first_name":"Stefan","full_name":"Dziembowski, Stefan"},{"full_name":"Faust, Sebastian","first_name":"Sebastian","last_name":"Faust"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"type":"conference","alternative_title":["LNCS"],"day":"05","main_file_link":[{"url":"https://eprint.iacr.org/2016/536","open_access":"1"}],"oa":1,"publication_status":"published","volume":10677,"_id":"605","date_published":"2017-11-05T00:00:00Z","abstract":[{"text":"Position based cryptography (PBC), proposed in the seminal work of Chandran, Goyal, Moriarty, and Ostrovsky (SIAM J. Computing, 2014), aims at constructing cryptographic schemes in which the identity of the user is his geographic position. Chandran et al. construct PBC schemes for secure positioning and position-based key agreement in the bounded-storage model (Maurer, J. Cryptology, 1992). Apart from bounded memory, their security proofs need a strong additional restriction on the power of the adversary: he cannot compute joint functions of his inputs. Removing this assumption is left as an open problem. We show that an answer to this question would resolve a long standing open problem in multiparty communication complexity: finding a function that is hard to compute with low communication complexity in the simultaneous message model, but easy to compute in the fully adaptive model. On a more positive side: we also show some implications in the other direction, i.e.: we prove that lower bounds on the communication complexity of certain multiparty problems imply existence of PBC primitives. Using this result we then show two attractive ways to “bypass” our hardness result: the first uses the random oracle model, the second weakens the locality requirement in the bounded-storage model to online computability. The random oracle construction is arguably one of the simplest proposed so far in this area. Our results indicate that constructing improved provably secure protocols for PBC requires a better understanding of multiparty communication complexity. This is yet another example where negative results in one area (in our case: lower bounds in multiparty communication complexity) can be used to construct secure cryptographic schemes.","lang":"eng"}],"publication_identifier":{"isbn":["978-331970499-9"]},"scopus_import":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T08:05:53Z","editor":[{"full_name":"Kalai, Yael","first_name":"Yael","last_name":"Kalai"},{"first_name":"Leonid","full_name":"Reyzin, Leonid","last_name":"Reyzin"}],"oa_version":"Submitted Version","year":"2017","publist_id":"7200"},{"scopus_import":1,"date_updated":"2021-01-12T08:06:04Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["978-331970499-9"]},"publist_id":"7196","year":"2017","oa_version":"Submitted Version","editor":[{"full_name":"Kalai, Yael","first_name":"Yael","last_name":"Kalai"},{"last_name":"Reyzin","full_name":"Reyzin, Leonid","first_name":"Leonid"}],"volume":10677,"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2017/945"}],"oa":1,"date_published":"2017-11-05T00:00:00Z","_id":"609","abstract":[{"text":"Several cryptographic schemes and applications are based on functions that are both reasonably efficient to compute and moderately hard to invert, including client puzzles for Denial-of-Service protection, password protection via salted hashes, or recent proof-of-work blockchain systems. Despite their wide use, a definition of this concept has not yet been distilled and formalized explicitly. Instead, either the applications are proven directly based on the assumptions underlying the function, or some property of the function is proven, but the security of the application is argued only informally. The goal of this work is to provide a (universal) definition that decouples the efforts of designing new moderately hard functions and of building protocols based on them, serving as an interface between the two. On a technical level, beyond the mentioned definitions, we instantiate the model for four different notions of hardness. We extend the work of Alwen and Serbinenko (STOC 2015) by providing a general tool for proving security for the first notion of memory-hard functions that allows for provably secure applications. The tool allows us to recover all of the graph-theoretic techniques developed for proving security under the older, non-composable, notion of security used by Alwen and Serbinenko. As an application of our definition of moderately hard functions, we prove the security of two different schemes for proofs of effort (PoE). We also formalize and instantiate the concept of a non-interactive proof of effort (niPoE), in which the proof is not bound to a particular communication context but rather any bit-string chosen by the prover.","lang":"eng"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-70500-2_17","day":"05","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F","first_name":"Joel F"},{"first_name":"Björn","full_name":"Tackmann, Björn","last_name":"Tackmann"}],"type":"conference","alternative_title":["LNCS"],"citation":{"ama":"Alwen JF, Tackmann B. Moderately hard functions: Definition, instantiations, and applications. In: Kalai Y, Reyzin L, eds. Vol 10677. Springer; 2017:493-526. doi:<a href=\"https://doi.org/10.1007/978-3-319-70500-2_17\">10.1007/978-3-319-70500-2_17</a>","apa":"Alwen, J. F., &#38; Tackmann, B. (2017). Moderately hard functions: Definition, instantiations, and applications. In Y. Kalai &#38; L. Reyzin (Eds.) (Vol. 10677, pp. 493–526). Presented at the TCC: Theory of Cryptography, Baltimore, MD, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-319-70500-2_17\">https://doi.org/10.1007/978-3-319-70500-2_17</a>","short":"J.F. Alwen, B. Tackmann, in:, Y. Kalai, L. Reyzin (Eds.), Springer, 2017, pp. 493–526.","mla":"Alwen, Joel F., and Björn Tackmann. <i>Moderately Hard Functions: Definition, Instantiations, and Applications</i>. Edited by Yael Kalai and Leonid Reyzin, vol. 10677, Springer, 2017, pp. 493–526, doi:<a href=\"https://doi.org/10.1007/978-3-319-70500-2_17\">10.1007/978-3-319-70500-2_17</a>.","chicago":"Alwen, Joel F, and Björn Tackmann. “Moderately Hard Functions: Definition, Instantiations, and Applications.” edited by Yael Kalai and Leonid Reyzin, 10677:493–526. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-70500-2_17\">https://doi.org/10.1007/978-3-319-70500-2_17</a>.","ista":"Alwen JF, Tackmann B. 2017. Moderately hard functions: Definition, instantiations, and applications. TCC: Theory of Cryptography, LNCS, vol. 10677, 493–526.","ieee":"J. F. Alwen and B. Tackmann, “Moderately hard functions: Definition, instantiations, and applications,” presented at the TCC: Theory of Cryptography, Baltimore, MD, United States, 2017, vol. 10677, pp. 493–526."},"title":"Moderately hard functions: Definition, instantiations, and applications","conference":{"location":"Baltimore, MD, United States","start_date":"2017-11-12","end_date":"2017-11-15","name":"TCC: Theory of Cryptography"},"department":[{"_id":"KrPi"}],"quality_controlled":"1","intvolume":"     10677","status":"public","publisher":"Springer","month":"11","date_created":"2018-12-11T11:47:28Z","page":"493 - 526"},{"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"838","status":"public"}]},"ddc":["000"],"doi":"10.13154/TOSC.V2016.I2.145-161","language":[{"iso":"eng"}],"title":"The exact security of PMAC","citation":{"ama":"Gazi P, Pietrzak KZ, Rybar M. The exact security of PMAC. <i>IACR Transactions on Symmetric Cryptology</i>. 2017;2016(2):145-161. doi:<a href=\"https://doi.org/10.13154/TOSC.V2016.I2.145-161\">10.13154/TOSC.V2016.I2.145-161</a>","apa":"Gazi, P., Pietrzak, K. Z., &#38; Rybar, M. (2017). The exact security of PMAC. <i>IACR Transactions on Symmetric Cryptology</i>. Ruhr University Bochum. <a href=\"https://doi.org/10.13154/TOSC.V2016.I2.145-161\">https://doi.org/10.13154/TOSC.V2016.I2.145-161</a>","short":"P. Gazi, K.Z. Pietrzak, M. Rybar, IACR Transactions on Symmetric Cryptology 2016 (2017) 145–161.","mla":"Gazi, Peter, et al. “The Exact Security of PMAC.” <i>IACR Transactions on Symmetric Cryptology</i>, vol. 2016, no. 2, Ruhr University Bochum, 2017, pp. 145–61, doi:<a href=\"https://doi.org/10.13154/TOSC.V2016.I2.145-161\">10.13154/TOSC.V2016.I2.145-161</a>.","chicago":"Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact Security of PMAC.” <i>IACR Transactions on Symmetric Cryptology</i>. Ruhr University Bochum, 2017. <a href=\"https://doi.org/10.13154/TOSC.V2016.I2.145-161\">https://doi.org/10.13154/TOSC.V2016.I2.145-161</a>.","ieee":"P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact security of PMAC,” <i>IACR Transactions on Symmetric Cryptology</i>, vol. 2016, no. 2. Ruhr University Bochum, pp. 145–161, 2017.","ista":"Gazi P, Pietrzak KZ, Rybar M. 2017. The exact security of PMAC. IACR Transactions on Symmetric Cryptology. 2016(2), 145–161."},"ec_funded":1,"type":"journal_article","author":[{"id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","last_name":"Gazi","first_name":"Peter","full_name":"Gazi, Peter"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Rybar, Michal","first_name":"Michal","last_name":"Rybar","id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87"}],"day":"03","publisher":"Ruhr University Bochum","intvolume":"      2016","status":"public","publication":"IACR Transactions on Symmetric Cryptology","quality_controlled":"1","department":[{"_id":"KrPi"}],"page":"145-161","date_created":"2019-04-04T13:48:23Z","month":"02","publication_identifier":{"eissn":["2519-173X"]},"date_updated":"2023-09-07T12:02:27Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","oa_version":"Published Version","year":"2017","oa":1,"publication_status":"published","license":"https://creativecommons.org/licenses/by/4.0/","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"volume":2016,"file_date_updated":"2020-07-14T12:47:24Z","issue":"2","date_published":"2017-02-03T00:00:00Z","_id":"6196","abstract":[{"lang":"eng","text":"PMAC is a simple and parallel block-cipher mode of operation, which was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random permutation over n-bit strings, PMAC constitutes a provably secure variable input-length (pseudo)random function. For adversaries making q queries, each of length at most l (in n-bit blocks), and of total length σ ≤ ql, the original paper proves an upper bound on the distinguishing advantage of  Ο(σ2/2n), while the currently best bound is  Ο (qσ/2n).In this work we show that this bound is tight by giving an attack with advantage Ω (q2l/2n). In the PMAC construction one initially XORs a mask to every message block, where the mask for the ith 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(2n). We then investigate if the security of PMAC can be further improved by using τi’s that are k-wise independent, for k > 1 (the original distribution is only 1-wise independent). We observe that the security of PMAC will not increase in general, even if the masks are chosen from a 2-wise independent distribution, and then prove that the security increases to O(q<2/2n), if the τi are 4-wise independent. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether 3-wise independence is already sufficient to get this level of security is left as an open problem."}],"file":[{"file_size":597335,"creator":"dernst","file_name":"2017_IACR_Gazi.pdf","access_level":"open_access","date_updated":"2020-07-14T12:47:24Z","checksum":"f23161d685dd957ae8d7274132999684","relation":"main_file","file_id":"6197","content_type":"application/pdf","date_created":"2019-04-04T13:53:58Z"}]},{"ec_funded":1,"citation":{"apa":"Alwen, J. F., Chen, B., Pietrzak, K. Z., Reyzin, L., &#38; Tessaro, S. (2017). Scrypt is maximally memory hard. In J.-S. Coron &#38; J. Buus Nielsen (Eds.) (Vol. 10212, pp. 33–62). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France: Springer. <a href=\"https://doi.org/10.1007/978-3-319-56617-7_2\">https://doi.org/10.1007/978-3-319-56617-7_2</a>","ama":"Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. Scrypt is maximally memory hard. In: Coron J-S, Buus Nielsen J, eds. Vol 10212. Springer; 2017:33-62. doi:<a href=\"https://doi.org/10.1007/978-3-319-56617-7_2\">10.1007/978-3-319-56617-7_2</a>","short":"J.F. Alwen, B. Chen, K.Z. Pietrzak, L. Reyzin, S. Tessaro, in:, J.-S. Coron, J. Buus Nielsen (Eds.), Springer, 2017, pp. 33–62.","mla":"Alwen, Joel F., et al. <i>Scrypt Is Maximally Memory Hard</i>. Edited by Jean-Sébastien Coron and Jesper Buus Nielsen, vol. 10212, Springer, 2017, pp. 33–62, doi:<a href=\"https://doi.org/10.1007/978-3-319-56617-7_2\">10.1007/978-3-319-56617-7_2</a>.","ieee":"J. F. Alwen, B. Chen, K. Z. Pietrzak, L. Reyzin, and S. Tessaro, “Scrypt is maximally memory hard,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France, 2017, vol. 10212, pp. 33–62.","ista":"Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. 2017. Scrypt is maximally memory hard. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 10212, 33–62.","chicago":"Alwen, Joel F, Binchi Chen, Krzysztof Z Pietrzak, Leonid Reyzin, and Stefano Tessaro. “Scrypt Is Maximally Memory Hard.” edited by Jean-Sébastien Coron and Jesper Buus Nielsen, 10212:33–62. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-56617-7_2\">https://doi.org/10.1007/978-3-319-56617-7_2</a>."},"conference":{"location":"Paris, France","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2017-04-30","end_date":"2017-05-04"},"title":"Scrypt is maximally memory hard","day":"01","alternative_title":["LNCS"],"author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"full_name":"Chen, Binchi","first_name":"Binchi","last_name":"Chen"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"last_name":"Reyzin","first_name":"Leonid","full_name":"Reyzin, Leonid"},{"last_name":"Tessaro","first_name":"Stefano","full_name":"Tessaro, Stefano"}],"type":"conference","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-56617-7_2","page":"33 - 62","month":"01","date_created":"2018-12-11T11:47:37Z","publisher":"Springer","department":[{"_id":"KrPi"}],"quality_controlled":"1","status":"public","intvolume":"     10212","editor":[{"last_name":"Coron","full_name":"Coron, Jean-Sébastien","first_name":"Jean-Sébastien"},{"last_name":"Buus Nielsen","first_name":"Jesper","full_name":"Buus Nielsen, Jesper"}],"publist_id":"7154","oa_version":"Submitted Version","year":"2017","date_updated":"2021-01-12T08:07:10Z","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"publication_identifier":{"isbn":["978-331956616-0"]},"date_published":"2017-01-01T00:00:00Z","_id":"635","abstract":[{"text":"Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is dominated by memory cost. As memory, unlike computation, costs about the same across different platforms, MHFs cannot be evaluated at significantly lower cost on dedicated hardware like ASICs. MHFs have found widespread applications including password hashing, key derivation, and proofs-of-work. This paper focuses on scrypt, a simple candidate MHF designed by Percival, and described in RFC 7914. It has been used within a number of cryptocurrencies (e.g., Litecoin and Dogecoin) and has been an inspiration for Argon2d, one of the winners of the recent password-hashing competition. Despite its popularity, no rigorous lower bounds on its memory complexity are known. We prove that scrypt is optimally memory-hard, i.e., its cumulative memory complexity (cmc) in the parallel random oracle model is Ω(n2w), where w and n are the output length and number of invocations of the underlying hash function, respectively. High cmc is a strong security target for MHFs introduced by Alwen and Serbinenko (STOC’15) which implies high memory cost even for adversaries who can amortize the cost over many evaluations and evaluate the underlying hash functions many times in parallel. Our proof is the first showing optimal memory-hardness for any MHF. Our result improves both quantitatively and qualitatively upon the recent work by Alwen et al. (EUROCRYPT’16) who proved a weaker lower bound of Ω(n2w/ log2 n) for a restricted class of adversaries.","lang":"eng"}],"publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/989"}],"volume":10212},{"volume":10401,"main_file_link":[{"url":"https://eprint.iacr.org/2017/515","open_access":"1"}],"oa":1,"publication_status":"published","_id":"637","date_published":"2017-01-01T00:00:00Z","abstract":[{"lang":"eng","text":"For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m ≪ n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs."}],"publication_identifier":{"isbn":["978-331963687-0"]},"scopus_import":1,"date_updated":"2023-09-07T13:32:11Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","year":"2017","oa_version":"Submitted Version","publist_id":"7151","editor":[{"last_name":"Katz","first_name":"Jonathan","full_name":"Katz, Jonathan"},{"last_name":"Shacham","first_name":"Hovav","full_name":"Shacham, Hovav"}],"intvolume":"     10401","status":"public","department":[{"_id":"KrPi"}],"quality_controlled":"1","publisher":"Springer","date_created":"2018-12-11T11:47:38Z","month":"01","page":"133 - 163","doi":"10.1007/978-3-319-63688-7_5","language":[{"iso":"eng"}],"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"10035","status":"public"}]},"author":[{"last_name":"Jafargholi","first_name":"Zahra","full_name":"Jafargholi, Zahra"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein"},{"last_name":"Komargodski","full_name":"Komargodski, Ilan","first_name":"Ilan"},{"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"}],"type":"conference","alternative_title":["LNCS"],"day":"01","title":"Be adaptive avoid overcommitting","conference":{"end_date":"2017-07-24","start_date":"2017-07-20","name":"CRYPTO: Cryptology","location":"Santa Barbara, CA, United States"},"citation":{"chicago":"Jafargholi, Zahra, Chethan Kamath Hosdurg, Karen Klein, Ilan Komargodski, Krzysztof Z Pietrzak, and Daniel Wichs. “Be Adaptive Avoid Overcommitting.” edited by Jonathan Katz and Hovav Shacham, 10401:133–63. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">https://doi.org/10.1007/978-3-319-63688-7_5</a>.","ista":"Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. 2017. Be adaptive avoid overcommitting. CRYPTO: Cryptology, LNCS, vol. 10401, 133–163.","ieee":"Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K. Z. Pietrzak, and D. Wichs, “Be adaptive avoid overcommitting,” presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States, 2017, vol. 10401, pp. 133–163.","mla":"Jafargholi, Zahra, et al. <i>Be Adaptive Avoid Overcommitting</i>. Edited by Jonathan Katz and Hovav Shacham, vol. 10401, Springer, 2017, pp. 133–63, doi:<a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">10.1007/978-3-319-63688-7_5</a>.","short":"Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K.Z. Pietrzak, D. Wichs, in:, J. Katz, H. Shacham (Eds.), Springer, 2017, pp. 133–163.","ama":"Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. Be adaptive avoid overcommitting. In: Katz J, Shacham H, eds. Vol 10401. Springer; 2017:133-163. doi:<a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">10.1007/978-3-319-63688-7_5</a>","apa":"Jafargholi, Z., Kamath Hosdurg, C., Klein, K., Komargodski, I., Pietrzak, K. Z., &#38; Wichs, D. (2017). Be adaptive avoid overcommitting. In J. Katz &#38; H. Shacham (Eds.) (Vol. 10401, pp. 133–163). Presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">https://doi.org/10.1007/978-3-319-63688-7_5</a>"},"ec_funded":1},{"page":"3 - 32","date_created":"2018-12-11T11:47:39Z","month":"04","publisher":"Springer","status":"public","intvolume":"     10212","quality_controlled":"1","department":[{"_id":"KrPi"}],"conference":{"start_date":"2017-04-30","end_date":"2017-05-04","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","location":"Paris, France"},"title":"Depth-robust graphs and their cumulative memory complexity","ec_funded":1,"citation":{"ieee":"J. F. Alwen, J. Blocki, and K. Z. Pietrzak, “Depth-robust graphs and their cumulative memory complexity,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France, 2017, vol. 10212, pp. 3–32.","ista":"Alwen JF, Blocki J, Pietrzak KZ. 2017. Depth-robust graphs and their cumulative memory complexity. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 10212, 3–32.","chicago":"Alwen, Joel F, Jeremiah Blocki, and Krzysztof Z Pietrzak. “Depth-Robust Graphs and Their Cumulative Memory Complexity.” edited by Jean-Sébastien Coron and Jesper Buus Nielsen, 10212:3–32. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-56617-7_1\">https://doi.org/10.1007/978-3-319-56617-7_1</a>.","mla":"Alwen, Joel F., et al. <i>Depth-Robust Graphs and Their Cumulative Memory Complexity</i>. Edited by Jean-Sébastien Coron and Jesper Buus Nielsen, vol. 10212, Springer, 2017, pp. 3–32, doi:<a href=\"https://doi.org/10.1007/978-3-319-56617-7_1\">10.1007/978-3-319-56617-7_1</a>.","short":"J.F. Alwen, J. Blocki, K.Z. Pietrzak, in:, J.-S. Coron, J. Buus Nielsen (Eds.), Springer, 2017, pp. 3–32.","apa":"Alwen, J. F., Blocki, J., &#38; Pietrzak, K. Z. (2017). Depth-robust graphs and their cumulative memory complexity. In J.-S. Coron &#38; J. Buus Nielsen (Eds.) (Vol. 10212, pp. 3–32). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Paris, France: Springer. <a href=\"https://doi.org/10.1007/978-3-319-56617-7_1\">https://doi.org/10.1007/978-3-319-56617-7_1</a>","ama":"Alwen JF, Blocki J, Pietrzak KZ. Depth-robust graphs and their cumulative memory complexity. In: Coron J-S, Buus Nielsen J, eds. Vol 10212. Springer; 2017:3-32. doi:<a href=\"https://doi.org/10.1007/978-3-319-56617-7_1\">10.1007/978-3-319-56617-7_1</a>"},"alternative_title":["LNCS"],"type":"conference","author":[{"last_name":"Alwen","first_name":"Joel F","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Blocki, Jeremiah","first_name":"Jeremiah","last_name":"Blocki"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak"}],"day":"01","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"doi":"10.1007/978-3-319-56617-7_1","language":[{"iso":"eng"}],"date_published":"2017-04-01T00:00:00Z","_id":"640","abstract":[{"lang":"eng","text":"Data-independent Memory Hard Functions (iMHFS) are finding a growing number of applications in security; especially in the domain of password hashing. An important property of a concrete iMHF is specified by fixing a directed acyclic graph (DAG) Gn on n nodes. The quality of that iMHF is then captured by the following two pebbling complexities of Gn: – The parallel cumulative pebbling complexity Π∥cc(Gn) must be as high as possible (to ensure that the amortized cost of computing the function on dedicated hardware is dominated by the cost of memory). – The sequential space-time pebbling complexity Πst(Gn) should be as close as possible to Π∥cc(Gn) (to ensure that using many cores in parallel and amortizing over many instances does not give much of an advantage). In this paper we construct a family of DAGs with best possible parameters in an asymptotic sense, i.e., where Π∥cc(Gn) = Ω(n2/ log(n)) (which matches a known upper bound) and Πst(Gn) is within a constant factor of Π∥cc(Gn). Our analysis relies on a new connection between the pebbling complexity of a DAG and its depth-robustness (DR) – a well studied combinatorial property. We show that high DR is sufficient for high Π∥cc. Alwen and Blocki (CRYPTO’16) showed that high DR is necessary and so, together, these results fully characterize DAGs with high Π∥cc in terms of DR. Complementing these results, we provide new upper and lower bounds on the Π∥cc of several important candidate iMHFs from the literature. We give the first lower bounds on the memory hardness of the Catena and Balloon Hashing functions in a parallel model of computation and we give the first lower bounds of any kind for (a version) of Argon2i. Finally we describe a new class of pebbling attacks improving on those of Alwen and Blocki (CRYPTO’16). By instantiating these attacks we upperbound the Π∥cc of the Password Hashing Competition winner Argon2i and one of the Balloon Hashing functions by O (n1.71). We also show an upper bound of O(n1.625) for the Catena functions and the two remaining Balloon Hashing functions."}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/875"}],"oa":1,"publication_status":"published","volume":10212,"editor":[{"full_name":"Coron, Jean-Sébastien","first_name":"Jean-Sébastien","last_name":"Coron"},{"last_name":"Buus Nielsen","full_name":"Buus Nielsen, Jesper","first_name":"Jesper"}],"oa_version":"Submitted Version","year":"2017","publist_id":"7148","publication_identifier":{"isbn":["978-331956616-0"]},"date_updated":"2021-01-12T08:07:22Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1},{"date_created":"2018-12-11T11:47:42Z","month":"04","page":"600 - 613","intvolume":"     10185","status":"public","quality_controlled":"1","department":[{"_id":"KrPi"}],"publisher":"Springer","alternative_title":["LNCS"],"author":[{"full_name":"Skórski, Maciej","first_name":"Maciej","last_name":"Skórski","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"type":"conference","day":"01","conference":{"end_date":"2017-04-22","start_date":"2017-04-20","name":"TAMC: Theory and Applications of Models of Computation","location":"Bern, Switzerland"},"title":"On the complexity of breaking pseudoentropy","citation":{"short":"M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 600–613.","ama":"Skórski M. On the complexity of breaking pseudoentropy. In: Jäger G, Steila S, eds. Vol 10185. Springer; 2017:600-613. doi:<a href=\"https://doi.org/10.1007/978-3-319-55911-7_43\">10.1007/978-3-319-55911-7_43</a>","apa":"Skórski, M. (2017). On the complexity of breaking pseudoentropy. In G. Jäger &#38; S. Steila (Eds.) (Vol. 10185, pp. 600–613). Presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland: Springer. <a href=\"https://doi.org/10.1007/978-3-319-55911-7_43\">https://doi.org/10.1007/978-3-319-55911-7_43</a>","chicago":"Skórski, Maciej. “On the Complexity of Breaking Pseudoentropy.” edited by Gerhard Jäger and Silvia Steila, 10185:600–613. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-55911-7_43\">https://doi.org/10.1007/978-3-319-55911-7_43</a>.","ista":"Skórski M. 2017. On the complexity of breaking pseudoentropy. TAMC: Theory and Applications of Models of Computation, LNCS, vol. 10185, 600–613.","ieee":"M. Skórski, “On the complexity of breaking pseudoentropy,” presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland, 2017, vol. 10185, pp. 600–613.","mla":"Skórski, Maciej. <i>On the Complexity of Breaking Pseudoentropy</i>. Edited by Gerhard Jäger and Silvia Steila, vol. 10185, Springer, 2017, pp. 600–13, doi:<a href=\"https://doi.org/10.1007/978-3-319-55911-7_43\">10.1007/978-3-319-55911-7_43</a>."},"doi":"10.1007/978-3-319-55911-7_43","language":[{"iso":"eng"}],"date_published":"2017-04-01T00:00:00Z","_id":"648","abstract":[{"lang":"eng","text":"Pseudoentropy has found a lot of important applications to cryptography and complexity theory. In this paper we focus on the foundational problem that has not been investigated so far, namely by how much pseudoentropy (the amount seen by computationally bounded attackers) differs from its information-theoretic counterpart (seen by unbounded observers), given certain limits on attacker’s computational power? We provide the following answer for HILL pseudoentropy, which exhibits a threshold behavior around the size exponential in the entropy amount:– If the attacker size (s) and advantage () satisfy s (formula presented) where k is the claimed amount of pseudoentropy, then the pseudoentropy boils down to the information-theoretic smooth entropy. – If s (formula presented) then pseudoentropy could be arbitrarily bigger than the information-theoretic smooth entropy. Besides answering the posted question, we show an elegant application of our result to the complexity theory, namely that it implies the clas-sical result on the existence of functions hard to approximate (due to Pippenger). In our approach we utilize non-constructive techniques: the duality of linear programming and the probabilistic method."}],"volume":10185,"oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2016/1186.pdf","open_access":"1"}],"publication_status":"published","year":"2017","oa_version":"Submitted Version","publist_id":"7125","editor":[{"last_name":"Jäger","full_name":"Jäger, Gerhard","first_name":"Gerhard"},{"last_name":"Steila","first_name":"Silvia","full_name":"Steila, Silvia"}],"publication_identifier":{"isbn":["978-331955910-0"]},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T08:07:39Z","scopus_import":1},{"oa_version":"Submitted Version","year":"2017","publist_id":"7119","editor":[{"full_name":"Jäger, Gerhard","first_name":"Gerhard","last_name":"Jäger"},{"last_name":"Steila","full_name":"Steila, Silvia","first_name":"Silvia"}],"publication_identifier":{"issn":["03029743"]},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T08:07:46Z","scopus_import":1,"_id":"650","abstract":[{"lang":"eng","text":"In this work we present a short and unified proof for the Strong and Weak Regularity Lemma, based on the cryptographic tech-nique called low-complexity approximations. In short, both problems reduce to a task of finding constructively an approximation for a certain target function under a class of distinguishers (test functions), where dis-tinguishers are combinations of simple rectangle-indicators. In our case these approximations can be learned by a simple iterative procedure, which yields a unified and simple proof, achieving for any graph with density d and any approximation parameter the partition size. The novelty in our proof is: (a) a simple approach which yields both strong and weaker variant, and (b) improvements when d = o(1). At an abstract level, our proof can be seen a refinement and simplification of the “analytic” proof given by Lovasz and Szegedy."}],"date_published":"2017-01-01T00:00:00Z","volume":10185,"main_file_link":[{"url":"https://eprint.iacr.org/2016/965.pdf","open_access":"1"}],"oa":1,"publication_status":"published","alternative_title":["LNCS"],"author":[{"last_name":"Skórski","first_name":"Maciej","full_name":"Skórski, Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD"}],"type":"conference","day":"01","conference":{"start_date":"2017-04-20","end_date":"2017-04-22","name":"TAMC: Theory and Applications of Models of Computation","location":"Bern, Switzerland"},"title":"A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds","citation":{"ama":"Skórski M. A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. In: Jäger G, Steila S, eds. Vol 10185. Springer; 2017:586-599. doi:<a href=\"https://doi.org/10.1007/978-3-319-55911-7_42\">10.1007/978-3-319-55911-7_42</a>","apa":"Skórski, M. (2017). A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. In G. Jäger &#38; S. Steila (Eds.) (Vol. 10185, pp. 586–599). Presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland: Springer. <a href=\"https://doi.org/10.1007/978-3-319-55911-7_42\">https://doi.org/10.1007/978-3-319-55911-7_42</a>","short":"M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 586–599.","mla":"Skórski, Maciej. <i>A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds</i>. Edited by Gerhard Jäger and Silvia Steila, vol. 10185, Springer, 2017, pp. 586–99, doi:<a href=\"https://doi.org/10.1007/978-3-319-55911-7_42\">10.1007/978-3-319-55911-7_42</a>.","chicago":"Skórski, Maciej. “A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds.” edited by Gerhard Jäger and Silvia Steila, 10185:586–99. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-55911-7_42\">https://doi.org/10.1007/978-3-319-55911-7_42</a>.","ista":"Skórski M. 2017. A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. TAMC: Theory and Applications of Models of Computation, LNCS, vol. 10185, 586–599.","ieee":"M. Skórski, “A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds,” presented at the TAMC: Theory and Applications of Models of Computation, Bern, Switzerland, 2017, vol. 10185, pp. 586–599."},"doi":"10.1007/978-3-319-55911-7_42","language":[{"iso":"eng"}],"date_created":"2018-12-11T11:47:42Z","month":"01","page":"586 - 599","status":"public","intvolume":"     10185","department":[{"_id":"KrPi"}],"quality_controlled":"1","publisher":"Springer"},{"oa_version":"Preprint","year":"2017","publication_identifier":{"isbn":["9781509040964"]},"external_id":{"arxiv":["1702.01666"]},"scopus_import":1,"date_updated":"2021-01-12T08:07:53Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"6526","date_published":"2017-08-09T00:00:00Z","abstract":[{"lang":"eng","text":"This paper studies the complexity of estimating Rényi divergences of discrete distributions: p observed from samples and the baseline distribution q known a priori. Extending the results of Acharya et al. (SODA'15) on estimating Rényi entropy, we present improved estimation techniques together with upper and lower bounds on the sample complexity. We show that, contrarily to estimating Rényi entropy where a sublinear (in the alphabet size) number of samples suffices, the sample complexity is heavily dependent on events occurring unlikely in q, and is unbounded in general (no matter what an estimation technique is used). For any divergence of integer order bigger than 1, we provide upper and lower bounds on the number of samples dependent on probabilities of p and q (the lower bounds hold for non-integer orders as well). We conclude that the worst-case sample complexity is polynomial in the alphabet size if and only if the probabilities of q are non-negligible. This gives theoretical insights into heuristics used in the applied literature to handle numerical instability, which occurs for small probabilities of q. Our result shows that they should be handled with care not only because of numerical issues, but also because of a blow up in the sample complexity."}],"article_number":"8006529","arxiv":1,"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1702.01666","open_access":"1"}],"publication_status":"published","type":"conference","author":[{"id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","last_name":"Skórski","full_name":"Skórski, Maciej","first_name":"Maciej"}],"day":"09","title":"On the complexity of estimating Rènyi divergences","conference":{"start_date":"2017-06-25","end_date":"2017-06-30","name":"ISIT: International Symposium on Information Theory","location":"Aachen, Germany"},"citation":{"mla":"Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>, 8006529, IEEE, 2017, doi:<a href=\"https://doi.org/10.1109/isit.2017.8006529\">10.1109/isit.2017.8006529</a>.","chicago":"Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” In <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>. IEEE, 2017. <a href=\"https://doi.org/10.1109/isit.2017.8006529\">https://doi.org/10.1109/isit.2017.8006529</a>.","ista":"Skórski M. 2017. On the complexity of estimating Rènyi divergences. 2017 IEEE International Symposium on Information Theory (ISIT). ISIT: International Symposium on Information Theory, 8006529.","ieee":"M. Skórski, “On the complexity of estimating Rènyi divergences,” in <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>, Aachen, Germany, 2017.","ama":"Skórski M. On the complexity of estimating Rènyi divergences. In: <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>. IEEE; 2017. doi:<a href=\"https://doi.org/10.1109/isit.2017.8006529\">10.1109/isit.2017.8006529</a>","apa":"Skórski, M. (2017). On the complexity of estimating Rènyi divergences. In <i>2017 IEEE International Symposium on Information Theory (ISIT)</i>. Aachen, Germany: IEEE. <a href=\"https://doi.org/10.1109/isit.2017.8006529\">https://doi.org/10.1109/isit.2017.8006529</a>","short":"M. Skórski, in:, 2017 IEEE International Symposium on Information Theory (ISIT), IEEE, 2017."},"ec_funded":1,"doi":"10.1109/isit.2017.8006529","language":[{"iso":"eng"}],"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"date_created":"2019-06-06T12:53:09Z","month":"08","status":"public","publication":"2017 IEEE International Symposium on Information Theory (ISIT)","department":[{"_id":"KrPi"}],"quality_controlled":"1","publisher":"IEEE"},{"publication_status":"published","publisher":"ACM Press","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2017/443"}],"oa":1,"quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security","status":"public","page":"1001-1017","month":"10","abstract":[{"text":"A memory-hard function (MHF) ƒn with parameter n can be computed in sequential time and space n. Simultaneously, a high amortized parallel area-time complexity (aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate at which an adversary (using a custom computational device) can evaluate a security sensitive function that still occasionally needs to be evaluated by honest users (using an off-the-shelf general purpose device). The most prevalent examples of such sensitive functions are Key Derivation Functions (KDFs) and password hashing algorithms where rate limits help mitigate off-line dictionary attacks. As the honest users' inputs to these functions are often (low-entropy) passwords special attention is given to a class of side-channel resistant MHFs called iMHFs.\r\n\r\nEssentially all iMHFs can be viewed as some mode of operation (making n calls to some round function) given by a directed acyclic graph (DAG) with very low indegree. Recently, a combinatorial property of a DAG has been identified (called \"depth-robustness\") which results in good provable security for an iMHF based on that DAG. Depth-robust DAGs have also proven useful in other cryptographic applications. Unfortunately, up till now, all known very depth-robust DAGs are impractically complicated and little is known about their exact (i.e. non-asymptotic) depth-robustness both in theory and in practice.\r\n\r\nIn this work we build and analyze (both formally and empirically) several exceedingly simple and efficient to navigate practical DAGs for use in iMHFs and other applications. For each DAG we:\r\n*Prove that their depth-robustness is asymptotically maximal.\r\n*Prove bounds of at least 3 orders of magnitude better on their exact depth-robustness compared to known bounds for other practical iMHF.\r\n*Implement and empirically evaluate their depth-robustness and aAT against a variety of state-of-the art (and several new) depth-reduction and low aAT attacks. \r\nWe find that, against all attacks, the new DAGs perform significantly better in practice than Argon2i, the most widely deployed iMHF in practice.\r\n\r\nAlong the way we also improve the best known empirical attacks on the aAT of Argon2i by implementing and testing several heuristic versions of a (hitherto purely theoretical) depth-reduction attack. Finally, we demonstrate practicality of our constructions by modifying the Argon2i code base to use one of the new high aAT DAGs. Experimental benchmarks on a standard off-the-shelf CPU show that the new modifications do not adversely affect the impressive throughput of Argon2i (despite seemingly enjoying significantly higher aAT).\r\n","lang":"eng"}],"_id":"6527","date_created":"2019-06-06T13:21:29Z","date_published":"2017-10-30T00:00:00Z","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"date_updated":"2021-01-12T08:07:53Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"scopus_import":1,"doi":"10.1145/3133956.3134031","publication_identifier":{"isbn":["9781450349468"]},"ec_funded":1,"citation":{"mla":"Alwen, Joel F., et al. “Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions.” <i>Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security</i>, ACM Press, 2017, pp. 1001–17, doi:<a href=\"https://doi.org/10.1145/3133956.3134031\">10.1145/3133956.3134031</a>.","ieee":"J. F. Alwen, J. Blocki, and B. Harsha, “Practical graphs for optimal side-channel resistant memory-hard functions,” in <i>Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security</i>, Dallas, TX, USA, 2017, pp. 1001–1017.","ista":"Alwen JF, Blocki J, Harsha B. 2017. Practical graphs for optimal side-channel resistant memory-hard functions. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. CCS: Conference on Computer and Communications Security, 1001–1017.","chicago":"Alwen, Joel F, Jeremiah Blocki, and Ben Harsha. “Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions.” In <i>Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security</i>, 1001–17. ACM Press, 2017. <a href=\"https://doi.org/10.1145/3133956.3134031\">https://doi.org/10.1145/3133956.3134031</a>.","apa":"Alwen, J. F., Blocki, J., &#38; Harsha, B. (2017). Practical graphs for optimal side-channel resistant memory-hard functions. In <i>Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security</i> (pp. 1001–1017). Dallas, TX, USA: ACM Press. <a href=\"https://doi.org/10.1145/3133956.3134031\">https://doi.org/10.1145/3133956.3134031</a>","ama":"Alwen JF, Blocki J, Harsha B. Practical graphs for optimal side-channel resistant memory-hard functions. In: <i>Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security</i>. ACM Press; 2017:1001-1017. doi:<a href=\"https://doi.org/10.1145/3133956.3134031\">10.1145/3133956.3134031</a>","short":"J.F. Alwen, J. Blocki, B. Harsha, in:, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ACM Press, 2017, pp. 1001–1017."},"conference":{"end_date":"2017-11-03","start_date":"2017-10-30","name":"CCS: Conference on Computer and Communications Security","location":"Dallas, TX, USA"},"title":"Practical graphs for optimal side-channel resistant memory-hard functions","day":"30","year":"2017","oa_version":"Submitted Version","type":"conference","author":[{"first_name":"Joel F","full_name":"Alwen, Joel F","last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Blocki","first_name":"Jeremiah","full_name":"Blocki, Jeremiah"},{"last_name":"Harsha","first_name":"Ben","full_name":"Harsha, Ben"}]},{"article_type":"original","publist_id":"6166","year":"2017","has_accepted_license":"1","oa_version":"Submitted Version","external_id":{"isi":["000410788600007"]},"scopus_import":"1","date_updated":"2023-09-20T11:20:58Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file":[{"relation":"main_file","file_id":"7843","content_type":"application/pdf","date_created":"2020-05-14T16:30:17Z","creator":"dernst","file_size":516959,"file_name":"2017_JournalCrypto_Kiltz.pdf","access_level":"open_access","date_updated":"2020-07-14T12:44:37Z","checksum":"c647520d115b772a1682fc06fa273eb1"}],"_id":"1187","abstract":[{"text":"We construct efficient authentication protocols and message authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work—starting with the (Formula presented.) protocol of Hopper and Blum in 2001—until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle attacks. A MAC implies such a (two-round) protocol.","lang":"eng"}],"date_published":"2017-10-01T00:00:00Z","article_processing_charge":"No","issue":"4","file_date_updated":"2020-07-14T12:44:37Z","volume":30,"publication_status":"published","oa":1,"day":"01","author":[{"last_name":"Kiltz","first_name":"Eike","full_name":"Kiltz, Eike"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Venturi","full_name":"Venturi, Daniele","first_name":"Daniele"},{"last_name":"Cash","first_name":"David","full_name":"Cash, David"},{"full_name":"Jain, Abhishek","first_name":"Abhishek","last_name":"Jain"}],"type":"journal_article","citation":{"short":"E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology 30 (2017) 1238–1275.","apa":"Kiltz, E., Pietrzak, K. Z., Venturi, D., Cash, D., &#38; Jain, A. (2017). Efficient authentication from hard learning problems. <i>Journal of Cryptology</i>. Springer. <a href=\"https://doi.org/10.1007/s00145-016-9247-3\">https://doi.org/10.1007/s00145-016-9247-3</a>","ama":"Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. Efficient authentication from hard learning problems. <i>Journal of Cryptology</i>. 2017;30(4):1238-1275. doi:<a href=\"https://doi.org/10.1007/s00145-016-9247-3\">10.1007/s00145-016-9247-3</a>","ista":"Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. 2017. Efficient authentication from hard learning problems. Journal of Cryptology. 30(4), 1238–1275.","ieee":"E. Kiltz, K. Z. Pietrzak, D. Venturi, D. Cash, and A. Jain, “Efficient authentication from hard learning problems,” <i>Journal of Cryptology</i>, vol. 30, no. 4. Springer, pp. 1238–1275, 2017.","chicago":"Kiltz, Eike, Krzysztof Z Pietrzak, Daniele Venturi, David Cash, and Abhishek Jain. “Efficient Authentication from Hard Learning Problems.” <i>Journal of Cryptology</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00145-016-9247-3\">https://doi.org/10.1007/s00145-016-9247-3</a>.","mla":"Kiltz, Eike, et al. “Efficient Authentication from Hard Learning Problems.” <i>Journal of Cryptology</i>, vol. 30, no. 4, Springer, 2017, pp. 1238–75, doi:<a href=\"https://doi.org/10.1007/s00145-016-9247-3\">10.1007/s00145-016-9247-3</a>."},"ec_funded":1,"title":"Efficient authentication from hard learning problems","language":[{"iso":"eng"}],"ddc":["000"],"doi":"10.1007/s00145-016-9247-3","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"}],"related_material":{"record":[{"id":"3238","relation":"earlier_version","status":"public"}]},"month":"10","date_created":"2018-12-11T11:50:37Z","page":"1238 - 1275","publication":"Journal of Cryptology","quality_controlled":"1","department":[{"_id":"KrPi"}],"status":"public","intvolume":"        30","publisher":"Springer","isi":1},{"page":"1321 - 1362","issue":"4","month":"04","_id":"1177","abstract":[{"text":"Boldyreva, Palacio and Warinschi introduced a multiple forking game as an extension of general forking. The notion of (multiple) forking is a useful abstraction from the actual simulation of cryptographic scheme to the adversary in a security reduction, and is achieved through the intermediary of a so-called wrapper algorithm. Multiple forking has turned out to be a useful tool in the security argument of several cryptographic protocols. However, a reduction employing multiple forking incurs a significant degradation of (Formula presented.) , where (Formula presented.) denotes the upper bound on the underlying random oracle calls and (Formula presented.) , the number of forkings. In this work we take a closer look at the reasons for the degradation with a tighter security bound in mind. We nail down the exact set of conditions for success in the multiple forking game. A careful analysis of the cryptographic schemes and corresponding security reduction employing multiple forking leads to the formulation of ‘dependence’ and ‘independence’ conditions pertaining to the output of the wrapper in different rounds. Based on the (in)dependence conditions we propose a general framework of multiple forking and a General Multiple Forking Lemma. Leveraging (in)dependence to the full allows us to improve the degradation factor in the multiple forking game by a factor of (Formula presented.). By implication, the cost of a single forking involving two random oracles (augmented forking) matches that involving a single random oracle (elementary forking). Finally, we study the effect of these observations on the concrete security of existing schemes employing multiple forking. We conclude that by careful design of the protocol (and the wrapper in the security reduction) it is possible to harness our observations to the full extent.","lang":"eng"}],"date_created":"2018-12-11T11:50:33Z","date_published":"2016-04-01T00:00:00Z","publisher":"Springer","publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"http://eprint.iacr.org/2013/651"}],"publication":"Algorithmica","quality_controlled":"1","department":[{"_id":"KrPi"}],"status":"public","intvolume":"        74","volume":74,"citation":{"mla":"Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking: Leveraging (in)Dependence for a Tighter Bound.” <i>Algorithmica</i>, vol. 74, no. 4, Springer, 2016, pp. 1321–62, doi:<a href=\"https://doi.org/10.1007/s00453-015-9997-6\">10.1007/s00453-015-9997-6</a>.","chicago":"Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking: Leveraging (in)Dependence for a Tighter Bound.” <i>Algorithmica</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s00453-015-9997-6\">https://doi.org/10.1007/s00453-015-9997-6</a>.","ista":"Kamath Hosdurg C, Chatterjee S. 2016. A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. Algorithmica. 74(4), 1321–1362.","ieee":"C. Kamath Hosdurg and S. Chatterjee, “A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound,” <i>Algorithmica</i>, vol. 74, no. 4. Springer, pp. 1321–1362, 2016.","ama":"Kamath Hosdurg C, Chatterjee S. A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. <i>Algorithmica</i>. 2016;74(4):1321-1362. doi:<a href=\"https://doi.org/10.1007/s00453-015-9997-6\">10.1007/s00453-015-9997-6</a>","apa":"Kamath Hosdurg, C., &#38; Chatterjee, S. (2016). A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/s00453-015-9997-6\">https://doi.org/10.1007/s00453-015-9997-6</a>","short":"C. Kamath Hosdurg, S. Chatterjee, Algorithmica 74 (2016) 1321–1362."},"title":"A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound","publist_id":"6177","day":"01","type":"journal_article","author":[{"first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Chatterjee, Sanjit","first_name":"Sanjit","last_name":"Chatterjee"}],"oa_version":"Submitted Version","year":"2016","acknowledgement":"We are grateful to the anonymous reviewers for their insightful comments. The\r\ndetailed reports helped us a lot to address the technical mistakes as well as to improve the overall presentation of the paper.","date_updated":"2021-01-12T06:48:52Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"doi":"10.1007/s00453-015-9997-6"},{"page":"183 - 203","date_created":"2018-12-11T11:50:34Z","month":"10","publisher":"Springer","intvolume":"      9985","status":"public","department":[{"_id":"KrPi"}],"quality_controlled":"1","conference":{"name":"TCC: Theory of Cryptography Conference","end_date":"2016-11-03","start_date":"2016-10-31","location":"Beijing, China"},"title":"Pseudoentropy: Lower-bounds for chain rules and transformations","ec_funded":1,"citation":{"chicago":"Pietrzak, Krzysztof Z, and Skorski Maciej. “Pseudoentropy: Lower-Bounds for Chain Rules and Transformations,” 9985:183–203. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-662-53641-4_8\">https://doi.org/10.1007/978-3-662-53641-4_8</a>.","ista":"Pietrzak KZ, Maciej S. 2016. Pseudoentropy: Lower-bounds for chain rules and transformations. TCC: Theory of Cryptography Conference, LNCS, vol. 9985, 183–203.","ieee":"K. Z. Pietrzak and S. Maciej, “Pseudoentropy: Lower-bounds for chain rules and transformations,” presented at the TCC: Theory of Cryptography Conference, Beijing, China, 2016, vol. 9985, pp. 183–203.","mla":"Pietrzak, Krzysztof Z., and Skorski Maciej. <i>Pseudoentropy: Lower-Bounds for Chain Rules and Transformations</i>. Vol. 9985, Springer, 2016, pp. 183–203, doi:<a href=\"https://doi.org/10.1007/978-3-662-53641-4_8\">10.1007/978-3-662-53641-4_8</a>.","short":"K.Z. Pietrzak, S. Maciej, in:, Springer, 2016, pp. 183–203.","ama":"Pietrzak KZ, Maciej S. Pseudoentropy: Lower-bounds for chain rules and transformations. In: Vol 9985. Springer; 2016:183-203. doi:<a href=\"https://doi.org/10.1007/978-3-662-53641-4_8\">10.1007/978-3-662-53641-4_8</a>","apa":"Pietrzak, K. Z., &#38; Maciej, S. (2016). Pseudoentropy: Lower-bounds for chain rules and transformations (Vol. 9985, pp. 183–203). Presented at the TCC: Theory of Cryptography Conference, Beijing, China: Springer. <a href=\"https://doi.org/10.1007/978-3-662-53641-4_8\">https://doi.org/10.1007/978-3-662-53641-4_8</a>"},"alternative_title":["LNCS"],"author":[{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Skorski","full_name":"Maciej, Skorski","last_name":"Maciej"}],"type":"conference","day":"22","acknowledgement":"K. Pietrzak—Supported by the European Research Council consolidator grant (682815-TOCNeT).\r\nM. Skórski—Supported by the National Science Center, Poland (2015/17/N/ST6/03564).","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"doi":"10.1007/978-3-662-53641-4_8","language":[{"iso":"eng"}],"date_published":"2016-10-22T00:00:00Z","_id":"1179","abstract":[{"text":"Computational notions of entropy have recently found many applications, including leakage-resilient cryptography, deterministic encryption or memory delegation. The two main types of results which make computational notions so useful are (1) Chain rules, which quantify by how much the computational entropy of a variable decreases if conditioned on some other variable (2) Transformations, which quantify to which extend one type of entropy implies another.\r\n\r\nSuch chain rules and transformations typically lose a significant amount in quality of the entropy, and are the reason why applying these results one gets rather weak quantitative security bounds. In this paper we for the first time prove lower bounds in this context, showing that existing results for transformations are, unfortunately, basically optimal for non-adaptive black-box reductions (and it’s hard to imagine how non black-box reductions or adaptivity could be useful here.)\r\n\r\nA variable X has k bits of HILL entropy of quality (ϵ,s)\r\nif there exists a variable Y with k bits min-entropy which cannot be distinguished from X with advantage ϵ\r\n\r\nby distinguishing circuits of size s. A weaker notion is Metric entropy, where we switch quantifiers, and only require that for every distinguisher of size s, such a Y exists.\r\n\r\nWe first describe our result concerning transformations. By definition, HILL implies Metric without any loss in quality. Metric entropy often comes up in applications, but must be transformed to HILL for meaningful security guarantees. The best known result states that if a variable X has k bits of Metric entropy of quality (ϵ,s)\r\n, then it has k bits of HILL with quality (2ϵ,s⋅ϵ2). We show that this loss of a factor Ω(ϵ−2)\r\n\r\nin circuit size is necessary. In fact, we show the stronger result that this loss is already necessary when transforming so called deterministic real valued Metric entropy to randomised boolean Metric (both these variants of Metric entropy are implied by HILL without loss in quality).\r\n\r\nThe chain rule for HILL entropy states that if X has k bits of HILL entropy of quality (ϵ,s)\r\n, then for any variable Z of length m, X conditioned on Z has k−m bits of HILL entropy with quality (ϵ,s⋅ϵ2/2m). We show that a loss of Ω(2m/ϵ) in circuit size necessary here. Note that this still leaves a gap of ϵ between the known bound and our lower bound.","lang":"eng"}],"oa":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/159"}],"publication_status":"published","volume":9985,"oa_version":"Preprint","year":"2016","publist_id":"6175","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:48:53Z","scopus_import":1},{"scopus_import":1,"date_updated":"2021-01-12T06:52:16Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2016","has_accepted_license":"1","oa_version":"Submitted Version","publist_id":"5497","oa":1,"publication_status":"published","pubrep_id":"677","volume":9452,"file_date_updated":"2020-07-14T12:45:08Z","_id":"1653","date_published":"2016-01-08T00:00:00Z","abstract":[{"lang":"eng","text":"A somewhere statistically binding (SSB) hash, introduced by Hubáček and Wichs (ITCS ’15), can be used to hash a long string x to a short digest y = H hk (x) using a public hashing-key hk. Furthermore, there is a way to set up the hash key hk to make it statistically binding on some arbitrary hidden position i, meaning that: (1) the digest y completely determines the i’th bit (or symbol) of x so that all pre-images of y have the same value in the i’th position, (2) it is computationally infeasible to distinguish the position i on which hk is statistically binding from any other position i’. Lastly, the hash should have a local opening property analogous to Merkle-Tree hashing, meaning that given x and y = H hk (x) it should be possible to create a short proof π that certifies the value of the i’th bit (or symbol) of x without having to provide the entire input x. A similar primitive called a positional accumulator, introduced by Koppula, Lewko and Waters (STOC ’15) further supports dynamic updates of the hashed value. These tools, which are interesting in their own right, also serve as one of the main technical components in several recent works building advanced applications from indistinguishability obfuscation (iO).\r\n\r\nThe prior constructions of SSB hashing and positional accumulators required fully homomorphic encryption (FHE) and iO respectively. In this work, we give new constructions of these tools based on well studied number-theoretic assumptions such as DDH, Phi-Hiding and DCR, as well as a general construction from lossy/injective functions."}],"file":[{"date_created":"2018-12-12T10:12:05Z","relation":"main_file","file_id":"4923","content_type":"application/pdf","checksum":"a57711cb660c5b17b42bb47275a00180","access_level":"open_access","date_updated":"2020-07-14T12:45:08Z","file_size":580088,"creator":"system","file_name":"IST-2016-677-v1+1_869.pdf"}],"project":[{"name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"}],"doi":"10.1007/978-3-662-48797-6_6","ddc":["000"],"language":[{"iso":"eng"}],"title":"New realizations of somewhere statistically binding hashing and positional accumulators","conference":{"location":"Auckland, New Zealand","name":"ASIACRYPT: Theory and Application of Cryptology and Information Security","end_date":"2015-12-03","start_date":"2015-11-29"},"citation":{"short":"T. Okamoto, K.Z. Pietrzak, B. Waters, D. Wichs, in:, Springer, 2016, pp. 121–145.","apa":"Okamoto, T., Pietrzak, K. Z., Waters, B., &#38; Wichs, D. (2016). New realizations of somewhere statistically binding hashing and positional accumulators (Vol. 9452, pp. 121–145). Presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Auckland, New Zealand: Springer. <a href=\"https://doi.org/10.1007/978-3-662-48797-6_6\">https://doi.org/10.1007/978-3-662-48797-6_6</a>","ama":"Okamoto T, Pietrzak KZ, Waters B, Wichs D. New realizations of somewhere statistically binding hashing and positional accumulators. In: Vol 9452. Springer; 2016:121-145. doi:<a href=\"https://doi.org/10.1007/978-3-662-48797-6_6\">10.1007/978-3-662-48797-6_6</a>","ista":"Okamoto T, Pietrzak KZ, Waters B, Wichs D. 2016. New realizations of somewhere statistically binding hashing and positional accumulators. ASIACRYPT: Theory and Application of Cryptology and Information Security, LNCS, vol. 9452, 121–145.","ieee":"T. Okamoto, K. Z. Pietrzak, B. Waters, and D. Wichs, “New realizations of somewhere statistically binding hashing and positional accumulators,” presented at the ASIACRYPT: Theory and Application of Cryptology and Information Security, Auckland, New Zealand, 2016, vol. 9452, pp. 121–145.","chicago":"Okamoto, Tatsuaki, Krzysztof Z Pietrzak, Brent Waters, and Daniel Wichs. “New Realizations of Somewhere Statistically Binding Hashing and Positional Accumulators,” 9452:121–45. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-662-48797-6_6\">https://doi.org/10.1007/978-3-662-48797-6_6</a>.","mla":"Okamoto, Tatsuaki, et al. <i>New Realizations of Somewhere Statistically Binding Hashing and Positional Accumulators</i>. Vol. 9452, Springer, 2016, pp. 121–45, doi:<a href=\"https://doi.org/10.1007/978-3-662-48797-6_6\">10.1007/978-3-662-48797-6_6</a>."},"ec_funded":1,"type":"conference","author":[{"first_name":"Tatsuaki","full_name":"Okamoto, Tatsuaki","last_name":"Okamoto"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Brent","full_name":"Waters, Brent","last_name":"Waters"},{"full_name":"Wichs, Daniel","first_name":"Daniel","last_name":"Wichs"}],"alternative_title":["LNCS"],"day":"08","publisher":"Springer","intvolume":"      9452","status":"public","department":[{"_id":"KrPi"}],"quality_controlled":"1","page":"121 - 145","date_created":"2018-12-11T11:53:16Z","month":"01"},{"has_accepted_license":"1","oa_version":"Submitted Version","year":"2016","publist_id":"5715","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T11:05:09Z","scopus_import":1,"_id":"1479","abstract":[{"text":"Most entropy notions H(.) like Shannon or min-entropy satisfy a chain rule stating that for random variables X,Z, and A we have H(X|Z,A)≥H(X|Z)−|A|. That is, by conditioning on A the entropy of X can decrease by at most the bitlength |A| of A. Such chain rules are known to hold for some computational entropy notions like Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue of min-entropy, the chain rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption, and memory delegation. These applications rely on restricted special cases of the chain rule. Whether the chain rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: we construct joint distributions (X,Z,A), where A is a distribution over a single bit, such that the HILL entropy H HILL (X|Z) is large but H HILL (X|Z,A) is basically zero.\r\n\r\nOur counterexample just makes the minimal assumption that NP⊈P/poly. Under the stronger assumption that injective one-way function exist, we can make all the distributions efficiently samplable.\r\n\r\nFinally, we show that some more sophisticated cryptographic objects like lossy functions can be used to sample a distribution constituting a counterexample to the chain rule making only a single invocation to the underlying object.","lang":"eng"}],"date_published":"2016-09-01T00:00:00Z","file":[{"date_created":"2018-12-12T10:13:29Z","content_type":"application/pdf","file_id":"5012","relation":"main_file","date_updated":"2020-07-14T12:44:56Z","access_level":"open_access","checksum":"7659296174fa75f5f0364f31f46f4bcf","file_name":"IST-2017-766-v1+1_678.pdf","creator":"system","file_size":483258}],"issue":"3","volume":25,"pubrep_id":"766","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"file_date_updated":"2020-07-14T12:44:56Z","oa":1,"publication_status":"published","author":[{"id":"329FCCF0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2835-9093","last_name":"Krenn","full_name":"Krenn, Stephan","first_name":"Stephan"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak"},{"first_name":"Akshay","full_name":"Wadia, Akshay","last_name":"Wadia"},{"first_name":"Daniel","full_name":"Wichs, Daniel","last_name":"Wichs"}],"type":"journal_article","day":"01","title":"A counterexample to the chain rule for conditional HILL entropy","ec_funded":1,"citation":{"short":"S. Krenn, K.Z. Pietrzak, A. Wadia, D. Wichs, Computational Complexity 25 (2016) 567–605.","ama":"Krenn S, Pietrzak KZ, Wadia A, Wichs D. A counterexample to the chain rule for conditional HILL entropy. <i>Computational Complexity</i>. 2016;25(3):567-605. doi:<a href=\"https://doi.org/10.1007/s00037-015-0120-9\">10.1007/s00037-015-0120-9</a>","apa":"Krenn, S., Pietrzak, K. Z., Wadia, A., &#38; Wichs, D. (2016). A counterexample to the chain rule for conditional HILL entropy. <i>Computational Complexity</i>. Springer. <a href=\"https://doi.org/10.1007/s00037-015-0120-9\">https://doi.org/10.1007/s00037-015-0120-9</a>","chicago":"Krenn, Stephan, Krzysztof Z Pietrzak, Akshay Wadia, and Daniel Wichs. “A Counterexample to the Chain Rule for Conditional HILL Entropy.” <i>Computational Complexity</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s00037-015-0120-9\">https://doi.org/10.1007/s00037-015-0120-9</a>.","ieee":"S. Krenn, K. Z. Pietrzak, A. Wadia, and D. Wichs, “A counterexample to the chain rule for conditional HILL entropy,” <i>Computational Complexity</i>, vol. 25, no. 3. Springer, pp. 567–605, 2016.","ista":"Krenn S, Pietrzak KZ, Wadia A, Wichs D. 2016. A counterexample to the chain rule for conditional HILL entropy. Computational Complexity. 25(3), 567–605.","mla":"Krenn, Stephan, et al. “A Counterexample to the Chain Rule for Conditional HILL Entropy.” <i>Computational Complexity</i>, vol. 25, no. 3, Springer, 2016, pp. 567–605, doi:<a href=\"https://doi.org/10.1007/s00037-015-0120-9\">10.1007/s00037-015-0120-9</a>."},"doi":"10.1007/s00037-015-0120-9","ddc":["004"],"language":[{"iso":"eng"}],"acknowledgement":"This work was partly funded by the European Research Council under ERC Starting Grant 259668-PSPC and ERC Advanced Grant 321310-PERCY.\r\n","related_material":{"record":[{"status":"public","id":"2940","relation":"earlier_version"}]},"project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Provable Security for Physical Cryptography","grant_number":"259668"}],"date_created":"2018-12-11T11:52:16Z","month":"09","page":"567 - 605","intvolume":"        25","status":"public","quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"Computational Complexity","publisher":"Springer"},{"quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"Journal of Cryptology","volume":29,"intvolume":"        29","status":"public","publication_status":"published","publisher":"Springer","month":"04","abstract":[{"lang":"eng","text":"A modular approach to constructing cryptographic protocols leads to simple designs but often inefficient instantiations. On the other hand, ad hoc constructions may yield efficient protocols at the cost of losing conceptual simplicity. We suggest a new design paradigm, structure-preserving cryptography, that provides a way to construct modular protocols with reasonable efficiency while retaining conceptual simplicity. A cryptographic scheme over a bilinear group is called structure-preserving if its public inputs and outputs consist of elements from the bilinear groups and their consistency can be verified by evaluating pairing-product equations. As structure-preserving schemes smoothly interoperate with each other, they are useful as building blocks in modular design of cryptographic applications. This paper introduces structure-preserving commitment and signature schemes over bilinear groups with several desirable properties. The commitment schemes include homomorphic, trapdoor and length-reducing commitments to group elements, and the structure-preserving signature schemes are the first ones that yield constant-size signatures on multiple group elements. A structure-preserving signature scheme is called automorphic if the public keys lie in the message space, which cannot be achieved by compressing inputs via a cryptographic hash function, as this would destroy the mathematical structure we are trying to preserve. Automorphic signatures can be used for building certification chains underlying privacy-preserving protocols. Among a vast number of applications of structure-preserving protocols, we present an efficient round-optimal blind-signature scheme and a group signature scheme with an efficient and concurrently secure protocol for enrolling new members."}],"_id":"1592","date_published":"2016-04-01T00:00:00Z","date_created":"2018-12-11T11:52:54Z","page":"363 - 421","issue":"2","language":[{"iso":"eng"}],"date_updated":"2021-01-12T06:51:49Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"doi":"10.1007/s00145-014-9196-7","acknowledgement":"The authors would like to thank the anonymous reviewers of this paper. We also would like to express our appreciation to the program committee and the anonymous reviewers for CRYPTO 2010. The first author thanks Sherman S. M. Chow for his comment on group signatures in Sect. 7.1.","publist_id":"5579","day":"01","year":"2016","oa_version":"None","author":[{"full_name":"Abe, Masayuki","first_name":"Masayuki","last_name":"Abe"},{"id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","last_name":"Fuchsbauer","first_name":"Georg","full_name":"Fuchsbauer, Georg"},{"last_name":"Groth","full_name":"Groth, Jens","first_name":"Jens"},{"full_name":"Haralambiev, Kristiyan","first_name":"Kristiyan","last_name":"Haralambiev"},{"last_name":"Ohkubo","full_name":"Ohkubo, Miyako","first_name":"Miyako"}],"type":"journal_article","citation":{"short":"M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, M. Ohkubo, Journal of Cryptology 29 (2016) 363–421.","apa":"Abe, M., Fuchsbauer, G., Groth, J., Haralambiev, K., &#38; Ohkubo, M. (2016). Structure preserving signatures and commitments to group elements. <i>Journal of Cryptology</i>. Springer. <a href=\"https://doi.org/10.1007/s00145-014-9196-7\">https://doi.org/10.1007/s00145-014-9196-7</a>","ama":"Abe M, Fuchsbauer G, Groth J, Haralambiev K, Ohkubo M. Structure preserving signatures and commitments to group elements. <i>Journal of Cryptology</i>. 2016;29(2):363-421. doi:<a href=\"https://doi.org/10.1007/s00145-014-9196-7\">10.1007/s00145-014-9196-7</a>","ieee":"M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, and M. Ohkubo, “Structure preserving signatures and commitments to group elements,” <i>Journal of Cryptology</i>, vol. 29, no. 2. Springer, pp. 363–421, 2016.","ista":"Abe M, Fuchsbauer G, Groth J, Haralambiev K, Ohkubo M. 2016. Structure preserving signatures and commitments to group elements. Journal of Cryptology. 29(2), 363–421.","chicago":"Abe, Masayuki, Georg Fuchsbauer, Jens Groth, Kristiyan Haralambiev, and Miyako Ohkubo. “Structure Preserving Signatures and Commitments to Group Elements.” <i>Journal of Cryptology</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s00145-014-9196-7\">https://doi.org/10.1007/s00145-014-9196-7</a>.","mla":"Abe, Masayuki, et al. “Structure Preserving Signatures and Commitments to Group Elements.” <i>Journal of Cryptology</i>, vol. 29, no. 2, Springer, 2016, pp. 363–421, doi:<a href=\"https://doi.org/10.1007/s00145-014-9196-7\">10.1007/s00145-014-9196-7</a>."},"title":"Structure preserving signatures and commitments to group elements"},{"doi":"10.1007/978-3-662-53008-5_9","scopus_import":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"date_updated":"2021-01-12T06:50:11Z","title":"Efficiently computing data-independent memory-hard functions","conference":{"name":"CRYPTO: International Cryptology Conference","end_date":"2016-08-18","start_date":"2016-08-14","location":"Santa Barbara, CA, USA"},"citation":{"chicago":"Alwen, Joel F, and Jeremiah Blocki. “Efficiently Computing Data-Independent Memory-Hard Functions,” 9815:241–71. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-662-53008-5_9\">https://doi.org/10.1007/978-3-662-53008-5_9</a>.","ieee":"J. F. Alwen and J. Blocki, “Efficiently computing data-independent memory-hard functions,” presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, USA, 2016, vol. 9815, pp. 241–271.","ista":"Alwen JF, Blocki J. 2016. Efficiently computing data-independent memory-hard functions. CRYPTO: International Cryptology Conference, LNCS, vol. 9815, 241–271.","mla":"Alwen, Joel F., and Jeremiah Blocki. <i>Efficiently Computing Data-Independent Memory-Hard Functions</i>. Vol. 9815, Springer, 2016, pp. 241–71, doi:<a href=\"https://doi.org/10.1007/978-3-662-53008-5_9\">10.1007/978-3-662-53008-5_9</a>.","short":"J.F. Alwen, J. Blocki, in:, Springer, 2016, pp. 241–271.","ama":"Alwen JF, Blocki J. Efficiently computing data-independent memory-hard functions. In: Vol 9815. Springer; 2016:241-271. doi:<a href=\"https://doi.org/10.1007/978-3-662-53008-5_9\">10.1007/978-3-662-53008-5_9</a>","apa":"Alwen, J. F., &#38; Blocki, J. (2016). Efficiently computing data-independent memory-hard functions (Vol. 9815, pp. 241–271). Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-662-53008-5_9\">https://doi.org/10.1007/978-3-662-53008-5_9</a>"},"author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"first_name":"Jeremiah","full_name":"Blocki, Jeremiah","last_name":"Blocki"}],"type":"conference","alternative_title":["LNCS"],"oa_version":"Preprint","year":"2016","publist_id":"5876","day":"01","main_file_link":[{"open_access":"1","url":"http://eprint.iacr.org/2016/115"}],"oa":1,"publication_status":"published","publisher":"Springer","intvolume":"      9815","status":"public","volume":9815,"quality_controlled":"1","department":[{"_id":"KrPi"}],"page":"241 - 271","date_published":"2016-08-01T00:00:00Z","_id":"1365","abstract":[{"text":"A memory-hard function (MHF) f is equipped with a space cost σ and time cost τ parameter such that repeatedly computing fσ,τ on an application specific integrated circuit (ASIC) is not economically advantageous relative to a general purpose computer. Technically we would like that any (generalized) circuit for evaluating an iMHF fσ,τ has area × time (AT) complexity at Θ(σ2 ∗ τ). A data-independent MHF (iMHF) has the added property that it can be computed with almost optimal memory and time complexity by an algorithm which accesses memory in a pattern independent of the input value. Such functions can be specified by fixing a directed acyclic graph (DAG) G on n = Θ(σ ∗ τ) nodes representing its computation graph. In this work we develop new tools for analyzing iMHFs. First we define and motivate a new complexity measure capturing the amount of energy (i.e. electricity) required to compute a function. We argue that, in practice, this measure is at least as important as the more traditional AT-complexity. Next we describe an algorithm A for repeatedly evaluating an iMHF based on an arbitrary DAG G. We upperbound both its energy and AT complexities per instance evaluated in terms of a certain combinatorial property of G. Next we instantiate our attack for several general classes of DAGs which include those underlying many of the most important iMHF candidates in the literature. In particular, we obtain the following results which hold for all choices of parameters σ and τ (and thread-count) such that n = σ ∗ τ. -The Catena-Dragonfly function of [FLW13] has AT and energy complexities O(n1.67). -The Catena-Butterfly function of [FLW13] has complexities is O(n1.67). -The Double-Buffer and the Linear functions of [CGBS16] both have complexities in O(n1.67). -The Argon2i function of [BDK15] (winner of the Password Hashing Competition [PHC]) has complexities O(n7/4 log(n)). -The Single-Buffer function of [CGBS16] has complexities O(n7/4 log(n)). -Any iMHF can be computed by an algorithm with complexities O(n2/ log1 −ε(n)) for all ε &gt; 0. In particular when τ = 1 this shows that the goal of constructing an iMHF with AT-complexity Θ(σ2 ∗ τ ) is unachievable. Along the way we prove a lemma upper-bounding the depth-robustness of any DAG which may prove to be of independent interest.","lang":"eng"}],"date_created":"2018-12-11T11:51:36Z","month":"08"},{"month":"05","date_created":"2018-12-11T11:51:36Z","page":"87 - 116","department":[{"_id":"KrPi"}],"quality_controlled":"1","status":"public","intvolume":"      9665","publisher":"Springer","day":"01","alternative_title":["LNCS"],"author":[{"id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","last_name":"Gazi","full_name":"Gazi, Peter","first_name":"Peter"},{"last_name":"Tessaro","full_name":"Tessaro, Stefano","first_name":"Stefano"}],"type":"conference","ec_funded":1,"citation":{"chicago":"Gazi, Peter, and Stefano Tessaro. “Provably Robust Sponge-Based PRNGs and KDFs,” 9665:87–116. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-662-49890-3_4\">https://doi.org/10.1007/978-3-662-49890-3_4</a>.","ieee":"P. Gazi and S. Tessaro, “Provably robust sponge-based PRNGs and KDFs,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016, vol. 9665, pp. 87–116.","ista":"Gazi P, Tessaro S. 2016. Provably robust sponge-based PRNGs and KDFs. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 9665, 87–116.","mla":"Gazi, Peter, and Stefano Tessaro. <i>Provably Robust Sponge-Based PRNGs and KDFs</i>. Vol. 9665, Springer, 2016, pp. 87–116, doi:<a href=\"https://doi.org/10.1007/978-3-662-49890-3_4\">10.1007/978-3-662-49890-3_4</a>.","short":"P. Gazi, S. Tessaro, in:, Springer, 2016, pp. 87–116.","ama":"Gazi P, Tessaro S. Provably robust sponge-based PRNGs and KDFs. In: Vol 9665. Springer; 2016:87-116. doi:<a href=\"https://doi.org/10.1007/978-3-662-49890-3_4\">10.1007/978-3-662-49890-3_4</a>","apa":"Gazi, P., &#38; Tessaro, S. (2016). Provably robust sponge-based PRNGs and KDFs (Vol. 9665, pp. 87–116). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria: Springer. <a href=\"https://doi.org/10.1007/978-3-662-49890-3_4\">https://doi.org/10.1007/978-3-662-49890-3_4</a>"},"conference":{"location":"Vienna, Austria","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","end_date":"2016-05-12","start_date":"2016-05-08"},"title":"Provably robust sponge-based PRNGs and KDFs","language":[{"iso":"eng"}],"doi":"10.1007/978-3-662-49890-3_4","project":[{"grant_number":"259668","name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"_id":"1366","date_published":"2016-05-01T00:00:00Z","abstract":[{"text":"We study the problem of devising provably secure PRNGs with input based on the sponge paradigm. Such constructions are very appealing, as efficient software/hardware implementations of SHA-3 can easily be translated into a PRNG in a nearly black-box way. The only existing sponge-based construction, proposed by Bertoni et al. (CHES 2010), fails to achieve the security notion of robustness recently considered by Dodis et al. (CCS 2013), for two reasons: (1) The construction is deterministic, and thus there are high-entropy input distributions on which the construction fails to extract random bits, and (2) The construction is not forward secure, and presented solutions aiming at restoring forward security have not been rigorously analyzed. We propose a seeded variant of Bertoni et al.’s PRNG with input which we prove secure in the sense of robustness, delivering in particular concrete security bounds. On the way, we make what we believe to be an important conceptual contribution, developing a variant of the security framework of Dodis et al. tailored at the ideal permutation model that captures PRNG security in settings where the weakly random inputs are provided from a large class of possible adversarial samplers which are also allowed to query the random permutation. As a further application of our techniques, we also present an efficient sponge-based key-derivation function (which can be instantiated from SHA-3 in a black-box fashion), which we also prove secure when fed with samples from permutation-dependent distributions.","lang":"eng"}],"volume":9665,"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/169/20160219:201940"}],"oa":1,"publist_id":"5872","year":"2016","oa_version":"Preprint","date_updated":"2021-01-12T06:50:11Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T10:08:16Z","scopus_import":1,"oa_version":"Submitted Version","year":"2016","publist_id":"6109","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/662"}],"oa":1,"publication_status":"published","volume":9841,"date_published":"2016-08-11T00:00:00Z","_id":"1225","abstract":[{"text":"At Crypto 2015 Fuchsbauer, Hanser and Slamanig (FHS) presented the first standard-model construction of efficient roundoptimal blind signatures that does not require complexity leveraging. It is conceptually simple and builds on the primitive of structure-preserving signatures on equivalence classes (SPS-EQ). FHS prove the unforgeability of their scheme assuming EUF-CMA security of the SPS-EQ scheme and hardness of a version of the DH inversion problem. Blindness under adversarially chosen keys is proven under an interactive variant of the DDH assumption. We propose a variant of their scheme whose blindness can be proven under a non-interactive assumption, namely a variant of the bilinear DDH assumption. We moreover prove its unforgeability assuming only unforgeability of the underlying SPS-EQ but no additional assumptions as needed for the FHS scheme.","lang":"eng"}],"project":[{"call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668","name":"Provable Security for Physical Cryptography"},{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"related_material":{"record":[{"relation":"earlier_version","id":"1647","status":"public"}]},"doi":"10.1007/978-3-319-44618-9_21","language":[{"iso":"eng"}],"conference":{"location":"Amalfi, Italy","name":"SCN: Security and Cryptography for Networks","end_date":"2016-09-02","start_date":"2016-08-31"},"title":"Practical round-optimal blind signatures in the standard model from weaker assumptions","ec_funded":1,"citation":{"ieee":"G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, and D. Slamanig, “Practical round-optimal blind signatures in the standard model from weaker assumptions,” presented at the SCN: Security and Cryptography for Networks, Amalfi, Italy, 2016, vol. 9841, pp. 391–408.","ista":"Fuchsbauer G, Hanser C, Kamath Hosdurg C, Slamanig D. 2016. Practical round-optimal blind signatures in the standard model from weaker assumptions. SCN: Security and Cryptography for Networks, LNCS, vol. 9841, 391–408.","chicago":"Fuchsbauer, Georg, Christian Hanser, Chethan Kamath Hosdurg, and Daniel Slamanig. “Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions,” 9841:391–408. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-44618-9_21\">https://doi.org/10.1007/978-3-319-44618-9_21</a>.","mla":"Fuchsbauer, Georg, et al. <i>Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions</i>. Vol. 9841, Springer, 2016, pp. 391–408, doi:<a href=\"https://doi.org/10.1007/978-3-319-44618-9_21\">10.1007/978-3-319-44618-9_21</a>.","short":"G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, D. Slamanig, in:, Springer, 2016, pp. 391–408.","apa":"Fuchsbauer, G., Hanser, C., Kamath Hosdurg, C., &#38; Slamanig, D. (2016). Practical round-optimal blind signatures in the standard model from weaker assumptions (Vol. 9841, pp. 391–408). Presented at the SCN: Security and Cryptography for Networks, Amalfi, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-319-44618-9_21\">https://doi.org/10.1007/978-3-319-44618-9_21</a>","ama":"Fuchsbauer G, Hanser C, Kamath Hosdurg C, Slamanig D. Practical round-optimal blind signatures in the standard model from weaker assumptions. In: Vol 9841. Springer; 2016:391-408. doi:<a href=\"https://doi.org/10.1007/978-3-319-44618-9_21\">10.1007/978-3-319-44618-9_21</a>"},"alternative_title":["LNCS"],"author":[{"id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","full_name":"Fuchsbauer, Georg","last_name":"Fuchsbauer"},{"first_name":"Christian","full_name":"Hanser, Christian","last_name":"Hanser"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan"},{"last_name":"Slamanig","first_name":"Daniel","full_name":"Slamanig, Daniel"}],"type":"conference","day":"11","publisher":"Springer","status":"public","intvolume":"      9841","department":[{"_id":"KrPi"}],"quality_controlled":"1","page":"391 - 408","date_created":"2018-12-11T11:50:49Z","month":"08"},{"acknowledgement":"Research  supported  by  the  European  Research  Council,  ERC  starting  grant (259668-PSPC) and ERC consolidator grant (682815 - TOCNeT).","project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"259668","name":"Provable Security for Physical Cryptography"},{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"related_material":{"record":[{"status":"public","id":"83","relation":"dissertation_contains"}]},"ddc":["005","600"],"doi":"10.1007/978-3-319-39555-5_16","language":[{"iso":"eng"}],"conference":{"location":"Guildford, UK","start_date":"2016-06-19","end_date":"2016-06-22","name":"ACNS: Applied Cryptography and Network Security"},"title":"Offline witness encryption","ec_funded":1,"citation":{"ista":"Abusalah HM, Fuchsbauer G, Pietrzak KZ. 2016. Offline witness encryption. ACNS: Applied Cryptography and Network Security, LNCS, vol. 9696, 285–303.","ieee":"H. M. Abusalah, G. Fuchsbauer, and K. Z. Pietrzak, “Offline witness encryption,” presented at the ACNS: Applied Cryptography and Network Security, Guildford, UK, 2016, vol. 9696, pp. 285–303.","chicago":"Abusalah, Hamza M, Georg Fuchsbauer, and Krzysztof Z Pietrzak. “Offline Witness Encryption,” 9696:285–303. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-39555-5_16\">https://doi.org/10.1007/978-3-319-39555-5_16</a>.","mla":"Abusalah, Hamza M., et al. <i>Offline Witness Encryption</i>. Vol. 9696, Springer, 2016, pp. 285–303, doi:<a href=\"https://doi.org/10.1007/978-3-319-39555-5_16\">10.1007/978-3-319-39555-5_16</a>.","short":"H.M. Abusalah, G. Fuchsbauer, K.Z. Pietrzak, in:, Springer, 2016, pp. 285–303.","apa":"Abusalah, H. M., Fuchsbauer, G., &#38; Pietrzak, K. Z. (2016). Offline witness encryption (Vol. 9696, pp. 285–303). Presented at the ACNS: Applied Cryptography and Network Security, Guildford, UK: Springer. <a href=\"https://doi.org/10.1007/978-3-319-39555-5_16\">https://doi.org/10.1007/978-3-319-39555-5_16</a>","ama":"Abusalah HM, Fuchsbauer G, Pietrzak KZ. Offline witness encryption. In: Vol 9696. Springer; 2016:285-303. doi:<a href=\"https://doi.org/10.1007/978-3-319-39555-5_16\">10.1007/978-3-319-39555-5_16</a>"},"alternative_title":["LNCS"],"author":[{"first_name":"Hamza M","full_name":"Abusalah, Hamza M","last_name":"Abusalah","id":"40297222-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Fuchsbauer","full_name":"Fuchsbauer, Georg","first_name":"Georg","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"type":"conference","day":"09","publisher":"Springer","intvolume":"      9696","status":"public","department":[{"_id":"KrPi"}],"quality_controlled":"1","page":"285 - 303","date_created":"2018-12-11T11:50:50Z","month":"06","date_updated":"2023-09-07T12:30:22Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"year":"2016","has_accepted_license":"1","oa_version":"Submitted Version","publist_id":"6105","oa":1,"publication_status":"published","volume":9696,"pubrep_id":"765","file_date_updated":"2020-07-14T12:44:39Z","abstract":[{"lang":"eng","text":"Witness encryption (WE) was introduced by Garg et al. [GGSW13]. A WE scheme is defined for some NP language L and lets a sender encrypt messages relative to instances x. A ciphertext for x can be decrypted using w witnessing x ∈ L, but hides the message if x ∈ L. Garg et al. construct WE from multilinear maps and give another construction [GGH+13b] using indistinguishability obfuscation (iO) for circuits. Due to the reliance on such heavy tools, WE can cur- rently hardly be implemented on powerful hardware and will unlikely be realizable on constrained devices like smart cards any time soon. We construct a WE scheme where encryption is done by simply computing a Naor-Yung ciphertext (two CPA encryptions and a NIZK proof). To achieve this, our scheme has a setup phase, which outputs public parameters containing an obfuscated circuit (only required for decryption), two encryption keys and a common reference string (used for encryption). This setup need only be run once, and the parame- ters can be used for arbitrary many encryptions. Our scheme can also be turned into a functional WE scheme, where a message is encrypted w.r.t. a statement and a function f, and decryption with a witness w yields f (m, w). Our construction is inspired by the functional encryption scheme by Garg et al. and we prove (selective) security assuming iO and statistically simulation-sound NIZK. We give a construction of the latter in bilinear groups and combining it with ElGamal encryption, our ciphertexts are of size 1.3 kB at a 128-bit security level and can be computed on a smart card."}],"_id":"1229","date_published":"2016-06-09T00:00:00Z","file":[{"file_name":"IST-2017-765-v1+1_838.pdf","file_size":515000,"creator":"system","date_updated":"2020-07-14T12:44:39Z","access_level":"open_access","checksum":"34fa9ce681da845a1ba945ba3dc57867","content_type":"application/pdf","relation":"main_file","file_id":"5273","date_created":"2018-12-12T10:17:20Z"}]}]