[{"fulldoi":"https://doi.org/10.1007/978-3-030-75539-3_17","abstract":[{"text":"Automated contract tracing aims at supporting manual contact tracing during pandemics by alerting users of encounters with infected people. There are currently many proposals for protocols (like the “decentralized” DP-3T and PACT or the “centralized” ROBERT and DESIRE) to be run on mobile phones, where the basic idea is to regularly broadcast (using low energy Bluetooth) some values, and at the same time store (a function of) incoming messages broadcasted by users in their proximity. In the existing proposals one can trigger false positives on a massive scale by an “inverse-Sybil” attack, where a large number of devices (malicious users or hacked phones) pretend to be the same user, such that later, just a single person needs to be diagnosed (and allowed to upload) to trigger an alert for all users who were in proximity to any of this large group of devices.\r\n\r\nWe propose the first protocols that do not succumb to such attacks assuming the devices involved in the attack do not constantly communicate, which we observe is a necessary assumption. The high level idea of the protocols is to derive the values to be broadcasted by a hash chain, so that two (or more) devices who want to launch an inverse-Sybil attack will not be able to connect their respective chains and thus only one of them will be able to upload. Our protocols also achieve security against replay, belated replay, and one of them even against relay attacks.","lang":"eng"}],"day":"11","date_updated":"2026-09-07T11:37:54Z","status":"public","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"month":"05","language":[{"iso":"eng"}],"type":"conference","article_processing_charge":"No","volume":12704,"date_created":"2021-08-08T22:01:30Z","date_published":"2021-05-11T00:00:00Z","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030755386"]},"title":"Inverse-Sybil attacks in automated contact tracing","_id":"9826","acknowledgement":"Guillermo Pascual-Perez and Michelle Yeo were funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie Grant Agreement No. 665385; the remaining contributors to this project have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","conference":{"location":"Virtual Event","name":"CT-RSA: Cryptographers’ Track at the RSA Conference","end_date":"2021-05-20","start_date":"2021-05-17"},"main_file_link":[{"url":"https://eprint.iacr.org/2020/670","open_access":"1"}],"oa_version":"Submitted Version","publication":"Topics in Cryptology – CT-RSA 2021","author":[{"last_name":"Auerbach","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","full_name":"Auerbach, Benedikt","first_name":"Benedikt","orcid":"0000-0002-7553-6606"},{"full_name":"Chakraborty, Suvradip","first_name":"Suvradip","last_name":"Chakraborty","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen"},{"last_name":"Pascual Perez","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","orcid":"0000-0001-8630-415X"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"},{"orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","last_name":"Walter","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0009-0001-3676-4809","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X"}],"scopus_import":"1","citation":{"short":"B. Auerbach, S. Chakraborty, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, M.X. Yeo, in:, Topics in Cryptology – CT-RSA 2021, Springer Nature, 2021, pp. 399–421.","ama":"Auerbach B, Chakraborty S, Klein K, et al. Inverse-Sybil attacks in automated contact tracing. In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer Nature; 2021:399-421. doi:10.1007/978-3-030-75539-3_17","mla":"Auerbach, Benedikt, et al. “Inverse-Sybil Attacks in Automated Contact Tracing.” Topics in Cryptology – CT-RSA 2021, vol. 12704, Springer Nature, 2021, pp. 399–421, doi:10.1007/978-3-030-75539-3_17.","chicago":"Auerbach, Benedikt, Suvradip Chakraborty, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, Michael Walter, and Michelle X Yeo. “Inverse-Sybil Attacks in Automated Contact Tracing.” In Topics in Cryptology – CT-RSA 2021, 12704:399–421. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_17.","ieee":"B. Auerbach et al., “Inverse-Sybil attacks in automated contact tracing,” in Topics in Cryptology – CT-RSA 2021, Virtual Event, 2021, vol. 12704, pp. 399–421.","apa":"Auerbach, B., Chakraborty, S., Klein, K., Pascual Perez, G., Pietrzak, K. Z., Walter, M., & Yeo, M. X. (2021). Inverse-Sybil attacks in automated contact tracing. In Topics in Cryptology – CT-RSA 2021 (Vol. 12704, pp. 399–421). Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_17","ista":"Auerbach B, Chakraborty S, Klein K, Pascual Perez G, Pietrzak KZ, Walter M, Yeo MX. 2021. Inverse-Sybil attacks in automated contact tracing. Topics in Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’ Track at the RSA Conference, LNCS, vol. 12704, 399–421."},"publication_status":"published","corr_author":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","quality_controlled":"1","page":"399-421","ec_funded":1,"year":"2021","doi":"10.1007/978-3-030-75539-3_17","alternative_title":["LNCS"],"publisher":"Springer Nature","intvolume":" 12704","project":[{"name":"International IST Doctoral Program","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"oa":1},{"language":[{"iso":"eng"}],"month":"08","status":"public","department":[{"_id":"KrPi"},{"_id":"DaAl"}],"day":"26","date_updated":"2026-09-07T14:12:38Z","abstract":[{"lang":"eng","text":"While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open."}],"fulldoi":"https://doi.org/10.1109/sp40001.2021.00035","date_created":"2021-09-27T13:46:27Z","article_processing_charge":"No","type":"conference","title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","date_published":"2021-08-26T00:00:00Z","external_id":{"isi":["001316065000016"]},"scopus_import":"1","author":[{"full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482"},{"orcid":"0009-0006-6812-7317","full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","last_name":"Kamath Hosdurg"},{"first_name":"Margarita","last_name":"Capretto","full_name":"Capretto, Margarita"},{"last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","first_name":"Miguel","full_name":"Cueto Noval, Miguel","orcid":"0000-0002-2505-4246"},{"full_name":"Markov, Ilia","last_name":"Markov","first_name":"Ilia","id":"D0CF4148-C985-11E9-8066-0BDEE5697425"},{"full_name":"Yeo, Michelle X","first_name":"Michelle X","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0001-3676-4809"},{"full_name":"Alwen, Joel F","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"}],"publication":"2021 IEEE Symposium on Security and Privacy ","main_file_link":[{"url":"https://eprint.iacr.org/2019/1489","open_access":"1"}],"oa_version":"Preprint","conference":{"end_date":"2021-05-27","start_date":"2021-05-24","location":"San Francisco, CA, United States","name":"SP: Symposium on Security and Privacy"},"acknowledgement":"The first three authors contributed equally to this work. Funded by the European Research Council (ERC) under the European Union’s Horizon2020 research and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.665385.","_id":"10049","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","publication_status":"published","citation":{"short":"K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M. Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–284.","ama":"Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In: 2021 IEEE Symposium on Security and Privacy . IEEE; 2021:268-284. doi:10.1109/sp40001.2021.00035","mla":"Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–84, doi:10.1109/sp40001.2021.00035.","chicago":"Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo, Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” In 2021 IEEE Symposium on Security and Privacy , 268–84. IEEE, 2021. https://doi.org/10.1109/sp40001.2021.00035.","ieee":"K. Klein et al., “Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement,” in 2021 IEEE Symposium on Security and Privacy , San Francisco, CA, United States, 2021, pp. 268–284.","apa":"Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M., Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In 2021 IEEE Symposium on Security and Privacy (pp. 268–284). San Francisco, CA, United States: IEEE. https://doi.org/10.1109/sp40001.2021.00035","ista":"Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium on Security and Privacy . SP: Symposium on Security and Privacy, 268–284."},"doi":"10.1109/sp40001.2021.00035","year":"2021","page":"268-284","ec_funded":1,"quality_controlled":"1","publisher":"IEEE","related_material":{"record":[{"status":"public","id":"10035","relation":"dissertation_contains"},{"relation":"dissertation_contains","id":"18088","status":"public"}]},"oa":1,"project":[{"call_identifier":"H2020","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program"},{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"isi":1},{"abstract":[{"lang":"eng","text":"For 1≤m≤n, we consider a natural m-out-of-n multi-instance scenario for a public-key encryption (PKE) scheme. An adversary, given n independent instances of PKE, wins if he breaks at least m out of the n instances. In this work, we are interested in the scaling factor of PKE schemes, SF, which measures how well the difficulty of breaking m out of the n instances scales in m. That is, a scaling factor SF=ℓ indicates that breaking m out of n instances is at least ℓ times more difficult than breaking one single instance. A PKE scheme with small scaling factor hence provides an ideal target for mass surveillance. In fact, the Logjam attack (CCS 2015) implicitly exploited, among other things, an almost constant scaling factor of ElGamal over finite fields (with shared group parameters).\r\n\r\nFor Hashed ElGamal over elliptic curves, we use the generic group model to argue that the scaling factor depends on the scheme's granularity. In low granularity, meaning each public key contains its independent group parameter, the scheme has optimal scaling factor SF=m; In medium and high granularity, meaning all public keys share the same group parameter, the scheme still has a reasonable scaling factor SF=√m. Our findings underline that instantiating ElGamal over elliptic curves should be preferred to finite fields in a multi-instance scenario.\r\n\r\nAs our main technical contribution, we derive new generic-group lower bounds of Ω(√(mp)) on the difficulty of solving both the m-out-of-n Gap Discrete Logarithm and the m-out-of-n Gap Computational Diffie-Hellman problem over groups of prime order p, extending a recent result by Yun (EUROCRYPT 2015). We establish the lower bound by studying the hardness of a related computational problem which we call the search-by-hypersurface problem."}],"fulldoi":"https://doi.org/10.1007/978-3-030-45727-3_16","day":"01","date_updated":"2026-04-16T10:21:02Z","department":[{"_id":"KrPi"}],"status":"public","month":"05","language":[{"iso":"eng"}],"type":"conference","article_processing_charge":"No","date_created":"2020-06-15T07:13:37Z","volume":12107,"date_published":"2020-05-01T00:00:00Z","title":"Everybody’s a target: Scalability in public-key encryption","publication_identifier":{"isbn":["9783030457266"],"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["9783030457273"]},"_id":"7966","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/364"}],"oa_version":"Submitted Version","conference":{"name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2020-05-11","end_date":"2020-05-15"},"external_id":{"isi":["000828688000016"]},"publication":"Advances in Cryptology – EUROCRYPT 2020","author":[{"orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach","first_name":"Benedikt"},{"last_name":"Giacon","first_name":"Federico","full_name":"Giacon, Federico"},{"first_name":"Eike","full_name":"Kiltz, Eike","last_name":"Kiltz"}],"scopus_import":"1","publication_status":"published","citation":{"short":"B. Auerbach, F. Giacon, E. Kiltz, in:, Advances in Cryptology – EUROCRYPT 2020, Springer Nature, 2020, pp. 475–506.","ama":"Auerbach B, Giacon F, Kiltz E. Everybody’s a target: Scalability in public-key encryption. In: Advances in Cryptology – EUROCRYPT 2020. Vol 12107. Springer Nature; 2020:475-506. doi:10.1007/978-3-030-45727-3_16","apa":"Auerbach, B., Giacon, F., & Kiltz, E. (2020). Everybody’s a target: Scalability in public-key encryption. In Advances in Cryptology – EUROCRYPT 2020 (Vol. 12107, pp. 475–506). Springer Nature. https://doi.org/10.1007/978-3-030-45727-3_16","ieee":"B. Auerbach, F. Giacon, and E. Kiltz, “Everybody’s a target: Scalability in public-key encryption,” in Advances in Cryptology – EUROCRYPT 2020, 2020, vol. 12107, pp. 475–506.","ista":"Auerbach B, Giacon F, Kiltz E. 2020. Everybody’s a target: Scalability in public-key encryption. Advances in Cryptology – EUROCRYPT 2020. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 12107, 475–506.","mla":"Auerbach, Benedikt, et al. “Everybody’s a Target: Scalability in Public-Key Encryption.” Advances in Cryptology – EUROCRYPT 2020, vol. 12107, Springer Nature, 2020, pp. 475–506, doi:10.1007/978-3-030-45727-3_16.","chicago":"Auerbach, Benedikt, Federico Giacon, and Eike Kiltz. “Everybody’s a Target: Scalability in Public-Key Encryption.” In Advances in Cryptology – EUROCRYPT 2020, 12107:475–506. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45727-3_16."},"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","quality_controlled":"1","year":"2020","doi":"10.1007/978-3-030-45727-3_16","page":"475-506","ec_funded":1,"alternative_title":["LNCS"],"intvolume":" 12107","publisher":"Springer Nature","isi":1,"oa":1,"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}]},{"volume":12110,"date_created":"2020-09-06T22:01:13Z","type":"conference","article_processing_charge":"No","status":"public","department":[{"_id":"KrPi"}],"month":"05","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Discrete Gaussian distributions over lattices are central to lattice-based cryptography, and to the computational and mathematical aspects of lattices more broadly. The literature contains a wealth of useful theorems about the behavior of discrete Gaussians under convolutions and related operations. Yet despite their structural similarities, most of these theorems are formally incomparable, and their proofs tend to be monolithic and written nearly “from scratch,” making them unnecessarily hard to verify, understand, and extend.\r\nIn this work we present a modular framework for analyzing linear operations on discrete Gaussian distributions. The framework abstracts away the particulars of Gaussians, and usually reduces proofs to the choice of appropriate linear transformations and elementary linear algebra. To showcase the approach, we establish several general properties of discrete Gaussians, and show how to obtain all prior convolution theorems (along with some new ones) as straightforward corollaries. As another application, we describe a self-reduction for Learning With Errors (LWE) that uses a fixed number of samples to generate an unlimited number of additional ones (having somewhat larger error). The distinguishing features of our reduction are its simple analysis in our framework, and its exclusive use of discrete Gaussians without any loss in parameters relative to a prior mixed discrete-and-continuous approach.\r\nAs a contribution of independent interest, for subgaussian random matrices we prove a singular value concentration bound with explicitly stated constants, and we give tighter heuristics for specific distributions that are commonly used for generating lattice trapdoors. These bounds yield improvements in the concrete bit-security estimates for trapdoor lattice cryptosystems."}],"fulldoi":"https://doi.org/10.1007/978-3-030-45374-9_21","day":"15","date_updated":"2026-04-16T09:32:27Z","external_id":{"isi":["001299210200021"]},"publication":"23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography","scopus_import":"1","author":[{"last_name":"Genise","full_name":"Genise, Nicholas","first_name":"Nicholas"},{"first_name":"Daniele","last_name":"Micciancio","full_name":"Micciancio, Daniele"},{"first_name":"Chris","last_name":"Peikert","full_name":"Peikert, Chris"},{"orcid":"0000-0003-3186-2482","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","full_name":"Walter, Michael"}],"_id":"8339","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2020/337"}],"conference":{"start_date":"2020-05-04","end_date":"2020-05-07","name":"PKC: Public-Key Cryptography","location":"Edinburgh, United Kingdom"},"title":"Improved discrete Gaussian and subgaussian analysis for lattice cryptography","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030453732"]},"date_published":"2020-05-15T00:00:00Z","doi":"10.1007/978-3-030-45374-9_21","year":"2020","ec_funded":1,"page":"623-651","quality_controlled":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_status":"published","citation":{"short":"N. Genise, D. Micciancio, C. Peikert, M. Walter, in:, 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, Springer Nature, 2020, pp. 623–651.","ama":"Genise N, Micciancio D, Peikert C, Walter M. Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In: 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography. Vol 12110. Springer Nature; 2020:623-651. doi:10.1007/978-3-030-45374-9_21","apa":"Genise, N., Micciancio, D., Peikert, C., & Walter, M. (2020). Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography (Vol. 12110, pp. 623–651). Edinburgh, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-45374-9_21","ieee":"N. Genise, D. Micciancio, C. Peikert, and M. Walter, “Improved discrete Gaussian and subgaussian analysis for lattice cryptography,” in 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, Edinburgh, United Kingdom, 2020, vol. 12110, pp. 623–651.","ista":"Genise N, Micciancio D, Peikert C, Walter M. 2020. Improved discrete Gaussian and subgaussian analysis for lattice cryptography. 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography, LNCS, vol. 12110, 623–651.","mla":"Genise, Nicholas, et al. “Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.” 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, vol. 12110, Springer Nature, 2020, pp. 623–51, doi:10.1007/978-3-030-45374-9_21.","chicago":"Genise, Nicholas, Daniele Micciancio, Chris Peikert, and Michael Walter. “Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.” In 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, 12110:623–51. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45374-9_21."},"isi":1,"project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"oa":1,"intvolume":" 12110","publisher":"Springer Nature","alternative_title":["LNCS"]},{"quality_controlled":"1","ec_funded":1,"page":"3-15","year":"2020","doi":"10.1007/978-3-030-65277-7_1","citation":{"apa":"Pietrzak, K. Z. (2020). Delayed authentication: Preventing replay and relay attacks in private contact tracing. In Progress in Cryptology (Vol. 12578, pp. 3–15). Bangalore, India: Springer Nature. https://doi.org/10.1007/978-3-030-65277-7_1","ieee":"K. Z. Pietrzak, “Delayed authentication: Preventing replay and relay attacks in private contact tracing,” in Progress in Cryptology, Bangalore, India, 2020, vol. 12578, pp. 3–15.","ista":"Pietrzak KZ. 2020. Delayed authentication: Preventing replay and relay attacks in private contact tracing. Progress in Cryptology. INDOCRYPT: International Conference on Cryptology in IndiaLNCS vol. 12578, 3–15.","mla":"Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing.” Progress in Cryptology, vol. 12578, Springer Nature, 2020, pp. 3–15, doi:10.1007/978-3-030-65277-7_1.","chicago":"Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing.” In Progress in Cryptology, 12578:3–15. LNCS. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-65277-7_1.","short":"K.Z. Pietrzak, in:, Progress in Cryptology, Springer Nature, 2020, pp. 3–15.","ama":"Pietrzak KZ. Delayed authentication: Preventing replay and relay attacks in private contact tracing. In: Progress in Cryptology. Vol 12578. LNCS. Springer Nature; 2020:3-15. doi:10.1007/978-3-030-65277-7_1"},"publication_status":"published","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"oa":1,"isi":1,"publisher":"Springer Nature","intvolume":" 12578","series_title":"LNCS","article_processing_charge":"No","type":"conference","volume":12578,"date_created":"2021-01-03T23:01:23Z","day":"08","date_updated":"2026-04-16T09:33:26Z","fulldoi":"https://doi.org/10.1007/978-3-030-65277-7_1","abstract":[{"lang":"eng","text":"Currently several projects aim at designing and implementing protocols for privacy preserving automated contact tracing to help fight the current pandemic. Those proposal are quite similar, and in their most basic form basically propose an app for mobile phones which broadcasts frequently changing pseudorandom identifiers via (low energy) Bluetooth, and at the same time, the app stores IDs broadcast by phones in its proximity. Only if a user is tested positive, they upload either the beacons they did broadcast (which is the case in decentralized proposals as DP-3T, east and west coast PACT or Covid watch) or received (as in Popp-PT or ROBERT) during the last two weeks or so.\r\n\r\nVaudenay [eprint 2020/399] observes that this basic scheme (he considers the DP-3T proposal) succumbs to relay and even replay attacks, and proposes more complex interactive schemes which prevent those attacks without giving up too many privacy aspects. Unfortunately interaction is problematic for this application for efficiency and security reasons. The countermeasures that have been suggested so far are either not practical or give up on key privacy aspects. We propose a simple non-interactive variant of the basic protocol that\r\n(security) Provably prevents replay and (if location data is available) relay attacks.\r\n(privacy) The data of all parties (even jointly) reveals no information on the location or time where encounters happened.\r\n(efficiency) The broadcasted message can fit into 128 bits and uses only basic crypto (commitments and secret key authentication).\r\n\r\nTowards this end we introduce the concept of “delayed authentication”, which basically is a message authentication code where verification can be done in two steps, where the first doesn’t require the key, and the second doesn’t require the message."}],"language":[{"iso":"eng"}],"month":"12","department":[{"_id":"KrPi"}],"status":"public","conference":{"end_date":"2020-12-16","start_date":"2020-12-13","location":"Bangalore, India","name":"INDOCRYPT: International Conference on Cryptology in India"},"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2020/418"}],"_id":"8987","author":[{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"publication":"Progress in Cryptology","scopus_import":"1","external_id":{"isi":["000927592800001"]},"date_published":"2020-12-08T00:00:00Z","publication_identifier":{"isbn":["9783030652760"],"issn":["0302-9743"],"eissn":["1611-3349"]},"title":"Delayed authentication: Preventing replay and relay attacks in private contact tracing"},{"intvolume":" 12171","OA_type":"green","publisher":"Springer Nature","alternative_title":["LNCS"],"isi":1,"OA_place":"repository","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","citation":{"ama":"Chakraborty S, Dziembowski S, Nielsen JB. Reverse firewalls for actively secure MPCs. In: Advances in Cryptology – CRYPTO 2020. Vol 12171. Springer Nature; 2020:732-762. doi:10.1007/978-3-030-56880-1_26","short":"S. Chakraborty, S. Dziembowski, J.B. Nielsen, in:, Advances in Cryptology – CRYPTO 2020, Springer Nature, 2020, pp. 732–762.","chicago":"Chakraborty, Suvradip, Stefan Dziembowski, and Jesper Buus Nielsen. “Reverse Firewalls for Actively Secure MPCs.” In Advances in Cryptology – CRYPTO 2020, 12171:732–62. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-56880-1_26.","mla":"Chakraborty, Suvradip, et al. “Reverse Firewalls for Actively Secure MPCs.” Advances in Cryptology – CRYPTO 2020, vol. 12171, Springer Nature, 2020, pp. 732–62, doi:10.1007/978-3-030-56880-1_26.","ista":"Chakraborty S, Dziembowski S, Nielsen JB. 2020. Reverse firewalls for actively secure MPCs. Advances in Cryptology – CRYPTO 2020. CRYPTO: Annual International Cryptology Conference, LNCS, vol. 12171, 732–762.","ieee":"S. Chakraborty, S. Dziembowski, and J. B. Nielsen, “Reverse firewalls for actively secure MPCs,” in Advances in Cryptology – CRYPTO 2020, Santa Barbara, CA, United States, 2020, vol. 12171, pp. 732–762.","apa":"Chakraborty, S., Dziembowski, S., & Nielsen, J. B. (2020). Reverse firewalls for actively secure MPCs. In Advances in Cryptology – CRYPTO 2020 (Vol. 12171, pp. 732–762). Santa Barbara, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-030-56880-1_26"},"doi":"10.1007/978-3-030-56880-1_26","year":"2020","ec_funded":1,"page":"732-762","quality_controlled":"1","title":"Reverse firewalls for actively secure MPCs","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030568795"]},"date_published":"2020-08-10T00:00:00Z","cryptoeprintid":1,"external_id":{"isi":["001415325700026"],"cryptoeprintid":["2019/1317"]},"publication":"Advances in Cryptology – CRYPTO 2020","author":[{"full_name":"Chakraborty, Suvradip","last_name":"Chakraborty","first_name":"Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"full_name":"Dziembowski, Stefan","last_name":"Dziembowski","first_name":"Stefan"},{"first_name":"Jesper Buus","last_name":"Nielsen","full_name":"Nielsen, Jesper Buus"}],"scopus_import":"1","acknowledgement":"We would like to thank the anonymous reviewers for their helpful comments and suggestions. The work was initiated while the first author was in IIT Madras, India. Part of this work was done while the author was visiting the University of Warsaw. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT) and from the Foundation for Polish Science under grant TEAM/2016-1/4 founded within the UE 2014–2020 Smart Growth Operational Program. The last author was supported by the Independent Research Fund Denmark project BETHE and the Concordium Blockchain Research Center, Aarhus University, Denmark.","_id":"8322","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1317"}],"oa_version":"Preprint","conference":{"location":"Santa Barbara, CA, United States","name":"CRYPTO: Annual International Cryptology Conference","end_date":"2020-08-21","start_date":"2020-08-17"},"status":"public","department":[{"_id":"KrPi"}],"language":[{"iso":"eng"}],"month":"08","abstract":[{"lang":"eng","text":"Reverse firewalls were introduced at Eurocrypt 2015 by Miro-nov and Stephens-Davidowitz, as a method for protecting cryptographic protocols against attacks on the devices of the honest parties. In a nutshell: a reverse firewall is placed outside of a device and its goal is to “sanitize” the messages sent by it, in such a way that a malicious device cannot leak its secrets to the outside world. It is typically assumed that the cryptographic devices are attacked in a “functionality-preserving way” (i.e. informally speaking, the functionality of the protocol remains unchanged under this attacks). In their paper, Mironov and Stephens-Davidowitz construct a protocol for passively-secure two-party computations with firewalls, leaving extension of this result to stronger models as an open question.\r\nIn this paper, we address this problem by constructing a protocol for secure computation with firewalls that has two main advantages over the original protocol from Eurocrypt 2015. Firstly, it is a multiparty computation protocol (i.e. it works for an arbitrary number n of the parties, and not just for 2). Secondly, it is secure in much stronger corruption settings, namely in the active corruption model. More precisely: we consider an adversary that can fully corrupt up to 𝑛−1 parties, while the remaining parties are corrupt in a functionality-preserving way.\r\nOur core techniques are: malleable commitments and malleable non-interactive zero-knowledge, which in particular allow us to create a novel protocol for multiparty augmented coin-tossing into the well with reverse firewalls (that is based on a protocol of Lindell from Crypto 2001)."}],"fulldoi":"https://doi.org/10.1007/978-3-030-56880-1_26","day":"10","date_updated":"2026-07-28T12:45:44Z","date_created":"2020-08-30T22:01:12Z","volume":12171,"article_processing_charge":"No","type":"conference"},{"corr_author":"1","citation":{"ama":"Kamath Hosdurg C. On the average-case hardness of total search problems. 2020. doi:10.15479/AT:ISTA:7896","short":"C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020.","chicago":"Kamath Hosdurg, Chethan. “On the Average-Case Hardness of Total Search Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7896.","mla":"Kamath Hosdurg, Chethan. On the Average-Case Hardness of Total Search Problems. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7896.","ista":"Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.","ieee":"C. Kamath Hosdurg, “On the average-case hardness of total search problems,” Institute of Science and Technology Austria, 2020.","apa":"Kamath Hosdurg, C. (2020). On the average-case hardness of total search problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7896"},"publication_status":"published","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","ddc":["000"],"degree_awarded":"PhD","ec_funded":1,"page":"126","year":"2020","doi":"10.15479/AT:ISTA:7896","file":[{"access_level":"open_access","creator":"dernst","file_id":"7897","checksum":"b39e2e1c376f5819b823fb7077491c64","date_updated":"2020-07-14T12:48:04Z","file_name":"2020_Thesis_Kamath.pdf","date_created":"2020-05-26T14:08:13Z","file_size":1622742,"relation":"main_file","content_type":"application/pdf"},{"date_updated":"2020-07-14T12:48:04Z","file_name":"Thesis_Kamath.zip","creator":"dernst","access_level":"closed","checksum":"8b26ba729c1a85ac6bea775f5d73cdc7","file_id":"7898","file_size":15301529,"relation":"source_file","content_type":"application/x-zip-compressed","date_created":"2020-05-26T14:08:23Z"}],"alternative_title":["ISTA Thesis"],"publisher":"Institute of Science and Technology Austria","related_material":{"record":[{"status":"public","id":"6677","relation":"part_of_dissertation"}]},"project":[{"call_identifier":"FP7","name":"Provable Security for Physical Cryptography","grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425"},{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"oa":1,"supervisor":[{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z"}],"OA_place":"publisher","date_updated":"2026-07-30T13:43:53Z","day":"25","fulldoi":"https://doi.org/10.15479/AT:ISTA:7896","doi_confirm":"1","abstract":[{"lang":"eng","text":"A search problem lies in the complexity class FNP if a solution to the given instance of the problem can be verified efficiently. The complexity class TFNP consists of all search problems in FNP that are total in the sense that a solution is guaranteed to exist. TFNP contains a host of interesting problems from fields such as algorithmic game theory, computational topology, number theory and combinatorics. Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead, one studies its syntactic subclasses which are defined based on the combinatorial principle used to argue totality. Of particular interest is the subclass PPAD, which contains important problems\r\nlike computing Nash equilibrium for bimatrix games and computational counterparts of several fixed-point theorems as complete. In the thesis, we undertake the study of averagecase hardness of TFNP, and in particular its subclass PPAD.\r\nAlmost nothing was known about average-case hardness of PPAD before a series of recent results showed how to achieve it using a cryptographic primitive called program obfuscation.\r\nHowever, it is currently not known how to construct program obfuscation from standard cryptographic assumptions. Therefore, it is desirable to relax the assumption under which average-case hardness of PPAD can be shown. In the thesis we take a step in this direction. First, we show that assuming the (average-case) hardness of a numbertheoretic\r\nproblem related to factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average in the random-oracle model. Then we strengthen this result to show that the average-case hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform, a well-known technique used to compile a public-coin interactive protocol into a non-interactive one. As a corollary, we obtain average-case hardness for PPAD in the random-oracle model assuming the worst-case hardness of #SAT. Moreover, the above results can all be strengthened to obtain average-case hardness for the class CLS ⊆ PPAD.\r\nOur main technical contribution is constructing incrementally-verifiable procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable, we mean that every intermediate state of the computation includes a proof of its correctness, and the proof can be updated and verified in polynomial time. Previous constructions of such procedures relied on strong, non-standard assumptions. Instead, we introduce a technique called recursive proof-merging to obtain the same from weaker assumptions. "}],"has_accepted_license":"1","language":[{"iso":"eng"}],"month":"05","status":"public","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"type":"dissertation","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_processing_charge":"No","date_created":"2020-05-26T14:08:55Z","date_published":"2020-05-25T00:00:00Z","file_date_updated":"2020-07-14T12:48:04Z","publication_identifier":{"issn":["2663-337X"]},"title":"On the average-case hardness of total search problems","oa_version":"Published Version","_id":"7896","author":[{"first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","orcid":"0009-0006-6812-7317"}]},{"date_updated":"2026-04-16T09:48:36Z","day":"01","abstract":[{"text":"Cryptographic security is usually defined as a guarantee that holds except when a bad event with negligible probability occurs, and nothing is guaranteed in that bad case. However, in settings where such failure can happen with substantial probability, one needs to provide guarantees even for the bad case. A typical example is where a (possibly weak) password is used instead of a secure cryptographic key to protect a session, the bad event being that the adversary correctly guesses the password. In a situation with multiple such sessions, a per-session guarantee is desired: any session for which the password has not been guessed remains secure, independently of whether other sessions have been compromised. A new formalism for stating such gracefully degrading security guarantees is introduced and applied to analyze the examples of password-based message authentication and password-based encryption. While a natural per-message guarantee is achieved for authentication, the situation of password-based encryption is more delicate: a per-session confidentiality guarantee only holds against attackers for which the distribution of password-guessing effort over the sessions is known in advance. In contrast, for more general attackers without such a restriction, a strong, composable notion of security cannot be achieved.","lang":"eng"}],"fulldoi":"https://doi.org/10.3233/JCS-181131","language":[{"iso":"eng"}],"month":"01","department":[{"_id":"KrPi"}],"status":"public","type":"journal_article","article_processing_charge":"No","date_created":"2019-01-27T22:59:10Z","volume":27,"date_published":"2019-01-01T00:00:00Z","title":"Per-session security: Password-based cryptography revisited","publication_identifier":{"issn":["0926-227X"]},"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/166"}],"oa_version":"Preprint","_id":"5887","author":[{"full_name":"Demay, Gregory","first_name":"Gregory","last_name":"Demay"},{"first_name":"Peter","id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","full_name":"Gazi, Peter","last_name":"Gazi"},{"first_name":"Ueli","full_name":"Maurer, Ueli","last_name":"Maurer"},{"full_name":"Tackmann, Bjorn","last_name":"Tackmann","first_name":"Bjorn"}],"scopus_import":"1","publication":"Journal of Computer Security","publication_status":"published","citation":{"ama":"Demay G, Gazi P, Maurer U, Tackmann B. Per-session security: Password-based cryptography revisited. Journal of Computer Security. 2019;27(1):75-111. doi:10.3233/JCS-181131","short":"G. Demay, P. Gazi, U. Maurer, B. Tackmann, Journal of Computer Security 27 (2019) 75–111.","ista":"Demay G, Gazi P, Maurer U, Tackmann B. 2019. Per-session security: Password-based cryptography revisited. Journal of Computer Security. 27(1), 75–111.","apa":"Demay, G., Gazi, P., Maurer, U., & Tackmann, B. (2019). Per-session security: Password-based cryptography revisited. Journal of Computer Security. IOS Press. https://doi.org/10.3233/JCS-181131","ieee":"G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Per-session security: Password-based cryptography revisited,” Journal of Computer Security, vol. 27, no. 1. IOS Press, pp. 75–111, 2019.","chicago":"Demay, Gregory, Peter Gazi, Ueli Maurer, and Bjorn Tackmann. “Per-Session Security: Password-Based Cryptography Revisited.” Journal of Computer Security. IOS Press, 2019. https://doi.org/10.3233/JCS-181131.","mla":"Demay, Gregory, et al. “Per-Session Security: Password-Based Cryptography Revisited.” Journal of Computer Security, vol. 27, no. 1, IOS Press, 2019, pp. 75–111, doi:10.3233/JCS-181131."},"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","quality_controlled":"1","doi":"10.3233/JCS-181131","year":"2019","page":"75-111","ec_funded":1,"intvolume":" 27","publisher":"IOS Press","issue":"1","project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"oa":1,"article_type":"original"},{"volume":11443,"date_created":"2019-05-13T08:13:46Z","type":"conference","article_processing_charge":"No","month":"04","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"status":"public","day":"06","date_updated":"2026-04-16T09:52:04Z","fulldoi":"https://doi.org/10.1007/978-3-030-17259-6_11","abstract":[{"text":"A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key 𝑝𝑘′. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under 𝑝𝑘′ without having to know the underlying message, while transformations from 𝑝𝑘′ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.\r\n\r\nAll existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in Open image in new window , rendering the result meaningless already for moderate Open image in new window .\r\n\r\nJafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.\r\n\r\nOur results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).","lang":"eng"}],"scopus_import":"1","author":[{"id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","full_name":"Fuchsbauer, Georg","first_name":"Georg","last_name":"Fuchsbauer"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","orcid":"0009-0006-6812-7317"},{"first_name":"Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"}],"external_id":{"isi":["001299215500011"]},"conference":{"end_date":"2019-04-17","start_date":"2019-04-14","location":"Beijing, China","name":"PKC: Public-Key Cryptograhy"},"oa_version":"Preprint","main_file_link":[{"url":"https://eprint.iacr.org/2018/426","open_access":"1"}],"_id":"6430","publication_identifier":{"isbn":["9783030172589"],"issn":["0302-9743"],"eissn":["1611-3349"]},"title":"Adaptively secure proxy re-encryption","date_published":"2019-04-06T00:00:00Z","page":"317-346","ec_funded":1,"doi":"10.1007/978-3-030-17259-6_11","year":"2019","quality_controlled":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","citation":{"ama":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. Adaptively secure proxy re-encryption. In: Vol 11443. Springer Nature; 2019:317-346. doi:10.1007/978-3-030-17259-6_11","short":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, Springer Nature, 2019, pp. 317–346.","ista":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. 2019. Adaptively secure proxy re-encryption. PKC: Public-Key Cryptograhy, LNCS, vol. 11443, 317–346.","ieee":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “Adaptively secure proxy re-encryption,” presented at the PKC: Public-Key Cryptograhy, Beijing, China, 2019, vol. 11443, pp. 317–346.","apa":"Fuchsbauer, G., Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2019). Adaptively secure proxy re-encryption (Vol. 11443, pp. 317–346). Presented at the PKC: Public-Key Cryptograhy, Beijing, China: Springer Nature. https://doi.org/10.1007/978-3-030-17259-6_11","chicago":"Fuchsbauer, Georg, Chethan Kamath Hosdurg, Karen Klein, and Krzysztof Z Pietrzak. “Adaptively Secure Proxy Re-Encryption,” 11443:317–46. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-17259-6_11.","mla":"Fuchsbauer, Georg, et al. Adaptively Secure Proxy Re-Encryption. Vol. 11443, Springer Nature, 2019, pp. 317–46, doi:10.1007/978-3-030-17259-6_11."},"publication_status":"published","oa":1,"project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"related_material":{"record":[{"id":"10035","relation":"dissertation_contains","status":"public"}]},"isi":1,"publisher":"Springer Nature","intvolume":" 11443","alternative_title":["LNCS"]},{"editor":[{"full_name":"Buchmann, J","last_name":"Buchmann","first_name":"J"},{"full_name":"Nitaj, A","last_name":"Nitaj","first_name":"A"},{"full_name":"Rachidi, T","first_name":"T","last_name":"Rachidi"}],"date_published":"2019-06-29T00:00:00Z","publication_identifier":{"eisbn":["978-3-0302-3696-0"],"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["978-3-0302-3695-3"]},"title":"Sampling the integers with low relative error","conference":{"start_date":"2019-07-09","end_date":"2019-07-11","name":"AFRICACRYPT: International Conference on Cryptology in Africa","location":"Rabat, Morocco"},"main_file_link":[{"url":"https://eprint.iacr.org/2019/068","open_access":"1"}],"oa_version":"Preprint","_id":"6726","publication":"Progress in Cryptology – AFRICACRYPT 2019","scopus_import":"1","author":[{"full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","last_name":"Walter","orcid":"0000-0003-3186-2482"}],"external_id":{"isi":["001299240700009"]},"place":"Cham","date_updated":"2025-09-10T10:38:28Z","day":"29","fulldoi":"https://doi.org/10.1007/978-3-030-23696-0_9","abstract":[{"text":"Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so.","lang":"eng"}],"language":[{"iso":"eng"}],"month":"06","status":"public","department":[{"_id":"KrPi"}],"series_title":"LNCS","type":"book_chapter","article_processing_charge":"No","volume":11627,"date_created":"2019-07-29T12:25:31Z","publisher":"Springer Nature","intvolume":" 11627","oa":1,"project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"isi":1,"citation":{"chicago":"Walter, Michael. “Sampling the Integers with Low Relative Error.” In Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann, A Nitaj, and T Rachidi, 11627:157–80. LNCS. Cham: Springer Nature, 2019. https://doi.org/10.1007/978-3-030-23696-0_9.","mla":"Walter, Michael. “Sampling the Integers with Low Relative Error.” Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann et al., vol. 11627, Springer Nature, 2019, pp. 157–80, doi:10.1007/978-3-030-23696-0_9.","ista":"Walter M. 2019.Sampling the integers with low relative error. In: Progress in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180.","apa":"Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann, A. Nitaj, & T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019 (Vol. 11627, pp. 157–180). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-23696-0_9","ieee":"M. Walter, “Sampling the integers with low relative error,” in Progress in Cryptology – AFRICACRYPT 2019, vol. 11627, J. Buchmann, A. Nitaj, and T. Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.","short":"M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.","ama":"Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj A, Rachidi T, eds. Progress in Cryptology – AFRICACRYPT 2019. Vol 11627. LNCS. Cham: Springer Nature; 2019:157-180. doi:10.1007/978-3-030-23696-0_9"},"publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","quality_controlled":"1","ec_funded":1,"page":"157-180","year":"2019","doi":"10.1007/978-3-030-23696-0_9"},{"quality_controlled":"1","doi":"10.1109/isit.2019.8849240","year":"2019","publication_status":"published","citation":{"ama":"Skórski M. Strong chain rules for min-entropy under few bits spoiled. In: 2019 IEEE International Symposium on Information Theory. IEEE; 2019. doi:10.1109/isit.2019.8849240","short":"M. Skórski, in:, 2019 IEEE International Symposium on Information Theory, IEEE, 2019.","ista":"Skórski M. 2019. Strong chain rules for min-entropy under few bits spoiled. 2019 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 8849240.","apa":"Skórski, M. (2019). Strong chain rules for min-entropy under few bits spoiled. In 2019 IEEE International Symposium on Information Theory. Paris, France: IEEE. https://doi.org/10.1109/isit.2019.8849240","ieee":"M. Skórski, “Strong chain rules for min-entropy under few bits spoiled,” in 2019 IEEE International Symposium on Information Theory, Paris, France, 2019.","chicago":"Skórski, Maciej. “Strong Chain Rules for Min-Entropy under Few Bits Spoiled.” In 2019 IEEE International Symposium on Information Theory. IEEE, 2019. https://doi.org/10.1109/isit.2019.8849240.","mla":"Skórski, Maciej. “Strong Chain Rules for Min-Entropy under Few Bits Spoiled.” 2019 IEEE International Symposium on Information Theory, 8849240, IEEE, 2019, doi:10.1109/isit.2019.8849240."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","isi":1,"oa":1,"article_number":"8849240","publisher":"IEEE","article_processing_charge":"No","type":"conference","date_created":"2019-11-28T10:19:21Z","abstract":[{"text":"It is well established that the notion of min-entropy fails to satisfy the \\emph{chain rule} of the form H(X,Y)=H(X|Y)+H(Y), known for Shannon Entropy. Such a property would help to analyze how min-entropy is split among smaller blocks. Problems of this kind arise for example when constructing extractors and dispersers.\r\nWe show that any sequence of variables exhibits a very strong strong block-source structure (conditional distributions of blocks are nearly flat) when we \\emph{spoil few correlated bits}. This implies, conditioned on the spoiled bits, that \\emph{splitting-recombination properties} hold. In particular, we have many nice properties that min-entropy doesn't obey in general, for example strong chain rules, \"information can't hurt\" inequalities, equivalences of average and worst-case conditional entropy definitions and others. Quantitatively, for any sequence X1,…,Xt of random variables over an alphabet X we prove that, when conditioned on m=t⋅O(loglog|X|+loglog(1/ϵ)+logt) bits of auxiliary information, all conditional distributions of the form Xi|XAdvances in Cryptology – EUROCRYPT 2019, vol. 11477, Springer International Publishing, 2019, pp. 277–91, doi:10.1007/978-3-030-17656-3_10.","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.","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.","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","ista":"Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2019. Reversible proofs of sequential work. Advances in Cryptology – EUROCRYPT 2019. EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol. 11477, 277–291.","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."},"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/252"}],"conference":{"location":"Darmstadt, Germany","name":"EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques","end_date":"2019-05-23","start_date":"2019-05-19"},"_id":"7411","external_id":{"isi":["000483516200010"]},"scopus_import":"1","publication":"Advances in Cryptology – EUROCRYPT 2019","author":[{"id":"40297222-F248-11E8-B48F-1D18A9856A87","full_name":"Abusalah, Hamza M","last_name":"Abusalah","first_name":"Hamza M"},{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0006-6812-7317"},{"full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","last_name":"Klein"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"},{"last_name":"Walter","full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","orcid":"0000-0003-3186-2482"}],"date_published":"2019-04-24T00:00:00Z","title":"Reversible proofs of sequential work","publication_identifier":{"issn":["0302-9743"],"isbn":["9783030176556"],"eisbn":["9783030176563"],"eissn":["1611-3349"]},"article_processing_charge":"No","type":"conference","volume":11477,"date_created":"2020-01-30T09:26:14Z","day":"24","date_updated":"2026-04-16T10:27:47Z","abstract":[{"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).","lang":"eng"}],"fulldoi":"https://doi.org/10.1007/978-3-030-17656-3_10","month":"04","language":[{"iso":"eng"}],"status":"public","department":[{"_id":"KrPi"}]},{"das_tickbox":"1","oa":1,"project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"article_number":"60","file":[{"content_type":"application/pdf","relation":"main_file","file_size":558770,"date_created":"2019-06-06T14:22:04Z","file_name":"2019_LIPIcs_Pietrzak.pdf","date_updated":"2020-07-14T12:47:33Z","checksum":"f0ae1bb161431d9db3dea5ace082bfb5","file_id":"6529","creator":"dernst","access_level":"open_access"}],"alternative_title":["LIPIcs"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","intvolume":" 124","quality_controlled":"1","ddc":["000"],"ec_funded":1,"year":"2019","doi":"10.4230/LIPICS.ITCS.2019.60","citation":{"short":"K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.","ama":"Pietrzak KZ. Simple verifiable delay functions. In: 10th Innovations in Theoretical Computer Science Conference. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.ITCS.2019.60","apa":"Pietrzak, K. Z. (2019). Simple verifiable delay functions. In 10th Innovations in Theoretical Computer Science Conference (Vol. 124). San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2019.60","ieee":"K. Z. Pietrzak, “Simple verifiable delay functions,” in 10th Innovations in Theoretical Computer Science Conference, San Diego, CA, United States, 2019, vol. 124.","ista":"Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 124, 60.","mla":"Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” 10th Innovations in Theoretical Computer Science Conference, vol. 124, 60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.ITCS.2019.60.","chicago":"Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” In 10th Innovations in Theoretical Computer Science Conference, Vol. 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ITCS.2019.60."},"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"end_date":"2019-01-12","start_date":"2019-01-10","location":"San Diego, CA, United States","name":"ITCS: Innovations in Theoretical Computer Science"},"oa_version":"Published Version","_id":"6528","author":[{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"}],"scopus_import":"1","publication":"10th Innovations in Theoretical Computer Science Conference","external_id":{"cryptoeprintid":["2018/627"]},"cryptoeprintid":1,"date_published":"2019-01-10T00:00:00Z","file_date_updated":"2020-07-14T12:47:33Z","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-095-8"]},"title":"Simple verifiable delay functions","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_processing_charge":"No","date_created":"2019-06-06T14:12:36Z","volume":124,"date_updated":"2026-07-07T13:31:01Z","day":"10","fulldoi":"https://doi.org/10.4230/LIPICS.ITCS.2019.60","abstract":[{"lang":"eng","text":"We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod N) where the prover doesn’t know the factorization of N and its running time is dominated by solving the puzzle, that is, compute x2T, which is conjectured to require T sequential squarings. To get a VDF we make this protocol non-interactive using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia blockchain design, which uses a VDF as akey ingredient. For typical parameters (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around three RSA exponentiations and computing the proof is 8000 times faster than solving the puzzle even without any parallelism."}],"has_accepted_license":"1","month":"01","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"status":"public"},{"date_published":"2019-06-01T00:00:00Z","title":"Finding a Nash equilibrium is no easier than breaking Fiat-Shamir","publication_identifier":{"isbn":["9781450367059"]},"_id":"6677","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/549"}],"oa_version":"Preprint","conference":{"name":"STOC: Symposium on Theory of Computing","location":"Phoenix, AZ, United States","start_date":"2019-06-23","end_date":"2019-06-26"},"external_id":{"isi":["000523199100100"]},"scopus_import":"1","author":[{"full_name":"Choudhuri, Arka Rai","first_name":"Arka Rai","last_name":"Choudhuri"},{"first_name":"Pavel","last_name":"Hubáček","full_name":"Hubáček, Pavel"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","orcid":"0009-0006-6812-7317"},{"orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Alon","full_name":"Rosen, Alon","last_name":"Rosen"},{"full_name":"Rothblum, Guy N.","last_name":"Rothblum","first_name":"Guy N."}],"publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019","abstract":[{"lang":"eng","text":"The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.\r\n\r\nWe show that solving the END−OF−METERED−LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT.\r\n\r\nOur main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n)."}],"fulldoi":"https://doi.org/10.1145/3313276.3316400","day":"01","date_updated":"2026-07-30T13:43:53Z","status":"public","department":[{"_id":"KrPi"}],"language":[{"iso":"eng"}],"month":"06","article_processing_charge":"No","type":"conference","date_created":"2019-07-24T09:20:53Z","publisher":"ACM","isi":1,"oa":1,"related_material":{"record":[{"id":"7896","relation":"dissertation_contains","status":"public"}]},"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"publication_status":"published","citation":{"ama":"Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019. ACM; 2019:1103-1114. doi:10.1145/3313276.3316400","short":"A.R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K.Z. Pietrzak, A. Rosen, G.N. Rothblum, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, ACM, 2019, pp. 1103–1114.","ista":"Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. 2019. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019. STOC: Symposium on Theory of Computing, 1103–1114.","ieee":"A. R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K. Z. Pietrzak, A. Rosen, and G. N. Rothblum, “Finding a Nash equilibrium is no easier than breaking Fiat-Shamir,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, Phoenix, AZ, United States, 2019, pp. 1103–1114.","apa":"Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen, A., & Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019 (pp. 1103–1114). Phoenix, AZ, United States: ACM. https://doi.org/10.1145/3313276.3316400","chicago":"Choudhuri, Arka Rai, Pavel Hubáček, Chethan Kamath Hosdurg, Krzysztof Z Pietrzak, Alon Rosen, and Guy N. Rothblum. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, 1103–14. ACM, 2019. https://doi.org/10.1145/3313276.3316400.","mla":"Choudhuri, Arka Rai, et al. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, ACM, 2019, pp. 1103–14, doi:10.1145/3313276.3316400."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.1145/3313276.3316400","year":"2019","ec_funded":1,"page":"1103-1114"},{"publication_status":"published","citation":{"ama":"Alwen JF, Blocki J, Pietrzak KZ. Sustained space complexity. In: Vol 10821. Springer; 2018:99-130. doi:10.1007/978-3-319-78375-8_4","short":"J.F. Alwen, J. Blocki, K.Z. Pietrzak, in:, Springer, 2018, pp. 99–130.","apa":"Alwen, J. F., Blocki, J., & Pietrzak, K. Z. (2018). Sustained space complexity (Vol. 10821, pp. 99–130). Presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78375-8_4","ieee":"J. F. Alwen, J. Blocki, and K. Z. Pietrzak, “Sustained space complexity,” presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10821, pp. 99–130.","ista":"Alwen JF, Blocki J, Pietrzak KZ. 2018. Sustained space complexity. Eurocrypt: Advances in Cryptology, LNCS, vol. 10821, 99–130.","mla":"Alwen, Joel F., et al. Sustained Space Complexity. Vol. 10821, Springer, 2018, pp. 99–130, doi:10.1007/978-3-319-78375-8_4.","chicago":"Alwen, Joel F, Jeremiah Blocki, and Krzysztof Z Pietrzak. “Sustained Space Complexity,” 10821:99–130. Springer, 2018. https://doi.org/10.1007/978-3-319-78375-8_4."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","year":"2018","doi":"10.1007/978-3-319-78375-8_4","ec_funded":1,"page":"99 - 130","alternative_title":["LNCS"],"intvolume":" 10821","publisher":"Springer","isi":1,"oa":1,"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"abstract":[{"text":"Memory-hard functions (MHF) are functions whose evaluation cost is dominated by memory cost. MHFs are egalitarian, in the sense that evaluating them on dedicated hardware (like FPGAs or ASICs) is not much cheaper than on off-the-shelf hardware (like x86 CPUs). MHFs have interesting cryptographic applications, most notably to password hashing and securing blockchains.\r\n\r\nAlwen and Serbinenko [STOC’15] define the cumulative memory complexity (cmc) of a function as the sum (over all time-steps) of the amount of memory required to compute the function. They advocate that a good MHF must have high cmc. Unlike previous notions, cmc takes into account that dedicated hardware might exploit amortization and parallelism. Still, cmc has been critizised as insufficient, as it fails to capture possible time-memory trade-offs; as memory cost doesn’t scale linearly, functions with the same cmc could still have very different actual hardware cost.\r\n\r\nIn this work we address this problem, and introduce the notion of sustained-memory complexity, which requires that any algorithm evaluating the function must use a large amount of memory for many steps. We construct functions (in the parallel random oracle model) whose sustained-memory complexity is almost optimal: our function can be evaluated using n steps and O(n/log(n)) memory, in each step making one query to the (fixed-input length) random oracle, while any algorithm that can make arbitrary many parallel queries to the random oracle, still needs Ω(n/log(n)) memory for Ω(n) steps.\r\n\r\nAs has been done for various notions (including cmc) before, we reduce the task of constructing an MHFs with high sustained-memory complexity to proving pebbling lower bounds on DAGs. Our main technical contribution is the construction is a family of DAGs on n nodes with constant indegree with high “sustained-space complexity”, meaning that any parallel black-pebbling strategy requires Ω(n/log(n)) pebbles for at least Ω(n) steps.\r\n\r\nAlong the way we construct a family of maximally “depth-robust” DAGs with maximum indegree O(logn) , improving upon the construction of Mahmoody et al. [ITCS’13] which had maximum indegree O(log2n⋅","lang":"eng"}],"fulldoi":"https://doi.org/10.1007/978-3-319-78375-8_4","day":"31","date_updated":"2025-07-10T11:52:24Z","department":[{"_id":"KrPi"}],"status":"public","language":[{"iso":"eng"}],"month":"03","type":"conference","article_processing_charge":"No","publist_id":"7583","date_created":"2018-12-11T11:45:41Z","volume":10821,"arxiv":1,"date_published":"2018-03-31T00:00:00Z","title":"Sustained space complexity","_id":"298","main_file_link":[{"url":"https://arxiv.org/abs/1705.05313","open_access":"1"}],"oa_version":"Preprint","conference":{"location":"Tel Aviv, Israel","name":"Eurocrypt: Advances in Cryptology","end_date":"2018-05-03","start_date":"2018-04-29"},"external_id":{"isi":["000517098700004"],"arxiv":["1705.05313"]},"scopus_import":"1","author":[{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F"},{"full_name":"Blocki, Jeremiah","last_name":"Blocki","first_name":"Jeremiah"},{"orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}]},{"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","corr_author":"1","publication_status":"published","citation":{"short":"D. Micciancio, M. Walter, in:, Springer, 2018, pp. 3–28.","ama":"Micciancio D, Walter M. On the bit security of cryptographic primitives. In: Vol 10820. Springer; 2018:3-28. doi:10.1007/978-3-319-78381-9_1","mla":"Micciancio, Daniele, and Michael Walter. On the Bit Security of Cryptographic Primitives. Vol. 10820, Springer, 2018, pp. 3–28, doi:10.1007/978-3-319-78381-9_1.","chicago":"Micciancio, Daniele, and Michael Walter. “On the Bit Security of Cryptographic Primitives,” 10820:3–28. Springer, 2018. https://doi.org/10.1007/978-3-319-78381-9_1.","ieee":"D. Micciancio and M. Walter, “On the bit security of cryptographic primitives,” presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10820, pp. 3–28.","apa":"Micciancio, D., & Walter, M. (2018). On the bit security of cryptographic primitives (Vol. 10820, pp. 3–28). Presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78381-9_1","ista":"Micciancio D, Walter M. 2018. On the bit security of cryptographic primitives. Eurocrypt: Advances in Cryptology, LNCS, vol. 10820, 3–28."},"doi":"10.1007/978-3-319-78381-9_1","year":"2018","page":"3 - 28","ec_funded":1,"quality_controlled":"1","intvolume":" 10820","publisher":"Springer","alternative_title":["LNCS"],"oa":1,"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"isi":1,"month":"03","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"status":"public","date_updated":"2025-04-14T07:22:06Z","day":"31","abstract":[{"lang":"eng","text":"We introduce a formal quantitative notion of “bit security” for a general type of cryptographic games (capturing both decision and search problems), aimed at capturing the intuition that a cryptographic primitive with k-bit security is as hard to break as an ideal cryptographic function requiring a brute force attack on a k-bit key space. Our new definition matches the notion of bit security commonly used by cryptographers and cryptanalysts when studying search (e.g., key recovery) problems, where the use of the traditional definition is well established. However, it produces a quantitatively different metric in the case of decision (indistinguishability) problems, where the use of (a straightforward generalization of) the traditional definition is more problematic and leads to a number of paradoxical situations or mismatches between theoretical/provable security and practical/common sense intuition. Key to our new definition is to consider adversaries that may explicitly declare failure of the attack. We support and justify the new definition by proving a number of technical results, including tight reductions between several standard cryptographic problems, a new hybrid theorem that preserves bit security, and an application to the security analysis of indistinguishability primitives making use of (approximate) floating point numbers. This is the first result showing that (standard precision) 53-bit floating point numbers can be used to achieve 100-bit security in the context of cryptographic primitives with general indistinguishability-based security definitions. Previous results of this type applied only to search problems, or special types of decision problems."}],"fulldoi":"https://doi.org/10.1007/978-3-319-78381-9_1","volume":10820,"date_created":"2018-12-11T11:45:42Z","type":"conference","article_processing_charge":"No","publist_id":"7581","title":"On the bit security of cryptographic primitives","date_published":"2018-03-31T00:00:00Z","external_id":{"isi":["000517097500001"]},"scopus_import":"1","author":[{"first_name":"Daniele","full_name":"Micciancio, Daniele","last_name":"Micciancio"},{"orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter"}],"oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/077"}],"conference":{"end_date":"2018-05-03","start_date":"2018-04-29","location":"Tel Aviv, Israel","name":"Eurocrypt: Advances in Cryptology"},"acknowledgement":"Research supported in part by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under the SafeWare program. Opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views, position or policy of the Government. The second author was also supported by the European Research Council, ERC consolidator grant (682815 - TOCNeT).","_id":"300"},{"language":[{"iso":"eng"}],"month":"05","status":"public","department":[{"_id":"KrPi"}],"date_updated":"2025-04-14T07:22:06Z","day":"29","fulldoi":"https://doi.org/10.1007/978-3-319-78375-8_15","abstract":[{"text":"At ITCS 2013, Mahmoody, Moran and Vadhan [MMV13] introduce and construct publicly verifiable proofs of sequential work, which is a protocol for proving that one spent sequential computational work related to some statement. The original motivation for such proofs included non-interactive time-stamping and universally verifiable CPU benchmarks. A more recent application, and our main motivation, are blockchain designs, where proofs of sequential work can be used – in combination with proofs of space – as a more ecological and economical substitute for proofs of work which are currently used to secure Bitcoin and other cryptocurrencies. The construction proposed by [MMV13] is based on a hash function and can be proven secure in the random oracle model, or assuming inherently sequential hash-functions, which is a new standard model assumption introduced in their work. In a proof of sequential work, a prover gets a “statement” χ, a time parameter N and access to a hash-function H, which for the security proof is modelled as a random oracle. Correctness requires that an honest prover can make a verifier accept making only N queries to H, while soundness requires that any prover who makes the verifier accept must have made (almost) N sequential queries to H. Thus a solution constitutes a proof that N time passed since χ was received. Solutions must be publicly verifiable in time at most polylogarithmic in N. The construction of [MMV13] is based on “depth-robust” graphs, and as a consequence has rather poor concrete parameters. But the major drawback is that the prover needs not just N time, but also N space to compute a proof. In this work we propose a proof of sequential work which is much simpler, more efficient and achieves much better concrete bounds. Most importantly, the space required can be as small as log (N) (but we get better soundness using slightly more memory than that). An open problem stated by [MMV13] that our construction does not solve either is achieving a “unique” proof, where even a cheating prover can only generate a single accepting proof. This property would be extremely useful for applications to blockchains.","lang":"eng"}],"date_created":"2018-12-11T11:45:42Z","volume":10821,"publist_id":"7579","type":"conference","article_processing_charge":"No","title":"Simple proofs of sequential work","date_published":"2018-05-29T00:00:00Z","scopus_import":"1","author":[{"first_name":"Bram","full_name":"Cohen, Bram","last_name":"Cohen"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654"}],"external_id":{"isi":["000517098700015"]},"conference":{"start_date":"2018-04-29","end_date":"2018-05-03","name":"Eurocrypt: Advances in Cryptology","location":"Tel Aviv, Israel"},"oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/183.pdf"}],"_id":"302","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Cohen B, Pietrzak KZ. 2018. Simple proofs of sequential work. Eurocrypt: Advances in Cryptology, LNCS, vol. 10821, 451–467.","ieee":"B. Cohen and K. Z. Pietrzak, “Simple proofs of sequential work,” presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10821, pp. 451–467.","apa":"Cohen, B., & Pietrzak, K. Z. (2018). Simple proofs of sequential work (Vol. 10821, pp. 451–467). Presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78375-8_15","chicago":"Cohen, Bram, and Krzysztof Z Pietrzak. “Simple Proofs of Sequential Work,” 10821:451–67. Springer, 2018. https://doi.org/10.1007/978-3-319-78375-8_15.","mla":"Cohen, Bram, and Krzysztof Z. Pietrzak. Simple Proofs of Sequential Work. Vol. 10821, Springer, 2018, pp. 451–67, doi:10.1007/978-3-319-78375-8_15.","ama":"Cohen B, Pietrzak KZ. Simple proofs of sequential work. In: Vol 10821. Springer; 2018:451-467. doi:10.1007/978-3-319-78375-8_15","short":"B. Cohen, K.Z. Pietrzak, in:, Springer, 2018, pp. 451–467."},"publication_status":"published","page":"451 - 467","ec_funded":1,"year":"2018","doi":"10.1007/978-3-319-78375-8_15","quality_controlled":"1","publisher":"Springer","intvolume":" 10821","alternative_title":["LNCS"],"project":[{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"oa":1,"isi":1},{"abstract":[{"text":"We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition (PHC). Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower hardware and/or energy cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks. Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC. Ideally, one would like the complexity of a DAG underlying an iMHF to be as close to quadratic in the number of nodes of the graph as possible. Instead, we show that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial property of each underlying DAG (called its depth-robustness. By establishing upper bounds on this property we are then able to apply the general technique of [Alwen-Block'16] for analyzing the hardware costs of an iMHF.","lang":"eng"}],"fulldoi":"https://doi.org/10.1145/3196494.3196534","date_updated":"2024-11-04T13:52:29Z","day":"01","department":[{"_id":"KrPi"},{"_id":"HeEd"},{"_id":"VlKo"}],"status":"public","month":"06","language":[{"iso":"eng"}],"article_processing_charge":"No","type":"conference","publist_id":"7723","date_created":"2018-12-11T11:45:07Z","date_published":"2018-06-01T00:00:00Z","title":"On the memory hardness of data independent password hashing functions","acknowledgement":"Leonid Reyzin was supported in part by IST Austria and by US NSF grants 1012910, 1012798, and 1422965; this research was performed while he was visiting IST Austria.","_id":"193","main_file_link":[{"url":"https://eprint.iacr.org/2016/783","open_access":"1"}],"oa_version":"Submitted Version","conference":{"location":"Incheon, Republic of Korea","name":"ASIACCS: Asia Conference on Computer and Communications Security ","end_date":"2018-06-08","start_date":"2018-06-04"},"external_id":{"isi":["000516620100005"]},"author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"last_name":"Gazi","full_name":"Gazi, Peter","first_name":"Peter"},{"last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan"},{"last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","first_name":"Karen"},{"last_name":"Osang","first_name":"Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","full_name":"Osang, Georg F","orcid":"0000-0002-8882-5116"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"},{"last_name":"Reyzin","first_name":"Lenoid","full_name":"Reyzin, Lenoid"},{"last_name":"Rolinek","full_name":"Rolinek, Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"},{"last_name":"Rybar","id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87","first_name":"Michal","full_name":"Rybar, Michal"}],"publication":"Proceedings of the 2018 on Asia Conference on Computer and Communication Security","scopus_import":"1","publication_status":"published","citation":{"chicago":"Alwen, Joel F, Peter Gazi, Chethan Kamath Hosdurg, Karen Klein, Georg F Osang, Krzysztof Z Pietrzak, Lenoid Reyzin, Michal Rolinek, and Michal Rybar. “On the Memory Hardness of Data Independent Password Hashing Functions.” In Proceedings of the 2018 on Asia Conference on Computer and Communication Security, 51–65. ACM, 2018. https://doi.org/10.1145/3196494.3196534.","mla":"Alwen, Joel F., et al. “On the Memory Hardness of Data Independent Password Hashing Functions.” Proceedings of the 2018 on Asia Conference on Computer and Communication Security, ACM, 2018, pp. 51–65, doi:10.1145/3196494.3196534.","ista":"Alwen JF, Gazi P, Kamath Hosdurg C, Klein K, Osang GF, Pietrzak KZ, Reyzin L, Rolinek M, Rybar M. 2018. On the memory hardness of data independent password hashing functions. Proceedings of the 2018 on Asia Conference on Computer and Communication Security. ASIACCS: Asia Conference on Computer and Communications Security , 51–65.","apa":"Alwen, J. F., Gazi, P., Kamath Hosdurg, C., Klein, K., Osang, G. F., Pietrzak, K. Z., … Rybar, M. (2018). On the memory hardness of data independent password hashing functions. In Proceedings of the 2018 on Asia Conference on Computer and Communication Security (pp. 51–65). Incheon, Republic of Korea: ACM. https://doi.org/10.1145/3196494.3196534","ieee":"J. F. Alwen et al., “On the memory hardness of data independent password hashing functions,” in Proceedings of the 2018 on Asia Conference on Computer and Communication Security, Incheon, Republic of Korea, 2018, pp. 51–65.","short":"J.F. Alwen, P. Gazi, C. Kamath Hosdurg, K. Klein, G.F. Osang, K.Z. Pietrzak, L. Reyzin, M. Rolinek, M. Rybar, in:, Proceedings of the 2018 on Asia Conference on Computer and Communication Security, ACM, 2018, pp. 51–65.","ama":"Alwen JF, Gazi P, Kamath Hosdurg C, et al. On the memory hardness of data independent password hashing functions. In: Proceedings of the 2018 on Asia Conference on Computer and Communication Security. ACM; 2018:51-65. doi:10.1145/3196494.3196534"},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","quality_controlled":"1","year":"2018","doi":"10.1145/3196494.3196534","ec_funded":1,"page":"51 - 65","publisher":"ACM","isi":1,"oa":1,"project":[{"call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160"},{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}]},{"issue":"4","publisher":"ACM","intvolume":" 65","article_number":"20","article_type":"original","oa":1,"project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"},{"name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668","call_identifier":"FP7"}],"isi":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ama":"Dziembowski S, Pietrzak KZ, Wichs D. Non-malleable codes. Journal of the ACM. 2018;65(4). doi:10.1145/3178432","short":"S. Dziembowski, K.Z. Pietrzak, D. Wichs, Journal of the ACM 65 (2018).","ista":"Dziembowski S, Pietrzak KZ, Wichs D. 2018. Non-malleable codes. Journal of the ACM. 65(4), 20.","apa":"Dziembowski, S., Pietrzak, K. Z., & Wichs, D. (2018). Non-malleable codes. Journal of the ACM. ACM. https://doi.org/10.1145/3178432","ieee":"S. Dziembowski, K. Z. Pietrzak, and D. Wichs, “Non-malleable codes,” Journal of the ACM, vol. 65, no. 4. ACM, 2018.","chicago":"Dziembowski, Stefan, Krzysztof Z Pietrzak, and Daniel Wichs. “Non-Malleable Codes.” Journal of the ACM. ACM, 2018. https://doi.org/10.1145/3178432.","mla":"Dziembowski, Stefan, et al. “Non-Malleable Codes.” Journal of the ACM, vol. 65, no. 4, 20, ACM, 2018, doi:10.1145/3178432."},"publication_status":"published","ec_funded":1,"year":"2018","doi":"10.1145/3178432","quality_controlled":"1","title":"Non-malleable codes","date_published":"2018-08-01T00:00:00Z","author":[{"last_name":"Dziembowski","full_name":"Dziembowski, Stefan","first_name":"Stefan"},{"orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak"},{"first_name":"Daniel","last_name":"Wichs","full_name":"Wichs, Daniel"}],"publication":"Journal of the ACM","scopus_import":"1","external_id":{"isi":["000442938200004"]},"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2009/608"}],"oa_version":"Preprint","_id":"107","language":[{"iso":"eng"}],"month":"08","department":[{"_id":"KrPi"}],"status":"public","date_updated":"2025-04-14T07:22:06Z","day":"01","fulldoi":"https://doi.org/10.1145/3178432","abstract":[{"lang":"eng","text":"We introduce the notion of “non-malleable codes” which relaxes the notion of error correction and error detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In contrast to error correction and error detection, non-malleability can be achieved for very rich classes of modifications. We construct an efficient code that is non-malleable with respect to modifications that affect each bit of the codeword arbitrarily (i.e., leave it untouched, flip it, or set it to either 0 or 1), but independently of the value of the other bits of the codeword. Using the probabilistic method, we also show a very strong and general statement: there exists a non-malleable code for every “small enough” family F of functions via which codewords can be modified. Although this probabilistic method argument does not directly yield efficient constructions, it gives us efficient non-malleable codes in the random-oracle model for very general classes of tampering functions—e.g., functions where every bit in the tampered codeword can depend arbitrarily on any 99% of the bits in the original codeword. As an application of non-malleable codes, we show that they provide an elegant algorithmic solution to the task of protecting functionalities implemented in hardware (e.g., signature cards) against “tampering attacks.” In such attacks, the secret state of a physical system is tampered, in the hopes that future interaction with the modified system will reveal some secret information. This problem was previously studied in the work of Gennaro et al. in 2004 under the name “algorithmic tamper proof security” (ATP). We show that non-malleable codes can be used to achieve important improvements over the prior work. In particular, we show that any functionality can be made secure against a large class of tampering attacks, simply by encoding the secret state with a non-malleable code while it is stored in memory."}],"date_created":"2018-12-11T11:44:40Z","volume":65,"publist_id":"7947","type":"journal_article","article_processing_charge":"No"},{"isi":1,"oa":1,"intvolume":" 2018","publisher":"IEEE","alternative_title":["ISIT Proceedings"],"year":"2018","doi":"10.1109/ISIT.2018.8437654","quality_controlled":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"published","citation":{"ama":"Obremski M, Skórski M. Inverted leftover hash lemma. In: Vol 2018. IEEE; 2018. doi:10.1109/ISIT.2018.8437654","short":"M. Obremski, M. Skórski, in:, IEEE, 2018.","mla":"Obremski, Marciej, and Maciej Skórski. Inverted Leftover Hash Lemma. Vol. 2018, IEEE, 2018, doi:10.1109/ISIT.2018.8437654.","chicago":"Obremski, Marciej, and Maciej Skórski. “Inverted Leftover Hash Lemma,” Vol. 2018. IEEE, 2018. https://doi.org/10.1109/ISIT.2018.8437654.","apa":"Obremski, M., & Skórski, M. (2018). Inverted leftover hash lemma (Vol. 2018). Presented at the ISIT: International Symposium on Information Theory, Vail, CO, USA: IEEE. https://doi.org/10.1109/ISIT.2018.8437654","ieee":"M. Obremski and M. Skórski, “Inverted leftover hash lemma,” presented at the ISIT: International Symposium on Information Theory, Vail, CO, USA, 2018, vol. 2018.","ista":"Obremski M, Skórski M. 2018. Inverted leftover hash lemma. ISIT: International Symposium on Information Theory, ISIT Proceedings, vol. 2018."},"external_id":{"isi":["000448139300368"]},"scopus_import":"1","author":[{"last_name":"Obremski","full_name":"Obremski, Marciej","first_name":"Marciej"},{"last_name":"Skorski","first_name":"Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","full_name":"Skorski, Maciej"}],"_id":"108","main_file_link":[{"url":"https://eprint.iacr.org/2017/507","open_access":"1"}],"oa_version":"Submitted Version","conference":{"start_date":"2018-06-17 ","end_date":"2018-06-22","name":"ISIT: International Symposium on Information Theory","location":"Vail, CO, USA"},"title":"Inverted leftover hash lemma","date_published":"2018-08-16T00:00:00Z","date_created":"2018-12-11T11:44:40Z","volume":2018,"type":"conference","article_processing_charge":"No","publist_id":"7946","department":[{"_id":"KrPi"}],"status":"public","language":[{"iso":"eng"}],"month":"08","abstract":[{"lang":"eng","text":"Universal hashing found a lot of applications in computer science. In cryptography the most important fact about universal families is the so called Leftover Hash Lemma, proved by Impagliazzo, Levin and Luby. In the language of modern cryptography it states that almost universal families are good extractors. In this work we provide a somewhat surprising characterization in the opposite direction. Namely, every extractor with sufficiently good parameters yields a universal family on a noticeable fraction of its inputs. Our proof technique is based on tools from extremal graph theory applied to the \\'collision graph\\' induced by the extractor, and may be of independent interest. We discuss possible applications to the theory of randomness extractors and non-malleable codes."}],"fulldoi":"https://doi.org/10.1109/ISIT.2018.8437654","day":"16","date_updated":"2023-09-13T08:23:18Z"}]