[{"day":"24","publication":"Advances in Cryptology – EUROCRYPT 2019","isi":1,"year":"2019","date_published":"2019-04-24T00:00:00Z","doi":"10.1007/978-3-030-17656-3_10","date_created":"2020-01-30T09:26:14Z","page":"277-291","publisher":"Springer International Publishing","quality_controlled":"1","oa":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"apa":"Abusalah, H. M., Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2019). Reversible proofs of sequential work. In Advances in Cryptology – EUROCRYPT 2019 (Vol. 11477, pp. 277–291). Darmstadt, Germany: Springer International Publishing. https://doi.org/10.1007/978-3-030-17656-3_10","ama":"Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. Reversible proofs of sequential work. In: Advances in Cryptology – EUROCRYPT 2019. Vol 11477. Springer International Publishing; 2019:277-291. doi:10.1007/978-3-030-17656-3_10","short":"H.M. Abusalah, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, Advances in Cryptology – EUROCRYPT 2019, Springer International Publishing, 2019, pp. 277–291.","ieee":"H. M. Abusalah, C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “Reversible proofs of sequential work,” in Advances in Cryptology – EUROCRYPT 2019, Darmstadt, Germany, 2019, vol. 11477, pp. 277–291.","mla":"Abusalah, Hamza M., et al. “Reversible Proofs of Sequential Work.” Advances in Cryptology – EUROCRYPT 2019, vol. 11477, Springer International Publishing, 2019, pp. 277–91, doi:10.1007/978-3-030-17656-3_10.","ista":"Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2019. Reversible proofs of sequential work. Advances in Cryptology – EUROCRYPT 2019. International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol. 11477, 277–291.","chicago":"Abusalah, Hamza M, Chethan Kamath Hosdurg, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “Reversible Proofs of Sequential Work.” In Advances in Cryptology – EUROCRYPT 2019, 11477:277–91. Springer International Publishing, 2019. https://doi.org/10.1007/978-3-030-17656-3_10."},"title":"Reversible proofs of sequential work","author":[{"last_name":"Abusalah","full_name":"Abusalah, Hamza M","first_name":"Hamza M","id":"40297222-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan"},{"last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"last_name":"Walter","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"isi":["000483516200010"]},"article_processing_charge":"No","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783030176556","9783030176563"]},"publication_status":"published","volume":11477,"ec_funded":1,"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving a statement χ and a time parameter T computes a proof ϕ(χ,T) which is efficiently and publicly verifiable. The proof can be computed in T sequential steps, but not much less, even by a malicious party having large parallelism. A PoSW thus serves as a proof that T units of time have passed since χ\r\n\r\nwas received.\r\n\r\nPoSW were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical construction was only recently proposed by Cohen and Pietrzak [CP18].\r\n\r\nIn this work we construct a new simple PoSW in the random permutation model which is almost as simple and efficient as [CP18] but conceptually very different. Whereas the structure underlying [CP18] is a hash tree, our construction is based on skip lists and has the interesting property that computing the PoSW is a reversible computation.\r\nThe fact that the construction is reversible can potentially be used for new applications like constructing proofs of replication. We also show how to “embed” the sloth function of Lenstra and Weselowski [LW17] into our PoSW to get a PoSW where one additionally can verify correctness of the output much more efficiently than recomputing it (though recent constructions of “verifiable delay functions” subsume most of the applications this construction was aiming at)."}],"month":"04","intvolume":" 11477","scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/252"}],"date_updated":"2023-09-06T15:26:06Z","department":[{"_id":"KrPi"}],"_id":"7411","status":"public","type":"conference","conference":{"start_date":"2019-05-19","end_date":"2019-05-23","location":"Darmstadt, Germany","name":"International Conference on the Theory and Applications of Cryptographic Techniques"}},{"publisher":"Institute of Science and Technology Austria","oa":1,"day":"05","has_accepted_license":"1","year":"2018","doi":"10.15479/AT:ISTA:TH_1046","date_published":"2018-09-05T00:00:00Z","date_created":"2018-12-11T11:44:32Z","page":"59","project":[{"name":"Provable Security for Physical Cryptography","grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"apa":"Abusalah, H. M. (2018). Proof systems for sustainable decentralized cryptocurrencies. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:TH_1046","ama":"Abusalah HM. Proof systems for sustainable decentralized cryptocurrencies. 2018. doi:10.15479/AT:ISTA:TH_1046","short":"H.M. Abusalah, Proof Systems for Sustainable Decentralized Cryptocurrencies, Institute of Science and Technology Austria, 2018.","ieee":"H. M. Abusalah, “Proof systems for sustainable decentralized cryptocurrencies,” Institute of Science and Technology Austria, 2018.","mla":"Abusalah, Hamza M. Proof Systems for Sustainable Decentralized Cryptocurrencies. Institute of Science and Technology Austria, 2018, doi:10.15479/AT:ISTA:TH_1046.","ista":"Abusalah HM. 2018. Proof systems for sustainable decentralized cryptocurrencies. Institute of Science and Technology Austria.","chicago":"Abusalah, Hamza M. “Proof Systems for Sustainable Decentralized Cryptocurrencies.” Institute of Science and Technology Austria, 2018. https://doi.org/10.15479/AT:ISTA:TH_1046."},"title":"Proof systems for sustainable decentralized cryptocurrencies","publist_id":"7971","author":[{"first_name":"Hamza M","id":"40297222-F248-11E8-B48F-1D18A9856A87","full_name":"Abusalah, Hamza M","last_name":"Abusalah"}],"article_processing_charge":"No","oa_version":"Published Version","abstract":[{"lang":"eng","text":"A proof system is a protocol between a prover and a verifier over a common input in which an honest prover convinces the verifier of the validity of true statements. Motivated by the success of decentralized cryptocurrencies, exemplified by Bitcoin, the focus of this thesis will be on proof systems which found applications in some sustainable alternatives to Bitcoin, such as the Spacemint and Chia cryptocurrencies. In particular, we focus on proofs of space and proofs of sequential work.\r\nProofs of space (PoSpace) were suggested as more ecological, economical, and egalitarian alternative to the energy-wasteful proof-of-work mining of Bitcoin. However, the state-of-the-art constructions of PoSpace are based on sophisticated graph pebbling lower bounds, and are therefore complex. Moreover, when these PoSpace are used in cryptocurrencies like Spacemint, miners can only start mining after ensuring that a commitment to their space is already added in a special transaction to the blockchain. Proofs of sequential work (PoSW) are proof systems in which a prover, upon receiving a statement x and a time parameter T, computes a proof which convinces the verifier that T time units had passed since x was received. Whereas Spacemint assumes synchrony to retain some interesting Bitcoin dynamics, Chia requires PoSW with unique proofs, i.e., PoSW in which it is hard to come up with more than one accepting proof for any true statement. In this thesis we construct simple and practically-efficient PoSpace and PoSW. When using our PoSpace in cryptocurrencies, miners can start mining on the fly, like in Bitcoin, and unlike current constructions of PoSW, which either achieve efficient verification of sequential work, or faster-than-recomputing verification of correctness of proofs, but not both at the same time, ours achieve the best of these two worlds."}],"month":"09","alternative_title":["ISTA Thesis"],"file":[{"file_size":876241,"date_updated":"2020-07-14T12:48:11Z","creator":"dernst","file_name":"2018_Thesis_Abusalah.pdf","date_created":"2019-04-09T06:43:41Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"6245","checksum":"c4b5f7d111755d1396787f41886fc674"},{"access_level":"closed","relation":"source_file","content_type":"application/x-gzip","file_id":"6246","checksum":"0f382ac56b471c48fd907d63eb87dafe","creator":"dernst","date_updated":"2020-07-14T12:48:11Z","file_size":2029190,"date_created":"2019-04-09T06:43:41Z","file_name":"2018_Thesis_Abusalah_source.tar.gz"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2663-337X"]},"degree_awarded":"PhD","publication_status":"published","related_material":{"record":[{"id":"1229","status":"public","relation":"part_of_dissertation"},{"id":"1235","status":"public","relation":"part_of_dissertation"},{"id":"1236","status":"public","relation":"part_of_dissertation"},{"id":"559","status":"public","relation":"part_of_dissertation"}]},"ec_funded":1,"_id":"83","status":"public","pubrep_id":"1046","type":"dissertation","ddc":["004"],"supervisor":[{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"date_updated":"2023-09-07T12:30:23Z","department":[{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:48:11Z"},{"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"83"}]},"volume":10625,"ec_funded":1,"publication_identifier":{"isbn":["978-331970696-2"]},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2017/893.pdf"}],"month":"11","intvolume":" 10625","abstract":[{"text":"Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don’t give meaningful security guarantees due to existing time-memory trade-offs. In particular, Hellman showed that any permutation over a domain of size N can be inverted in time T by an algorithm that is given S bits of auxiliary information whenever (Formula presented). For functions Hellman gives a weaker attack with S2· T≈ N2 (e.g., S= T≈ N2/3). To prove lower bounds, one considers an adversary who has access to an oracle f: [ N] → [N] and can make T oracle queries. The best known lower bound is S· T∈ Ω(N) and holds for random functions and permutations. We construct functions that provably require more time and/or space to invert. Specifically, for any constant k we construct a function [N] → [N] that cannot be inverted unless Sk· T∈ Ω(Nk) (in particular, S= T≈ (Formula presented). Our construction does not contradict Hellman’s time-memory trade-off, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in N, which is sufficient for the PoS application. Our simplest construction is built from a random function oracle g: [N] × [N] → [ N] and a random permutation oracle f: [N] → N] and is defined as h(x) = g(x, x′) where f(x) = π(f(x′)) with π being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets S bits of auxiliary information, makes at most T oracle queries, and inverts h on an ϵ fraction of outputs must satisfy S2· T∈ Ω(ϵ2N2).","lang":"eng"}],"oa_version":"Submitted Version","department":[{"_id":"KrPi"}],"date_updated":"2023-09-07T12:30:22Z","type":"conference","conference":{"end_date":"2017-12-07","location":"Hong Kong, China","start_date":"2017-12-03","name":"ASIACRYPT: Theory and Applications of Cryptology and Information Security"},"status":"public","_id":"559","page":"357 - 379","doi":"10.1007/978-3-319-70697-9_13","date_published":"2017-11-18T00:00:00Z","date_created":"2018-12-11T11:47:10Z","year":"2017","day":"18","quality_controlled":"1","publisher":"Springer","oa":1,"publist_id":"7257","author":[{"last_name":"Abusalah","full_name":"Abusalah, Hamza M","first_name":"Hamza M","id":"40297222-F248-11E8-B48F-1D18A9856A87"},{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F","full_name":"Alwen, Joel F","last_name":"Alwen"},{"last_name":"Cohen","full_name":"Cohen, Bram","first_name":"Bram"},{"first_name":"Danylo","last_name":"Khilko","full_name":"Khilko, Danylo"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Leonid","full_name":"Reyzin, Leonid","last_name":"Reyzin"}],"title":"Beyond Hellman’s time-memory trade-offs with applications to proofs of space","citation":{"ista":"Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. 2017. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. ASIACRYPT: Theory and Applications of Cryptology and Information Security, LNCS, vol. 10625, 357–379.","chicago":"Abusalah, Hamza M, Joel F Alwen, Bram Cohen, Danylo Khilko, Krzysztof Z Pietrzak, and Leonid Reyzin. “Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space,” 10625:357–79. Springer, 2017. https://doi.org/10.1007/978-3-319-70697-9_13.","ama":"Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. In: Vol 10625. Springer; 2017:357-379. doi:10.1007/978-3-319-70697-9_13","apa":"Abusalah, H. M., Alwen, J. F., Cohen, B., Khilko, D., Pietrzak, K. Z., & Reyzin, L. (2017). Beyond Hellman’s time-memory trade-offs with applications to proofs of space (Vol. 10625, pp. 357–379). Presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China: Springer. https://doi.org/10.1007/978-3-319-70697-9_13","ieee":"H. M. Abusalah, J. F. Alwen, B. Cohen, D. Khilko, K. Z. Pietrzak, and L. Reyzin, “Beyond Hellman’s time-memory trade-offs with applications to proofs of space,” presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017, vol. 10625, pp. 357–379.","short":"H.M. Abusalah, J.F. Alwen, B. Cohen, D. Khilko, K.Z. Pietrzak, L. Reyzin, in:, Springer, 2017, pp. 357–379.","mla":"Abusalah, Hamza M., et al. Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space. Vol. 10625, Springer, 2017, pp. 357–79, doi:10.1007/978-3-319-70697-9_13."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}]},{"file_date_updated":"2020-07-14T12:44:39Z","department":[{"_id":"KrPi"}],"ddc":["005","600"],"date_updated":"2023-09-07T12:30:22Z","pubrep_id":"765","status":"public","conference":{"start_date":"2016-06-19","end_date":"2016-06-22","location":"Guildford, UK","name":"ACNS: Applied Cryptography and Network Security"},"type":"conference","_id":"1229","ec_funded":1,"volume":9696,"related_material":{"record":[{"id":"83","status":"public","relation":"dissertation_contains"}]},"language":[{"iso":"eng"}],"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"34fa9ce681da845a1ba945ba3dc57867","file_id":"5273","creator":"system","date_updated":"2020-07-14T12:44:39Z","file_size":515000,"date_created":"2018-12-12T10:17:20Z","file_name":"IST-2017-765-v1+1_838.pdf"}],"publication_status":"published","intvolume":" 9696","month":"06","alternative_title":["LNCS"],"scopus_import":1,"oa_version":"Submitted Version","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."}],"title":"Offline witness encryption","author":[{"full_name":"Abusalah, Hamza M","last_name":"Abusalah","id":"40297222-F248-11E8-B48F-1D18A9856A87","first_name":"Hamza M"},{"full_name":"Fuchsbauer, Georg","last_name":"Fuchsbauer","first_name":"Georg","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"}],"publist_id":"6105","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Abusalah HM, Fuchsbauer G, Pietrzak KZ. 2016. Offline witness encryption. ACNS: Applied Cryptography and Network Security, LNCS, vol. 9696, 285–303.","chicago":"Abusalah, Hamza M, Georg Fuchsbauer, and Krzysztof Z Pietrzak. “Offline Witness Encryption,” 9696:285–303. Springer, 2016. https://doi.org/10.1007/978-3-319-39555-5_16.","ama":"Abusalah HM, Fuchsbauer G, Pietrzak KZ. Offline witness encryption. In: Vol 9696. Springer; 2016:285-303. doi:10.1007/978-3-319-39555-5_16","apa":"Abusalah, H. M., Fuchsbauer, G., & Pietrzak, K. Z. (2016). Offline witness encryption (Vol. 9696, pp. 285–303). Presented at the ACNS: Applied Cryptography and Network Security, Guildford, UK: Springer. https://doi.org/10.1007/978-3-319-39555-5_16","short":"H.M. Abusalah, G. Fuchsbauer, K.Z. Pietrzak, in:, Springer, 2016, pp. 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.","mla":"Abusalah, Hamza M., et al. Offline Witness Encryption. Vol. 9696, Springer, 2016, pp. 285–303, doi:10.1007/978-3-319-39555-5_16."},"project":[{"name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"},{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"date_created":"2018-12-11T11:50:50Z","doi":"10.1007/978-3-319-39555-5_16","date_published":"2016-06-09T00:00:00Z","page":"285 - 303","day":"09","year":"2016","has_accepted_license":"1","oa":1,"publisher":"Springer","quality_controlled":"1","acknowledgement":"Research supported by the European Research Council, ERC starting grant (259668-PSPC) and ERC consolidator grant (682815 - TOCNeT)."},{"ddc":["005","600"],"date_updated":"2023-09-07T12:30:22Z","department":[{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:44:41Z","_id":"1236","status":"public","pubrep_id":"764","type":"conference","conference":{"name":"CT-RSA: Topics in Cryptology","start_date":"2016-02-29","location":"San Francisco, CA, USA","end_date":"2016-03-04"},"file":[{"file_size":495176,"date_updated":"2020-07-14T12:44:41Z","creator":"system","file_name":"IST-2017-764-v1+1_279.pdf","date_created":"2018-12-12T10:08:05Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"4664","checksum":"3851cee49933ae13b1272e516f213e13"}],"language":[{"iso":"eng"}],"publication_status":"published","volume":9610,"related_material":{"record":[{"status":"public","id":"83","relation":"dissertation_contains"}]},"ec_funded":1,"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"A constrained pseudorandom function F: K × X → Y for a family T ⊆ 2X of subsets of X is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a constrained key kS which allows to evaluate F (k, ·) on all inputs x ∈ S, while even given this key, the outputs on all inputs x ∉ S look random. At Asiacrypt’13 Boneh and Waters gave a construction which supports the most general set family so far. Its keys kc are defined for sets decided by boolean circuits C and enable evaluation of the PRF on any x ∈ X where C(x) = 1. In their construction the PRF input length and the size of the circuits C for which constrained keys can be computed must be fixed beforehand during key generation. We construct a constrained PRF that has an unbounded input length and whose constrained keys can be defined for any set recognized by a Turing machine. The only a priori bound we make is on the description size of the machines. We prove our construction secure assuming publiccoin differing-input obfuscation. As applications of our constrained PRF we build a broadcast encryption scheme where the number of potential receivers need not be fixed at setup (in particular, the length of the keys is independent of the number of parties) and the first identity-based non-interactive key exchange protocol with no bound on the number of parties that can agree on a shared key."}],"month":"02","intvolume":" 9610","scopus_import":1,"alternative_title":["LNCS"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Abusalah, Hamza M, Georg Fuchsbauer, and Krzysztof Z Pietrzak. “Constrained PRFs for Unbounded Inputs,” 9610:413–28. Springer, 2016. https://doi.org/10.1007/978-3-319-29485-8_24.","ista":"Abusalah HM, Fuchsbauer G, Pietrzak KZ. 2016. Constrained PRFs for unbounded inputs. CT-RSA: Topics in Cryptology, LNCS, vol. 9610, 413–428.","mla":"Abusalah, Hamza M., et al. Constrained PRFs for Unbounded Inputs. Vol. 9610, Springer, 2016, pp. 413–28, doi:10.1007/978-3-319-29485-8_24.","apa":"Abusalah, H. M., Fuchsbauer, G., & Pietrzak, K. Z. (2016). Constrained PRFs for unbounded inputs (Vol. 9610, pp. 413–428). Presented at the CT-RSA: Topics in Cryptology, San Francisco, CA, USA: Springer. https://doi.org/10.1007/978-3-319-29485-8_24","ama":"Abusalah HM, Fuchsbauer G, Pietrzak KZ. Constrained PRFs for unbounded inputs. In: Vol 9610. Springer; 2016:413-428. doi:10.1007/978-3-319-29485-8_24","short":"H.M. Abusalah, G. Fuchsbauer, K.Z. Pietrzak, in:, Springer, 2016, pp. 413–428.","ieee":"H. M. Abusalah, G. Fuchsbauer, and K. Z. Pietrzak, “Constrained PRFs for unbounded inputs,” presented at the CT-RSA: Topics in Cryptology, San Francisco, CA, USA, 2016, vol. 9610, pp. 413–428."},"title":"Constrained PRFs for unbounded inputs","publist_id":"6097","author":[{"full_name":"Abusalah, Hamza M","last_name":"Abusalah","first_name":"Hamza M","id":"40297222-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Fuchsbauer, Georg","last_name":"Fuchsbauer","first_name":"Georg","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"}],"project":[{"call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668","name":"Provable Security for Physical Cryptography"}],"day":"02","has_accepted_license":"1","year":"2016","doi":"10.1007/978-3-319-29485-8_24","date_published":"2016-02-02T00:00:00Z","date_created":"2018-12-11T11:50:52Z","page":"413 - 428","acknowledgement":"Supported by the European Research Council, ERC Starting Grant (259668-PSPC).","publisher":"Springer","quality_controlled":"1","oa":1},{"conference":{"name":"ACNS: Applied Cryptography and Network Security","start_date":"2016-06-19","location":"Guildford, UK","end_date":"2016-06-22"},"type":"conference","status":"public","_id":"1235","department":[{"_id":"KrPi"}],"date_updated":"2023-09-07T12:30:22Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/279.pdf"}],"alternative_title":["LNCS"],"scopus_import":1,"intvolume":" 9696","month":"01","abstract":[{"text":"A constrained pseudorandom function (CPRF) F: K×X → Y for a family T of subsets of χ is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a short constrained key kS, which allows to evaluate F(k, ·) on all inputs x ∈ S, while the outputs on all inputs x /∈ S look random even given kS. Abusalah et al. recently constructed the first constrained PRF for inputs of arbitrary length whose sets S are decided by Turing machines. They use their CPRF to build broadcast encryption and the first ID-based non-interactive key exchange for an unbounded number of users. Their constrained keys are obfuscated circuits and are therefore large. In this work we drastically reduce the key size and define a constrained key for a Turing machine M as a short signature on M. For this, we introduce a new signature primitive with constrained signing keys that let one only sign certain messages, while forging a signature on others is hard even when knowing the coins for key generation.","lang":"eng"}],"oa_version":"Submitted Version","ec_funded":1,"volume":9696,"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"83"}]},"publication_status":"published","language":[{"iso":"eng"}],"project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Provable Security for Physical Cryptography","grant_number":"259668"},{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"author":[{"first_name":"Hamza M","id":"40297222-F248-11E8-B48F-1D18A9856A87","full_name":"Abusalah, Hamza M","last_name":"Abusalah"},{"id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","first_name":"Georg","full_name":"Fuchsbauer, Georg","last_name":"Fuchsbauer"}],"publist_id":"6098","title":"Constrained PRFs for unbounded inputs with short keys","citation":{"mla":"Abusalah, Hamza M., and Georg Fuchsbauer. Constrained PRFs for Unbounded Inputs with Short Keys. Vol. 9696, Springer, 2016, pp. 445–63, doi:10.1007/978-3-319-39555-5_24.","ieee":"H. M. Abusalah and G. Fuchsbauer, “Constrained PRFs for unbounded inputs with short keys,” presented at the ACNS: Applied Cryptography and Network Security, Guildford, UK, 2016, vol. 9696, pp. 445–463.","short":"H.M. Abusalah, G. Fuchsbauer, in:, Springer, 2016, pp. 445–463.","apa":"Abusalah, H. M., & Fuchsbauer, G. (2016). Constrained PRFs for unbounded inputs with short keys (Vol. 9696, pp. 445–463). Presented at the ACNS: Applied Cryptography and Network Security, Guildford, UK: Springer. https://doi.org/10.1007/978-3-319-39555-5_24","ama":"Abusalah HM, Fuchsbauer G. Constrained PRFs for unbounded inputs with short keys. In: Vol 9696. Springer; 2016:445-463. doi:10.1007/978-3-319-39555-5_24","chicago":"Abusalah, Hamza M, and Georg Fuchsbauer. “Constrained PRFs for Unbounded Inputs with Short Keys,” 9696:445–63. Springer, 2016. https://doi.org/10.1007/978-3-319-39555-5_24.","ista":"Abusalah HM, Fuchsbauer G. 2016. Constrained PRFs for unbounded inputs with short keys. ACNS: Applied Cryptography and Network Security, LNCS, vol. 9696, 445–463."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa":1,"quality_controlled":"1","publisher":"Springer","acknowledgement":"H. Abusalah—Research supported by the European Research Council, ERC starting grant (259668-PSPC) and ERC consolidator grant (682815 - TOCNeT).","page":"445 - 463","date_created":"2018-12-11T11:50:52Z","doi":"10.1007/978-3-319-39555-5_24","date_published":"2016-01-01T00:00:00Z","year":"2016","day":"01"}]