[{"date_updated":"2023-11-30T10:54:50Z","department":[{"_id":"KrPi"}],"_id":"9969","conference":{"name":"2021 IFIP Networking Conference (IFIP Networking)","start_date":"2021-06-21","end_date":"2021-06-24","location":"Espoo and Helsinki, Finland"},"type":"conference","status":"public","publication_status":"published","publication_identifier":{"isbn":["978-1-6654-4501-6"],"eissn":["1861-2288"],"eisbn":["978-3-9031-7639-3"]},"language":[{"iso":"eng"}],"ec_funded":1,"related_material":{"record":[{"relation":"dissertation_contains","id":"14506","status":"public"}]},"abstract":[{"text":"Payment channel networks are a promising approach to improve the scalability of cryptocurrencies: they allow to perform transactions in a peer-to-peer fashion, along multihop routes in the network, without requiring consensus on the blockchain. However, during the discovery of cost-efficient routes for the transaction, critical information may be revealed about the transacting entities. This paper initiates the study of privacy-preserving route discovery mechanisms for payment channel networks. In particular, we present LightPIR, an approach which allows a client to learn the shortest (or cheapest in terms of fees) path between two nodes without revealing any information about the endpoints of the transaction to the servers. The two main observations which allow for an efficient solution in LightPIR are that: (1) surprisingly, hub labelling algorithms – which were developed to preprocess “street network like” graphs so one can later efficiently compute shortest paths – also perform well for the graphs underlying payment channel networks, and that (2) hub labelling algorithms can be conveniently combined with private information retrieval. LightPIR relies on a simple hub labeling heuristic on top of existing hub labeling algorithms which leverages the specific topological features of cryptocurrency networks to further minimize storage and bandwidth overheads. In a case study considering the Lightning network, we show that our approach is an order of magnitude more efficient compared to a privacy-preserving baseline based on using private information retrieval on a database that stores all pairs shortest paths.","lang":"eng"}],"oa_version":"Submitted Version","main_file_link":[{"url":"https://arxiv.org/abs/2104.04293","open_access":"1"}],"scopus_import":"1","month":"06","citation":{"mla":"Pietrzak, Krzysztof Z., et al. LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks. IEEE, 2021, doi:10.23919/IFIPNetworking52078.2021.9472205.","short":"K.Z. Pietrzak, I. Salem, S. Schmid, M.X. Yeo, in:, IEEE, 2021.","ieee":"K. Z. Pietrzak, I. Salem, S. Schmid, and M. X. Yeo, “LightPIR: Privacy-preserving route discovery for payment channel networks,” presented at the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland, 2021.","apa":"Pietrzak, K. Z., Salem, I., Schmid, S., & Yeo, M. X. (2021). LightPIR: Privacy-preserving route discovery for payment channel networks. Presented at the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland: IEEE. https://doi.org/10.23919/IFIPNetworking52078.2021.9472205","ama":"Pietrzak KZ, Salem I, Schmid S, Yeo MX. LightPIR: Privacy-preserving route discovery for payment channel networks. In: IEEE; 2021. doi:10.23919/IFIPNetworking52078.2021.9472205","chicago":"Pietrzak, Krzysztof Z, Iosif Salem, Stefan Schmid, and Michelle X Yeo. “LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks.” IEEE, 2021. https://doi.org/10.23919/IFIPNetworking52078.2021.9472205.","ista":"Pietrzak KZ, Salem I, Schmid S, Yeo MX. 2021. LightPIR: Privacy-preserving route discovery for payment channel networks. 2021 IFIP Networking Conference (IFIP Networking)."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000853016800008"],"arxiv":["2104.04293"]},"article_processing_charge":"No","author":[{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"first_name":"Iosif","full_name":"Salem, Iosif","last_name":"Salem"},{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"},{"last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"title":"LightPIR: Privacy-preserving route discovery for payment channel networks","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"year":"2021","isi":1,"day":"21","date_created":"2021-08-29T22:01:16Z","date_published":"2021-06-21T00:00:00Z","doi":"10.23919/IFIPNetworking52078.2021.9472205","oa":1,"publisher":"IEEE","quality_controlled":"1"},{"type":"conference","conference":{"name":"CRYPTO: Annual International Cryptology Conference","start_date":"2020-08-17","end_date":"2020-08-21","location":"Santa Barbara, CA, United States"},"status":"public","_id":"8322","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T08:18:08Z","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"url":"https://eprint.iacr.org/2019/1317","open_access":"1"}],"month":"08","intvolume":" 12171","abstract":[{"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).","lang":"eng"}],"oa_version":"Preprint","volume":12171,"ec_funded":1,"publication_identifier":{"isbn":["9783030568795"],"eissn":["16113349"],"issn":["03029743"]},"publication_status":"published","language":[{"iso":"eng"}],"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"author":[{"last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","first_name":"Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"first_name":"Stefan","last_name":"Dziembowski","full_name":"Dziembowski, Stefan"},{"first_name":"Jesper Buus","full_name":"Nielsen, Jesper Buus","last_name":"Nielsen"}],"article_processing_charge":"No","title":"Reverse firewalls for actively secure MPCs","citation":{"short":"S. Chakraborty, S. Dziembowski, J.B. Nielsen, in:, Advances in Cryptology – CRYPTO 2020, Springer Nature, 2020, pp. 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.","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","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","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.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","publisher":"Springer Nature","oa":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.","page":"732-762","date_published":"2020-08-10T00:00:00Z","doi":"10.1007/978-3-030-56880-1_26","date_created":"2020-08-30T22:01:12Z","year":"2020","day":"10","publication":"Advances in Cryptology – CRYPTO 2020"},{"abstract":[{"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.","lang":"eng"}],"oa_version":"Preprint","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"url":"https://eprint.iacr.org/2020/337","open_access":"1"}],"month":"05","intvolume":" 12110","publication_identifier":{"eissn":["16113349"],"isbn":["9783030453732"],"issn":["03029743"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":12110,"ec_funded":1,"_id":"8339","type":"conference","conference":{"start_date":"2020-05-04","end_date":"2020-05-07","location":"Edinburgh, United Kingdom","name":"PKC: Public-Key Cryptography"},"status":"public","date_updated":"2023-02-23T13:31:06Z","department":[{"_id":"KrPi"}],"publisher":"Springer Nature","quality_controlled":"1","oa":1,"year":"2020","day":"15","publication":"23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography","page":"623-651","date_published":"2020-05-15T00:00:00Z","doi":"10.1007/978-3-030-45374-9_21","date_created":"2020-09-06T22:01:13Z","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"citation":{"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.","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.","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","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","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.","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.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Genise","full_name":"Genise, Nicholas","first_name":"Nicholas"},{"last_name":"Micciancio","full_name":"Micciancio, Daniele","first_name":"Daniele"},{"first_name":"Chris","last_name":"Peikert","full_name":"Peikert, Chris"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","last_name":"Walter","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482"}],"article_processing_charge":"No","title":"Improved discrete Gaussian and subgaussian analysis for lattice cryptography"},{"main_file_link":[{"url":"https://eprint.iacr.org/2020/418","open_access":"1"}],"scopus_import":"1","intvolume":" 12578","month":"12","abstract":[{"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.","lang":"eng"}],"oa_version":"Preprint","ec_funded":1,"volume":12578,"publication_status":"published","publication_identifier":{"isbn":["9783030652760"],"eissn":["16113349"],"issn":["03029743"]},"language":[{"iso":"eng"}],"conference":{"start_date":"2020-12-13","location":"Bangalore, India","end_date":"2020-12-16","name":"INDOCRYPT: International Conference on Cryptology in India"},"type":"conference","status":"public","_id":"8987","series_title":"LNCS","department":[{"_id":"KrPi"}],"date_updated":"2023-08-24T11:08:58Z","oa":1,"publisher":"Springer Nature","quality_controlled":"1","page":"3-15","date_created":"2021-01-03T23:01:23Z","date_published":"2020-12-08T00:00:00Z","doi":"10.1007/978-3-030-65277-7_1","year":"2020","isi":1,"publication":"Progress in Cryptology","day":"08","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"article_processing_charge":"No","external_id":{"isi":["000927592800001"]},"author":[{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"title":"Delayed authentication: Preventing replay and relay attacks in private contact tracing","citation":{"short":"K.Z. Pietrzak, in:, Progress in Cryptology, Springer Nature, 2020, pp. 3–15.","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.","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","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","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.","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.","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."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8"},{"date_published":"2020-05-01T00:00:00Z","doi":"10.1007/978-3-030-45727-3_16","date_created":"2020-06-15T07:13:37Z","page":"475-506","day":"01","publication":"Advances in Cryptology – EUROCRYPT 2020","isi":1,"year":"2020","quality_controlled":"1","publisher":"Springer Nature","oa":1,"title":"Everybody’s a target: Scalability in public-key encryption","author":[{"id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","last_name":"Auerbach"},{"first_name":"Federico","full_name":"Giacon, Federico","last_name":"Giacon"},{"first_name":"Eike","full_name":"Kiltz, Eike","last_name":"Kiltz"}],"article_processing_charge":"No","external_id":{"isi":["000828688000016"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"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.","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.","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","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.","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."},"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"volume":12107,"ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1611-3349"],"isbn":["9783030457266","9783030457273"],"issn":["0302-9743"]},"publication_status":"published","month":"05","intvolume":" 12107","alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/364"}],"oa_version":"Submitted Version","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."}],"department":[{"_id":"KrPi"}],"date_updated":"2023-09-05T15:06:40Z","status":"public","type":"conference","conference":{"name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","end_date":"2020-05-15","start_date":"2020-05-11"},"_id":"7966"},{"alternative_title":["ISTA Thesis"],"month":"05","abstract":[{"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. ","lang":"eng"}],"oa_version":"Published Version","ec_funded":1,"related_material":{"record":[{"relation":"part_of_dissertation","id":"6677","status":"public"}]},"degree_awarded":"PhD","publication_status":"published","publication_identifier":{"issn":["2663-337X"]},"language":[{"iso":"eng"}],"file":[{"checksum":"b39e2e1c376f5819b823fb7077491c64","file_id":"7897","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"2020_Thesis_Kamath.pdf","date_created":"2020-05-26T14:08:13Z","creator":"dernst","file_size":1622742,"date_updated":"2020-07-14T12:48:04Z"},{"date_created":"2020-05-26T14:08:23Z","file_name":"Thesis_Kamath.zip","date_updated":"2020-07-14T12:48:04Z","file_size":15301529,"creator":"dernst","file_id":"7898","checksum":"8b26ba729c1a85ac6bea775f5d73cdc7","content_type":"application/x-zip-compressed","access_level":"closed","relation":"source_file"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"dissertation","status":"public","_id":"7896","department":[{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:48:04Z","date_updated":"2023-09-07T13:15:55Z","supervisor":[{"orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"}],"ddc":["000"],"oa":1,"publisher":"Institute of Science and Technology Austria","page":"126","date_created":"2020-05-26T14:08:55Z","doi":"10.15479/AT:ISTA:7896","date_published":"2020-05-25T00:00:00Z","year":"2020","has_accepted_license":"1","day":"25","project":[{"call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425","name":"Provable Security for Physical Cryptography","grant_number":"259668"},{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"article_processing_charge":"No","author":[{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"}],"title":"On the average-case hardness of total search problems","citation":{"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.","ista":"Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.","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.","short":"C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020.","ieee":"C. Kamath Hosdurg, “On the average-case hardness of total search problems,” Institute of Science and Technology Austria, 2020.","ama":"Kamath Hosdurg C. On the average-case hardness of total search problems. 2020. doi:10.15479/AT:ISTA:7896","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"},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1"},{"scopus_import":"1","main_file_link":[{"url":"https://eprint.iacr.org/2016/166","open_access":"1"}],"month":"01","intvolume":" 27","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"}],"oa_version":"Preprint","volume":27,"issue":"1","ec_funded":1,"publication_identifier":{"issn":["0926227X"]},"publication_status":"published","language":[{"iso":"eng"}],"article_type":"original","type":"journal_article","status":"public","_id":"5887","department":[{"_id":"KrPi"}],"date_updated":"2021-01-12T08:05:08Z","publisher":"IOS Press","quality_controlled":"1","oa":1,"page":"75-111","doi":"10.3233/JCS-181131","date_published":"2019-01-01T00:00:00Z","date_created":"2019-01-27T22:59:10Z","year":"2019","day":"1","publication":"Journal of Computer Security","project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"author":[{"first_name":"Gregory","full_name":"Demay, Gregory","last_name":"Demay"},{"id":"3E0BFE38-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","last_name":"Gazi","full_name":"Gazi, Peter"},{"first_name":"Ueli","full_name":"Maurer, Ueli","last_name":"Maurer"},{"first_name":"Bjorn","full_name":"Tackmann, Bjorn","last_name":"Tackmann"}],"article_processing_charge":"No","title":"Per-session security: Password-based cryptography revisited","citation":{"short":"G. Demay, P. Gazi, U. Maurer, B. Tackmann, Journal of Computer Security 27 (2019) 75–111.","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.","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","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","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.","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.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"oa_version":"Published Version","abstract":[{"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.","lang":"eng"}],"month":"01","intvolume":" 124","scopus_import":1,"alternative_title":["LIPIcs"],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/627"}],"file":[{"creator":"dernst","date_updated":"2020-07-14T12:47:33Z","file_size":558770,"date_created":"2019-06-06T14:22:04Z","file_name":"2019_LIPIcs_Pietrzak.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"6529","checksum":"f0ae1bb161431d9db3dea5ace082bfb5"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-3-95977-095-8"],"issn":["1868-8969"]},"publication_status":"published","volume":124,"ec_funded":1,"_id":"6528","status":"public","type":"conference","conference":{"name":"ITCS 2019: Innovations in Theoretical Computer Science","start_date":"2019-01-10","location":"San Diego, CA, United States","end_date":"2019-01-12"},"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)"},"ddc":["000"],"date_updated":"2021-01-12T08:07:53Z","file_date_updated":"2020-07-14T12:47:33Z","department":[{"_id":"KrPi"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"day":"10","publication":"10th Innovations in Theoretical Computer Science Conference","has_accepted_license":"1","year":"2019","doi":"10.4230/LIPICS.ITCS.2019.60","date_published":"2019-01-10T00:00:00Z","date_created":"2019-06-06T14:12:36Z","article_number":"60","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","ista":"Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in Theoretical Computer Science Conference. ITCS 2019: Innovations in Theoretical Computer Science, LIPIcs, vol. 124, 60.","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.","ieee":"K. Z. Pietrzak, “Simple verifiable delay functions,” in 10th Innovations in Theoretical Computer Science Conference, San Diego, CA, United States, 2019, vol. 124.","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"},"title":"Simple verifiable delay functions","author":[{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No"},{"date_updated":"2023-02-23T12:50:15Z","department":[{"_id":"KrPi"}],"series_title":"LNCS","_id":"6726","status":"public","type":"book_chapter","conference":{"end_date":"2019-07-11","location":"Rabat, Morocco","start_date":"2019-07-09","name":"AFRICACRYPT: International Conference on Cryptology in Africa"},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-3-0302-3695-3"],"issn":["0302-9743","1611-3349"],"eisbn":["978-3-0302-3696-0"]},"publication_status":"published","volume":11627,"ec_funded":1,"oa_version":"Preprint","abstract":[{"lang":"eng","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."}],"month":"06","place":"Cham","intvolume":" 11627","scopus_import":"1","main_file_link":[{"url":"https://eprint.iacr.org/2019/068","open_access":"1"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","citation":{"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.","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","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","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.","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."},"title":"Sampling the integers with low relative error","editor":[{"first_name":"J","full_name":"Buchmann, J","last_name":"Buchmann"},{"first_name":"A","last_name":"Nitaj","full_name":"Nitaj, A"},{"first_name":"T","last_name":"Rachidi","full_name":"Rachidi, T"}],"author":[{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482"}],"article_processing_charge":"No","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"day":"29","publication":"Progress in Cryptology – AFRICACRYPT 2019","year":"2019","date_published":"2019-06-29T00:00:00Z","doi":"10.1007/978-3-030-23696-0_9","date_created":"2019-07-29T12:25:31Z","page":"157-180","quality_controlled":"1","publisher":"Springer Nature","oa":1},{"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|X2019 IEEE International Symposium on Information Theory. IEEE, 2019. 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.","short":"M. Skórski, in:, 2019 IEEE International Symposium on Information Theory, IEEE, 2019.","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","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","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","author":[{"id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","first_name":"Maciej","full_name":"Skórski, Maciej","last_name":"Skórski"}],"external_id":{"arxiv":["1702.08476"],"isi":["000489100301043"]},"article_processing_charge":"No","title":"Strong chain rules for min-entropy under few bits spoiled"}]