[{"title":"Anthemius: Efficient and modular block assembly for concurrent execution","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2502.10074","open_access":"1"}],"volume":15751,"day":"01","abstract":[{"text":"Many blockchains such as Ethereum execute all incoming transactions sequentially significantly limiting the potential throughput. A common approach to scale execution is parallel execution engines that fully utilize modern multi-core architectures. Parallel execution is then either done optimistically, by executing transactions in parallel and detecting conflicts on the fly, or guided, by requiring exhaustive client transaction hints and scheduling transactions accordingly.\r\n\r\nHowever, recent studies have shown that the performance of parallel execution engines depends on the nature of the underlying workload. In fact, in some cases, only a 60% speed-up compared to sequential execution could be obtained. This is the case, as transactions that access the same resources must be executed sequentially. For example, if 10% of the transactions in a block access the same resource, the execution cannot meaningfully scale beyond 10 cores. Therefore, a single popular application can bottleneck the execution and limit the potential throughput.\r\n\r\nIn this paper, we introduce Anthemius, a block construction algorithm that optimizes parallel transaction execution throughput. We evaluate Anthemius exhaustively under a range of workloads, and show that Anthemius enables the underlying parallel execution engine to process over twice as many transactions.","lang":"eng"}],"date_created":"2026-01-25T23:01:40Z","scopus_import":"1","quality_controlled":"1","author":[{"id":"f09651b9-fec0-11ec-b5d8-934aff0e52a4","first_name":"Ray","full_name":"Neiheiser, Ray","last_name":"Neiheiser","orcid":"0000-0001-7227-8309"},{"orcid":"0000-0002-8827-3382","last_name":"Kokoris Kogias","first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"}],"page":"307-323","doi":"10.1007/978-3-032-07024-1_18","_id":"21042","project":[{"_id":"34a1b658-11ca-11ed-8bc3-c75229f0241e","name":"Interface Theory for Security and Privacy","grant_number":"F8502"},{"name":"SeCure, privAte, and interoperabLe layEr 2","grant_number":"ICT22-045","_id":"7bdd2f70-9f16-11ee-852c-b7950bc6d277"}],"publication":"29th International Conference on Financial Cryptography and Data Security","type":"conference","acknowledgement":"This work was supported by the Austrian Science Fund (FWF) SFB project SpyCoDe F8502 and the Vienna Science and Technology Fund (WWTF) project SCALE2 CT22-045.","citation":{"ama":"Neiheiser R, Kokoris Kogias E. Anthemius: Efficient and modular block assembly for concurrent execution. In: <i>29th International Conference on Financial Cryptography and Data Security</i>. Vol 15751. Springer Nature; 2026:307-323. doi:<a href=\"https://doi.org/10.1007/978-3-032-07024-1_18\">10.1007/978-3-032-07024-1_18</a>","apa":"Neiheiser, R., &#38; Kokoris Kogias, E. (2026). Anthemius: Efficient and modular block assembly for concurrent execution. In <i>29th International Conference on Financial Cryptography and Data Security</i> (Vol. 15751, pp. 307–323). Miyakojima, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-07024-1_18\">https://doi.org/10.1007/978-3-032-07024-1_18</a>","ieee":"R. Neiheiser and E. Kokoris Kogias, “Anthemius: Efficient and modular block assembly for concurrent execution,” in <i>29th International Conference on Financial Cryptography and Data Security</i>, Miyakojima, Japan, 2026, vol. 15751, pp. 307–323.","mla":"Neiheiser, Ray, and Eleftherios Kokoris Kogias. “Anthemius: Efficient and Modular Block Assembly for Concurrent Execution.” <i>29th International Conference on Financial Cryptography and Data Security</i>, vol. 15751, Springer Nature, 2026, pp. 307–23, doi:<a href=\"https://doi.org/10.1007/978-3-032-07024-1_18\">10.1007/978-3-032-07024-1_18</a>.","short":"R. Neiheiser, E. Kokoris Kogias, in:, 29th International Conference on Financial Cryptography and Data Security, Springer Nature, 2026, pp. 307–323.","chicago":"Neiheiser, Ray, and Eleftherios Kokoris Kogias. “Anthemius: Efficient and Modular Block Assembly for Concurrent Execution.” In <i>29th International Conference on Financial Cryptography and Data Security</i>, 15751:307–23. Springer Nature, 2026. <a href=\"https://doi.org/10.1007/978-3-032-07024-1_18\">https://doi.org/10.1007/978-3-032-07024-1_18</a>.","ista":"Neiheiser R, Kokoris Kogias E. 2026. Anthemius: Efficient and modular block assembly for concurrent execution. 29th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 15751, 307–323."},"external_id":{"arxiv":["2502.10074"]},"arxiv":1,"intvolume":"     15751","oa":1,"article_processing_charge":"No","department":[{"_id":"KrPi"}],"conference":{"start_date":"2025-04-14","name":"FC: Financial Cryptography and Data Security","end_date":"2025-04-18","location":"Miyakojima, Japan"},"month":"01","date_published":"2026-01-01T00:00:00Z","date_updated":"2026-02-12T13:39:07Z","publication_status":"published","publisher":"Springer Nature","year":"2026","status":"public","corr_author":"1","OA_place":"repository","publication_identifier":{"issn":["0302-9743"],"isbn":["9783032070234"],"eissn":["1611-3349"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"oa_version":"Preprint","OA_type":"green"},{"month":"01","date_published":"2026-01-01T00:00:00Z","date_updated":"2026-04-15T08:45:18Z","publication_status":"published","publisher":"Springer Nature","oa":1,"article_processing_charge":"No","department":[{"_id":"KrPi"}],"conference":{"start_date":"2025-04-14","name":"FC: Financial Cryptography and Data Security","end_date":"2025-04-18","location":"Miyakojima, Japan"},"OA_place":"repository","publication_identifier":{"isbn":["9783032070340"],"issn":["0302-9743"],"eissn":["1611-3349"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"oa_version":"Preprint","OA_type":"green","status":"public","year":"2026","corr_author":"1","scopus_import":"1","title":"On the (in)security of Proofs-of-space based longest-chain blockchains","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2505.14891"}],"language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"21651"}]},"volume":15752,"abstract":[{"lang":"eng","text":"The Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof of work as a voting mechanism. Honest miners who contribute hashing power towards securing the chain try to extend the longest chain they are aware of. Despite its simplicity, Nakamoto consensus achieves meaningful security guarantees assuming that at any point in time, a majority of the hashing power is controlled by honest parties. This also holds under “resource variability”, i.e., if the total hashing power varies greatly over time.\r\nProofs of space (PoSpace) have been suggested as a more sustainable replacement for proofs of work. Unfortunately, no construction of a “longest-chain” blockchain based on PoSpace, that is secure under dynamic availability, is known. In this work, we prove that without additional assumptions no such protocol exists. We exactly quantify this impossibility result by proving a bound on the length of the fork required for double spending as a function of the adversarial capabilities. This bound holds for any chain selection rule, and we also show a chain selection rule (albeit a very strange one) that almost matches this bound.\r\nThe Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof of work as a voting mechanism. Honest miners who contribute hashing power towards securing the chain try to extend the longest chain they are aware of. Despite its simplicity, Nakamoto consensus achieves meaningful security guarantees assuming that at any point in time, a majority of the hashing power is controlled by honest parties. This also holds under “resource variability”, i.e., if the total hashing power varies greatly over time.\r\n\r\nProofs of space (PoSpace) have been suggested as a more sustainable replacement for proofs of work. Unfortunately, no construction of a “longest-chain” blockchain based on PoSpace, that is secure under dynamic availability, is known. In this work, we prove that without additional assumptions no such protocol exists. We exactly quantify this impossibility result by proving a bound on the length of the fork required for double spending as a function of the adversarial capabilities. This bound holds for any chain selection rule, and we also show a chain selection rule (albeit a very strange one) that almost matches this bound.\r\n\r\nConcretely, we consider a security game in which the honest parties at any point control 0 > 1\r\n times more space than the adversary. The adversary can change the honest space by a factor 1+- E with every block (dynamic availability), and “replotting” the space (which allows answering two challenges using the same space) takes as much time as p blocks.\r\nWe prove that no matter what chain selection rule is used, in this game the adversary can create a fork of length o^2 . p/E that will be picked as the winner by the chain selection rule.\r\nWe also provide an upper bound that matches the lower bound up to a factor o. There exists a chain selection rule (albeit a very strange one) which in the above game requires forks of length at least o . p/E\r\nOur results show the necessity of additional assumptions to create a secure PoSpace based longest-chain blockchain. The Chia network in addition to PoSpace uses a verifiable delay function. Our bounds show that an additional primitive like that is necessary."}],"day":"01","date_created":"2026-02-01T23:01:43Z","publication":"29th International Conference on Financial Cryptography and Data Security","type":"conference","citation":{"ista":"Baig MA, Pietrzak KZ. 2026. On the (in)security of Proofs-of-space based longest-chain blockchains. 29th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 15752, 127–142.","chicago":"Baig, Mirza Ahad, and Krzysztof Z Pietrzak. “On the (in)Security of Proofs-of-Space Based Longest-Chain Blockchains.” In <i>29th International Conference on Financial Cryptography and Data Security</i>, 15752:127–42. Springer Nature, 2026. <a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">https://doi.org/10.1007/978-3-032-07035-7_8</a>.","short":"M.A. Baig, K.Z. Pietrzak, in:, 29th International Conference on Financial Cryptography and Data Security, Springer Nature, 2026, pp. 127–142.","ieee":"M. A. Baig and K. Z. Pietrzak, “On the (in)security of Proofs-of-space based longest-chain blockchains,” in <i>29th International Conference on Financial Cryptography and Data Security</i>, Miyakojima, Japan, 2026, vol. 15752, pp. 127–142.","mla":"Baig, Mirza Ahad, and Krzysztof Z. Pietrzak. “On the (in)Security of Proofs-of-Space Based Longest-Chain Blockchains.” <i>29th International Conference on Financial Cryptography and Data Security</i>, vol. 15752, Springer Nature, 2026, pp. 127–42, doi:<a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">10.1007/978-3-032-07035-7_8</a>.","apa":"Baig, M. A., &#38; Pietrzak, K. Z. (2026). On the (in)security of Proofs-of-space based longest-chain blockchains. In <i>29th International Conference on Financial Cryptography and Data Security</i> (Vol. 15752, pp. 127–142). Miyakojima, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">https://doi.org/10.1007/978-3-032-07035-7_8</a>","ama":"Baig MA, Pietrzak KZ. On the (in)security of Proofs-of-space based longest-chain blockchains. In: <i>29th International Conference on Financial Cryptography and Data Security</i>. Vol 15752. Springer Nature; 2026:127-142. doi:<a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">10.1007/978-3-032-07035-7_8</a>"},"acknowledgement":"This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/F85.","external_id":{"arxiv":["2505.14891"]},"arxiv":1,"intvolume":"     15752","quality_controlled":"1","page":"127-142","author":[{"last_name":"Baig","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad","full_name":"Baig, Mirza Ahad"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"doi":"10.1007/978-3-032-07035-7_8","_id":"21134","project":[{"grant_number":"F8509","name":"Security and Privacy by Design for Complex Systems","_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1"}]},{"related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"21134"},{"status":"public","id":"20587","relation":"part_of_dissertation"}]},"language":[{"iso":"eng"}],"title":"On secure chain selection rules from physical resources in a permissionless setting","file_date_updated":"2026-04-15T07:37:25Z","date_created":"2026-04-02T09:31:34Z","day":"04","abstract":[{"text":"Blockchains enable distributed consensus in permissionless settings, where participants\r\nare unknown, dynamically changing, and do not trust each other. While Bitcoin,\r\nbased on Proof-of-Work (PoW), was the first protocol in this model, significant\r\nresearch has focused on permissionless protocols using alternative physical resources,\r\nspecifically Proof-of-Space (PoSpace) and Verifiable Delay Functions (VDFs). This\r\nthesis investigates the theoretical limits and design space of longest-chain protocols in\r\nthe fully permissionless and dynamically available settings using these three resources.\r\nFirst, we address the feasibility of blockchains relying solely on storage as a resource.\r\nWe prove a fundamental impossibility result: there exists no secure longest-chain\r\nprotocol based exclusively on Proof-of-Space in the fully permissionless or dynamically\r\navailable settings. Further, we quantify the adversarial capabilities required to execute\r\na double-spend attack. Our result formally justifies the necessity of coupling PoSpace\r\nwith time-dependent primitives (such as VDFs) or to move to less permissive settings\r\n(quasi-permissionless or permissioned) to ensure security.\r\nSecond, we generalize Nakamoto-like heaviest chain consensus to protocols utilizing\r\ncombinations of multiple physical resources. We analyze chain selection rules governed\r\nby a weight function Γ(S, V,W), which assigns weight to blocks based on recorded\r\nSpace (S), VDF speed (V ), and Work (W). We provide a complete classification\r\nof secure weight functions, proving that a weight function is secure against private\r\ndouble-spend attacks if and only if it is homogeneous in the timed resources (V,W)\r\nand sub-homogeneous in S. This framework unifies existing protocols like Bitcoin and\r\nChia under a single theoretical model and provides a powerful tool for designing new\r\nlongest-chain blockchains from a mix of physical resources.","lang":"eng"}],"supervisor":[{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"author":[{"first_name":"Mirza Ahad","full_name":"Baig, Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","last_name":"Baig"}],"_id":"21651","doi":"10.15479/AT-ISTA-21651","type":"dissertation","ddc":["000"],"citation":{"ista":"Baig MA. 2026. On secure chain selection rules from physical resources in a permissionless setting. Institute of Science and Technology Austria.","chicago":"Baig, Mirza Ahad. “On Secure Chain Selection Rules from Physical Resources in a Permissionless Setting.” Institute of Science and Technology Austria, 2026. <a href=\"https://doi.org/10.15479/AT-ISTA-21651\">https://doi.org/10.15479/AT-ISTA-21651</a>.","short":"M.A. Baig, On Secure Chain Selection Rules from Physical Resources in a Permissionless Setting, Institute of Science and Technology Austria, 2026.","mla":"Baig, Mirza Ahad. <i>On Secure Chain Selection Rules from Physical Resources in a Permissionless Setting</i>. Institute of Science and Technology Austria, 2026, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-21651\">10.15479/AT-ISTA-21651</a>.","ieee":"M. A. Baig, “On secure chain selection rules from physical resources in a permissionless setting,” Institute of Science and Technology Austria, 2026.","apa":"Baig, M. A. (2026). <i>On secure chain selection rules from physical resources in a permissionless setting</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-21651\">https://doi.org/10.15479/AT-ISTA-21651</a>","ama":"Baig MA. On secure chain selection rules from physical resources in a permissionless setting. 2026. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-21651\">10.15479/AT-ISTA-21651</a>"},"oa":1,"article_processing_charge":"No","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"publication_status":"published","date_updated":"2026-04-15T08:45:19Z","month":"03","date_published":"2026-03-04T00:00:00Z","publisher":"Institute of Science and Technology Austria","year":"2026","status":"public","degree_awarded":"PhD","corr_author":"1","has_accepted_license":"1","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-078-7"]},"OA_place":"publisher","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","oa_version":"Published Version","alternative_title":["ISTA Thesis"],"file":[{"date_updated":"2026-04-13T08:24:13Z","creator":"mbaig","content_type":"application/x-zip-compressed","access_level":"closed","file_size":139353434,"checksum":"c3986dba90653dac97adba662ebff238","file_id":"21655","relation":"source_file","file_name":"PhD-Thesis-Mirza-Ahad-Baig - Library Submission.zip","date_created":"2026-04-03T17:28:48Z"},{"relation":"main_file","date_created":"2026-04-03T17:29:30Z","file_name":"2026_Baig_Mirza_Ahad_Thesis.pdf","file_id":"21656","checksum":"292a5989262521f7c145a109d1f348cb","access_level":"open_access","file_size":1942037,"content_type":"application/pdf","creator":"mbaig","date_updated":"2026-04-15T07:37:25Z"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","short":"CC BY-NC-SA (4.0)","image":"/images/cc_by_nc_sa.png","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"}},{"_id":"22007","doi":"10.4230/LIPIcs.ITC.2025.4","quality_controlled":"1","author":[{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wang, Pengxiang","first_name":"Pengxiang","last_name":"Wang"}],"external_id":{"cryptoeprintid":["2025/723"]},"ddc":["000"],"citation":{"ama":"Pietrzak KZ, Wang P. Time-space tradeoffs of truncation with preprocessing. In: <i>6th Conference on Information-Theoretic Cryptography</i>. Vol 343. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITC.2025.4\">10.4230/LIPIcs.ITC.2025.4</a>","apa":"Pietrzak, K. Z., &#38; Wang, P. (2025). Time-space tradeoffs of truncation with preprocessing. In <i>6th Conference on Information-Theoretic Cryptography</i> (Vol. 343). Santa Barbara, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITC.2025.4\">https://doi.org/10.4230/LIPIcs.ITC.2025.4</a>","ieee":"K. Z. Pietrzak and P. Wang, “Time-space tradeoffs of truncation with preprocessing,” in <i>6th Conference on Information-Theoretic Cryptography</i>, Santa Barbara, CA, United States, 2025, vol. 343.","mla":"Pietrzak, Krzysztof Z., and Pengxiang Wang. “Time-Space Tradeoffs of Truncation with Preprocessing.” <i>6th Conference on Information-Theoretic Cryptography</i>, vol. 343, 4:1-4:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITC.2025.4\">10.4230/LIPIcs.ITC.2025.4</a>.","short":"K.Z. Pietrzak, P. Wang, in:, 6th Conference on Information-Theoretic Cryptography, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","chicago":"Pietrzak, Krzysztof Z, and Pengxiang Wang. “Time-Space Tradeoffs of Truncation with Preprocessing.” In <i>6th Conference on Information-Theoretic Cryptography</i>, Vol. 343. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ITC.2025.4\">https://doi.org/10.4230/LIPIcs.ITC.2025.4</a>.","ista":"Pietrzak KZ, Wang P. 2025. Time-space tradeoffs of truncation with preprocessing. 6th Conference on Information-Theoretic Cryptography. ITC: Information Theoretic Cryptography, LIPIcs, vol. 343, 4:1-4:10."},"intvolume":"       343","type":"conference","publication":"6th Conference on Information-Theoretic Cryptography","date_created":"2026-06-14T22:01:45Z","abstract":[{"lang":"eng","text":"Truncation of cryptographic outputs is a technique that was recently introduced in Baldimtsi et al. [Foteini Baldimtsi et al., 2022]. The general idea is to try out many inputs to some cryptographic algorithm until the output (e.g. a public-key or some hash value) falls into some sparse set and thus can be compressed: by trying out an expected 2^k different inputs one will find an output that starts with k zeros.\r\nUsing such truncation one can for example save substantial gas fees on Blockchains where storing values is very expensive. While [Foteini Baldimtsi et al., 2022] show that truncation preserves the security of the underlying primitive, they only consider a setting without preprocessing. In this work we show that lower bounds on the time-space tradeoff for inverting random functions and permutations also hold with truncation, except for parameters ranges where the bound fails to hold for \"trivial\" reasons.\r\nConcretely, it’s known that any algorithm that inverts a random function or permutation with range N making T queries and using S bits of auxiliary input must satisfy S⋅ T ≥ Nlog N. This lower bound no longer holds in the truncated setting where one must only invert a challenge from a range of size N/2^k, as now one can simply save the replies to all N/2^k challenges, which requires S = log N⋅ N /2^k bits and allows to invert with T = 1 query.\r\nWe show that with truncation, whenever S is somewhat smaller than the log N⋅ N /2^k bits required to store the entire truncated function table, the known S⋅ T ≥ Nlog N lower bound applies."}],"day":"08","language":[{"iso":"eng"}],"title":"Time-space tradeoffs of truncation with preprocessing","volume":343,"keyword":["Time-Space Lower Bounds","Blockchains"],"file_date_updated":"2026-06-22T08:54:32Z","scopus_import":"1","has_accepted_license":"1","corr_author":"1","status":"public","year":"2025","oa_version":"Published Version","alternative_title":["LIPIcs"],"file":[{"file_name":"2025_LIPIcs_Pietrzak.pdf","date_created":"2026-06-22T08:54:32Z","relation":"main_file","file_id":"22118","creator":"dernst","access_level":"open_access","content_type":"application/pdf","checksum":"3f791b03df26853342855a9d9581cb58","file_size":772046,"success":1,"date_updated":"2026-06-22T08:54:32Z"}],"OA_type":"gold","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773850"]},"OA_place":"publisher","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"Yes","conference":{"name":"ITC: Information Theoretic Cryptography","start_date":"2025-08-16","location":"Santa Barbara, CA, United States","end_date":"2025-08-17"},"department":[{"_id":"KrPi"}],"article_number":"4:1-4:10","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","das_tickbox":"0","date_updated":"2026-06-22T08:57:41Z","publication_status":"published","cryptoeprintid":1,"date_published":"2025-09-08T00:00:00Z","month":"09"},{"scopus_import":"1","abstract":[{"lang":"eng","text":"We introduce and construct a new proof system called Non-interactive Arguments of Knowledge or Space (NArKoS), where a space-bounded prover can convince a verifier they know a secret, while having access to sufficient space allows one to forge indistinguishable proofs without the secret.\r\nAn application of NArKoS are space-deniable proofs, which are proofs of knowledge (say for authentication in access control) that are sound when executed by a lightweight device like a smart-card or an RFID chip that cannot have much storage, but are deniable (in the strong sense of online deniability) as the verifier, like a card reader, can efficiently forge such proofs.\r\nWe construct NArKoS in the random oracle model using an OR-proof combining a sigma protocol (for the proof of knowledge of the secret) with a new proof system called simulatable Proof of Transient Space (simPoTS). We give two different constructions of simPoTS, one based on labelling graphs with high pebbling complexity, a technique used in the construction of memory-hard functions and proofs of space, and a more practical construction based on the verifiable space-hard functions from TCC’24 where a prover must compute a root of a sparse polynomial. In both cases, the main challenge is making the proofs efficiently simulatable."}],"day":"05","date_created":"2025-12-21T23:01:33Z","title":"Space-deniable proofs","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/1723"}],"volume":16271,"acknowledgement":"Jesko Dujmovic: Funded by the European Union (ERC, LACONIC, 101041207). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.\r\nChristoph U. Günther and Krzysztof Pietrzak: This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/F85. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission.","citation":{"short":"J. Dujmovic, C.U. Günther, K.Z. Pietrzak, in:, 23rd International Conference on Theory of Cryptography, Springer Nature, 2025, pp. 171–202.","chicago":"Dujmovic, Jesko, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Space-Deniable Proofs.” In <i>23rd International Conference on Theory of Cryptography</i>, 16271:171–202. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-12290-2_6\">https://doi.org/10.1007/978-3-032-12290-2_6</a>.","ista":"Dujmovic J, Günther CU, Pietrzak KZ. 2025. Space-deniable proofs. 23rd International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 16271, 171–202.","ama":"Dujmovic J, Günther CU, Pietrzak KZ. Space-deniable proofs. In: <i>23rd International Conference on Theory of Cryptography</i>. Vol 16271. Springer Nature; 2025:171-202. doi:<a href=\"https://doi.org/10.1007/978-3-032-12290-2_6\">10.1007/978-3-032-12290-2_6</a>","apa":"Dujmovic, J., Günther, C. U., &#38; Pietrzak, K. Z. (2025). Space-deniable proofs. In <i>23rd International Conference on Theory of Cryptography</i> (Vol. 16271, pp. 171–202). Aarhus, Denmark: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-12290-2_6\">https://doi.org/10.1007/978-3-032-12290-2_6</a>","mla":"Dujmovic, Jesko, et al. “Space-Deniable Proofs.” <i>23rd International Conference on Theory of Cryptography</i>, vol. 16271, Springer Nature, 2025, pp. 171–202, doi:<a href=\"https://doi.org/10.1007/978-3-032-12290-2_6\">10.1007/978-3-032-12290-2_6</a>.","ieee":"J. Dujmovic, C. U. Günther, and K. Z. Pietrzak, “Space-deniable proofs,” in <i>23rd International Conference on Theory of Cryptography</i>, Aarhus, Denmark, 2025, vol. 16271, pp. 171–202."},"intvolume":"     16271","type":"conference","publication":"23rd International Conference on Theory of Cryptography","doi":"10.1007/978-3-032-12290-2_6","_id":"20844","project":[{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","name":"Security and Privacy by Design for Complex Systems","grant_number":"F8509"}],"quality_controlled":"1","author":[{"full_name":"Dujmovic, Jesko","first_name":"Jesko","last_name":"Dujmovic"},{"last_name":"Günther","full_name":"Günther, Christoph Ullrich","first_name":"Christoph Ullrich","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"}],"page":"171-202","publisher":"Springer Nature","date_published":"2025-12-05T00:00:00Z","month":"12","publication_status":"published","date_updated":"2025-12-29T11:44:16Z","article_processing_charge":"No","department":[{"_id":"KrPi"}],"conference":{"name":"TCC: Theory of Cryptography","start_date":"2025-12-01","location":"Aarhus, Denmark","end_date":"2025-12-05"},"oa":1,"alternative_title":["LNCS"],"oa_version":"Preprint","OA_type":"green","OA_place":"repository","publication_identifier":{"isbn":["9783032122896"],"issn":["0302-9743"],"eissn":["1611-3349"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","year":"2025","status":"public"},{"acknowledgement":"We thank Rachel Lin for expressing concern about the applicability of “HJL-style” attacks [15] on the construction in [2] during a talk by the first author about [2]. This was the starting point of the investigation that led us to develop the attack in [5, Sec 4.1]. The first author also thanks Hoeteck Wee for sharing his rationale for introducing evasive LWE.\r\nThe first author is supported by the CyStar center of excellence, the VHAR faculty chair, and the C3iHub fellowship. The third author thanks Cystar, IIT Madras, for supporting a visit to IIT Madras during which the collaboration was initiated. The 4th author is partly supported by JST CREST Grant Number JPMJCR22M1.","citation":{"chicago":"Agrawal, Shweta, Anuja Modi, Anshu Yadav, and Shota Yamada. “Zeroizing Attacks against Evasive and Circular Evasive LWE.” In <i>23rd International Conference on Theory of Cryptography</i>, 16269:259–90. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-12293-3_9\">https://doi.org/10.1007/978-3-032-12293-3_9</a>.","short":"S. Agrawal, A. Modi, A. Yadav, S. Yamada, in:, 23rd International Conference on Theory of Cryptography, Springer Nature, 2025, pp. 259–290.","ista":"Agrawal S, Modi A, Yadav A, Yamada S. 2025. Zeroizing attacks against evasive and circular evasive LWE. 23rd International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 16269, 259–290.","apa":"Agrawal, S., Modi, A., Yadav, A., &#38; Yamada, S. (2025). Zeroizing attacks against evasive and circular evasive LWE. In <i>23rd International Conference on Theory of Cryptography</i> (Vol. 16269, pp. 259–290). Aarhus, Denmark: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-12293-3_9\">https://doi.org/10.1007/978-3-032-12293-3_9</a>","ama":"Agrawal S, Modi A, Yadav A, Yamada S. Zeroizing attacks against evasive and circular evasive LWE. In: <i>23rd International Conference on Theory of Cryptography</i>. Vol 16269. Springer Nature; 2025:259-290. doi:<a href=\"https://doi.org/10.1007/978-3-032-12293-3_9\">10.1007/978-3-032-12293-3_9</a>","mla":"Agrawal, Shweta, et al. “Zeroizing Attacks against Evasive and Circular Evasive LWE.” <i>23rd International Conference on Theory of Cryptography</i>, vol. 16269, Springer Nature, 2025, pp. 259–90, doi:<a href=\"https://doi.org/10.1007/978-3-032-12293-3_9\">10.1007/978-3-032-12293-3_9</a>.","ieee":"S. Agrawal, A. Modi, A. Yadav, and S. Yamada, “Zeroizing attacks against evasive and circular evasive LWE,” in <i>23rd International Conference on Theory of Cryptography</i>, Aarhus, Denmark, 2025, vol. 16269, pp. 259–290."},"intvolume":"     16269","type":"conference","publication":"23rd International Conference on Theory of Cryptography","doi":"10.1007/978-3-032-12293-3_9","_id":"20845","quality_controlled":"1","page":"259-290","author":[{"last_name":"Agrawal","first_name":"Shweta","full_name":"Agrawal, Shweta"},{"last_name":"Modi","full_name":"Modi, Anuja","first_name":"Anuja"},{"last_name":"Yadav","full_name":"Yadav, Anshu","first_name":"Anshu","id":"dc8f1524-403e-11ee-bf07-9649ad996e21"},{"last_name":"Yamada","first_name":"Shota","full_name":"Yamada, Shota"}],"scopus_import":"1","day":"05","abstract":[{"lang":"eng","text":"We develop new attacks against the Evasive LWE family of assumptions, in both the public and private-coin regime. To the best of our knowledge, ours are the first attacks against Evasive LWE in the public-coin regime, for any instantiation from the family. Our attacks are summarized below.\r\n\r\nPublic-Coin Attacks.\r\n1.The recent work by Hseih, Lin and Luo [17] constructed the first Attribute Based Encryption (ABE) for unbounded depth circuits by relying on the “circular” evasive LWE assumption. This assumption has been popularly considered as a safe, public-coin instance of Evasive LWE in contrast to its “private-coin” cousins (for instance, see [10, 11]).\r\nWe provide the first attack against this assumption, challenging the widely held belief that this is a public-coin assumption.\r\n2. We demonstrate a counter-example against vanilla public-coin evasive LWE by Wee [26] in an unnatural parameter regime. Our attack crucially relies on the error in the pre-condition being larger than the error in the post-condition, necessitating a refinement of the assumption.\r\n\r\nPrivate-Coin Attacks.\r\n1. The recent work by Agrawal, Kumari and Yamada [2] constructed the first functional encryption scheme for pseudorandom functionalities (PRFE) and extended this to obfuscation for pseudorandom functionalities (PRIO) [4] by relying on private-coin evasive LWE. We provide a new attack against the assumption stated in the first posting of their work (subsequently refined to avoid these attacks).\r\n2. The recent work by Branco et al. [8] (concurrently to [4]) provides a construction of obfuscation for pseudorandom functionalities by relying on private-coin evasive LWE. We provide a new attack against their stated assumption.\r\n3. Branco et al. [8] showed that there exist contrived, “self-referential” classes of pseudorandom functionalities for which pseudorandom obfuscation cannot exist. We extend their techniques to develop an analogous result for pseudorandom functional encryption.\r\n\r\nWhile Evasive LWE was developed to specifically avoid “zeroizing attacks”, our work shows that in certain settings, such attacks can still apply."}],"date_created":"2025-12-21T23:01:33Z","title":"Zeroizing attacks against evasive and circular evasive LWE","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://eprint.iacr.org/2025/375","open_access":"1"}],"volume":16269,"alternative_title":["LNCS"],"oa_version":"Preprint","OA_type":"green","OA_place":"repository","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783032122926"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","year":"2025","publisher":"Springer Nature","month":"12","date_published":"2025-12-05T00:00:00Z","date_updated":"2025-12-29T11:51:13Z","publication_status":"published","article_processing_charge":"No","department":[{"_id":"KrPi"}],"conference":{"start_date":"2025-12-01","name":"TCC: Theory of Cryptography","end_date":"2025-12-05","location":"Aarhus, Denmark"},"oa":1},{"type":"conference","publication":"23rd International Conference on Theory of Cryptography","intvolume":"     16271","citation":{"ista":"Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. 2025. Constrained verifiable random functions without obfuscation and friends. 23rd International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 16271, 478–511.","short":"N. Brandt, M. Cueto Noval, C.U. Günther, A. Ünal, S. Wohnig, in:, 23rd International Conference on Theory of Cryptography, Springer Nature, 2025, pp. 478–511.","chicago":"Brandt, Nicholas, Miguel Cueto Noval, Christoph Ullrich Günther, Akin Ünal, and Stella Wohnig. “Constrained Verifiable Random Functions without Obfuscation and Friends.” In <i>23rd International Conference on Theory of Cryptography</i>, 16271:478–511. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-12290-2_16\">https://doi.org/10.1007/978-3-032-12290-2_16</a>.","ieee":"N. Brandt, M. Cueto Noval, C. U. Günther, A. Ünal, and S. Wohnig, “Constrained verifiable random functions without obfuscation and friends,” in <i>23rd International Conference on Theory of Cryptography</i>, Aarhus, Denmark, 2025, vol. 16271, pp. 478–511.","mla":"Brandt, Nicholas, et al. “Constrained Verifiable Random Functions without Obfuscation and Friends.” <i>23rd International Conference on Theory of Cryptography</i>, vol. 16271, Springer Nature, 2025, pp. 478–511, doi:<a href=\"https://doi.org/10.1007/978-3-032-12290-2_16\">10.1007/978-3-032-12290-2_16</a>.","ama":"Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. Constrained verifiable random functions without obfuscation and friends. In: <i>23rd International Conference on Theory of Cryptography</i>. Vol 16271. Springer Nature; 2025:478-511. doi:<a href=\"https://doi.org/10.1007/978-3-032-12290-2_16\">10.1007/978-3-032-12290-2_16</a>","apa":"Brandt, N., Cueto Noval, M., Günther, C. U., Ünal, A., &#38; Wohnig, S. (2025). Constrained verifiable random functions without obfuscation and friends. In <i>23rd International Conference on Theory of Cryptography</i> (Vol. 16271, pp. 478–511). Aarhus, Denmark: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-12290-2_16\">https://doi.org/10.1007/978-3-032-12290-2_16</a>"},"acknowledgement":"We thank Jonas Steinbach and Gertjan De Mulder for helpful discussions on BIP 32, Dennis Hofheinz and Julia Kastner for helpful discussions on early prototypes of our CVRF, and Klaus Kraßnitzer for running pairing benchmarks on his MacBook Pro.\r\nChristoph U. Günther: This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/F85. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission.","author":[{"last_name":"Brandt","first_name":"Nicholas","full_name":"Brandt, Nicholas"},{"id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","full_name":"Cueto Noval, Miguel","first_name":"Miguel","last_name":"Cueto Noval","orcid":"0000-0002-2505-4246"},{"last_name":"Günther","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","first_name":"Christoph Ullrich","full_name":"Günther, Christoph Ullrich"},{"id":"f6b56fb6-dc63-11ee-9dbf-f6780863a85a","full_name":"Ünal, Akin","first_name":"Akin","last_name":"Ünal","orcid":"0000-0002-8929-0221"},{"last_name":"Wohnig","first_name":"Stella","full_name":"Wohnig, Stella"}],"page":"478-511","quality_controlled":"1","project":[{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","grant_number":"F8509","name":"Security and Privacy by Design for Complex Systems"}],"_id":"20846","doi":"10.1007/978-3-032-12290-2_16","scopus_import":"1","volume":16271,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/1045"}],"language":[{"iso":"eng"}],"title":"Constrained verifiable random functions without obfuscation and friends","date_created":"2025-12-21T23:01:34Z","abstract":[{"lang":"eng","text":"CVRFs are PRFs that unify the properties of verifiable and constrained PRFs. Since they were introduced concurrently by Fuchsbauer and Chandran-Raghuraman-Vinayagamurthy in 2014, it has been an open problem to construct CVRFs without using heavy machinery such as multilinear maps, obfuscation or functional encryption.\r\nWe solve this problem by constructing a prefix-constrained verifiable PRF that does not rely on the aforementioned assumptions. Essentially, our construction is a verifiable version of the Goldreich-Goldwasser-Micali PRF. To achieve verifiability we leverage degree-2 algebraic PRGs and bilinear groups. In short, proofs consist of intermediate values of the Goldreich-Goldwasser-Micali PRF raised to the exponents of group elements. These outputs can be verified using pairings since the underlying PRG is of degree 2.\r\nWe prove the selective security of our construction under the Decisional Square Diffie-Hellman (DSDH) assumption and a new assumption, which we dub recursive Decisional Diffie-Hellman (recursive DDH).\r\nWe prove the soundness of recursive DDH in the generic group model assuming the hardness of the Multivariate Quadratic (MQ) problem and a new variant thereof, which we call MQ+.\r\nLast, in terms of applications, we observe that our CVRF is also an exponent (C)VRF in the plain model. Exponent VRFs were recently introduced by Boneh et al. (Eurocrypt’25) with various applications to threshold cryptography in mind. In addition to that, we give further applications for prefix-CVRFs in the blockchain setting, namely, stake-pooling and compressible randomness beacons."}],"day":"05","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783032122896"]},"OA_place":"repository","OA_type":"green","oa_version":"Preprint","alternative_title":["LNCS"],"status":"public","year":"2025","corr_author":"1","publication_status":"published","date_updated":"2025-12-29T11:11:29Z","month":"12","date_published":"2025-12-05T00:00:00Z","publisher":"Springer Nature","oa":1,"conference":{"name":"TCC: Theory of Cryptography","start_date":"2025-12-01","location":"Aarhus, Denmark","end_date":"2025-12-05"},"department":[{"_id":"KrPi"}],"article_processing_charge":"No"},{"author":[{"last_name":"Hoffmann","orcid":"0000-0003-2027-5549","id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7","first_name":"Charlotte","full_name":"Hoffmann, Charlotte"}],"page":"116","doi":"10.15479/AT-ISTA-20920","_id":"20920","type":"dissertation","citation":{"ista":"Hoffmann C. 2025. Theory and applications of verifiable delay functions. Institute of Science and Technology Austria.","chicago":"Hoffmann, Charlotte. “Theory and Applications of Verifiable Delay Functions.” Institute of Science and Technology Austria, 2025. <a href=\"https://doi.org/10.15479/AT-ISTA-20920\">https://doi.org/10.15479/AT-ISTA-20920</a>.","short":"C. Hoffmann, Theory and Applications of Verifiable Delay Functions, Institute of Science and Technology Austria, 2025.","mla":"Hoffmann, Charlotte. <i>Theory and Applications of Verifiable Delay Functions</i>. Institute of Science and Technology Austria, 2025, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20920\">10.15479/AT-ISTA-20920</a>.","ieee":"C. Hoffmann, “Theory and applications of verifiable delay functions,” Institute of Science and Technology Austria, 2025.","apa":"Hoffmann, C. (2025). <i>Theory and applications of verifiable delay functions</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-20920\">https://doi.org/10.15479/AT-ISTA-20920</a>","ama":"Hoffmann C. Theory and applications of verifiable delay functions. 2025. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20920\">10.15479/AT-ISTA-20920</a>"},"ddc":["004"],"file_date_updated":"2026-01-02T10:39:26Z","title":"Theory and applications of verifiable delay functions","related_material":{"record":[{"relation":"part_of_dissertation","id":"13143","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"20701"},{"status":"public","relation":"part_of_dissertation","id":"12176"},{"relation":"earlier_version","id":"20556","status":"public"},{"relation":"part_of_dissertation","id":"19778","status":"public"}]},"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Verifiable Delay Functions (VDFs) introduced by Boneh et al. (CRYPTO'18) are functions that require a prescribed number of sequential steps T to evaluate, yet their output can be verified in time much faster than T. Since their introduction, VDFs have gained a lot of attention due to their applications in blockchain protocols, randomness beacons, timestamping and deniability. This thesis explores the theory and applications of VDFs, focusing on enhancing their soundness, efficiency and practicality.\r\n\r\nThe only practical VDFs known to date are based on repeated squaring in hidden order groups. Consider the function VDF(x,T)=x^(2^T).\r\nThe iterated squaring assumption states that, for a random group element x, the result of VDF cannot be computed significantly faster than performing T sequential squarings if the group order is unknown. To make the result verifiable a prover can compute a proof of exponentiation (PoE) \\pi. Given \\pi, the output of VDF can be verified in time much less than T.\r\n\r\nWe first present new constructions of statistically sound proofs of exponentiation, which are an important building block in the construction of SNARKs (Succinct Non-Interactive Argument of Knowledge). Statistical soundness means that the proofs remain secure against computationally unbounded adversaries, in particular, it remains secure even when the group order is known. We thereby address limitations in previous PoE protocols which either required (non-standard) hardness assumptions or a lot of parallel repetitions. Our construction significantly reduces the proof size of statistically sound PoEs that allow for a structured exponent, which leads to better efficiency of SNARKs and other applications.\r\n\r\nSecondly, we introduce improved batching techniques for PoEs, which allow multiple proofs to be aggregated and verified with minimal overhead. These protocols optimize communication and computation complexity in large-scale blockchain environments and enable scalable remote benchmarking of parallel computation resources.\r\n\r\nWe then construct VDFs with enhanced properties such as zero-knowledge and watermarkability. It was shown by Arun, Bonneau and Clark (ASIACRYPT'22) that these features enable new cryptographic primitives called short-lived proofs and signatures. The validity of such proofs and signatures expires after a predefined amount of time T, i.e., they are deniable after time T. Our constructions improve upon the constructions by Arun, Bonneau and Clark in several dimensions (faster forging times, arguably weaker assumptions).\r\n\r\nFinally, we apply PoEs in the realm of primality testing, providing cryptographically sound proofs of non-primality for large Proth numbers. This work gives a surprising application of VDFs in the area of computational number theory.\r\n\r\nTogether, our contributions advance both the theoretical foundations and the real-world usability of VDFs in general and in particular of PoEs, making them more adaptable and secure for current and emerging cryptographic applications."}],"day":"31","date_created":"2026-01-02T10:46:47Z","supervisor":[{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"}],"degree_awarded":"PhD","year":"2025","status":"public","has_accepted_license":"1","corr_author":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","OA_place":"publisher","publication_identifier":{"issn":["2663-337X"]},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","short":"CC BY-NC-SA (4.0)","image":"/images/cc_by_nc_sa.png","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"},"alternative_title":["ISTA Thesis"],"file":[{"file_id":"20921","date_created":"2026-01-02T10:39:16Z","file_name":"2025_Hoffmann_Charlotte_Source.zip","relation":"source_file","date_updated":"2026-01-02T10:39:16Z","checksum":"8a099fbf54963bd0be38f7ce73658682","content_type":"application/x-zip-compressed","file_size":8355494,"access_level":"closed","creator":"choffman"},{"success":1,"creator":"choffman","file_size":2258804,"access_level":"open_access","checksum":"9521c07bfb2bb5b14a49c09fcfc96474","content_type":"application/pdf","date_updated":"2026-01-02T10:39:26Z","relation":"main_file","file_name":"2025_Hoffmann_Charlotte_Thesis.pdf","date_created":"2026-01-02T10:39:26Z","file_id":"20922"}],"oa_version":"Published Version","oa":1,"department":[{"_id":"GradSch"},{"_id":"KrPi"}],"article_processing_charge":"No","date_published":"2025-12-31T00:00:00Z","month":"12","publication_status":"published","date_updated":"2026-04-16T09:11:08Z","publisher":"Institute of Science and Technology Austria"},{"oa":1,"department":[{"_id":"KrPi"}],"article_number":"3769423","article_processing_charge":"Yes (via OA deal)","PlanS_conform":"1","date_updated":"2026-06-18T18:28:26Z","publication_status":"epub_ahead","article_type":"original","date_published":"2025-09-05T00:00:00Z","month":"09","publisher":"Association for Computing Machinery","year":"2025","status":"public","has_accepted_license":"1","corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["0734-2071"],"eissn":["1557-7333"]},"OA_place":"publisher","OA_type":"hybrid","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1145/3769423"}],"title":"Kauri: BFT consensus with pipelined tree-based dissemination and aggregation","date_created":"2026-01-20T10:14:23Z","day":"05","abstract":[{"lang":"eng","text":"With the growing interest in blockchains, permissioned approaches to consensus have received increasing attention. Unfortunately, the BFT consensus algorithms that are the backbone of most of these blockchains scale poorly and offer limited throughput. In fact, many state-of-the-art BFT consensus algorithms require a single leader process to receive and validate votes from a quorum of processes and then broadcast the result, which is inherently non-scalable. Recent approaches avoid this bottleneck by using dissemination/aggregation trees to propagate values and collect and validate votes. However, the use of trees increases the round latency, which limits the throughput for deeper trees. In this paper we propose Kauri, a BFT communication abstraction that sustains high throughput as the system size grows by leveraging a novel pipelining technique to perform scalable dissemination and aggregation on trees. Furthermore, when the number of faults is moderate (arguably the most common case in practice), our construction is able to recover from faults in an optimal number of reconfiguration steps. We implemented and experimentally evaluated Kauri with up to 800 processes. Our results show that Kauri outperforms the throughput of state-of-the-art permissioned blockchain protocols, by up to 58x without compromising latency. Interestingly, in some cases, the parallelization provided by Kauri can also decrease the latency."}],"scopus_import":"1","author":[{"first_name":"Ray","full_name":"Neiheiser, Ray","id":"f09651b9-fec0-11ec-b5d8-934aff0e52a4","orcid":"0000-0001-7227-8309","last_name":"Neiheiser"},{"first_name":"Miguel","full_name":"Matos, Miguel","last_name":"Matos"},{"last_name":"Rodrigues","full_name":"Rodrigues, Luis","first_name":"Luis"}],"quality_controlled":"1","project":[{"_id":"34a1b658-11ca-11ed-8bc3-c75229f0241e","name":"Interface Theory for Security and Privacy","grant_number":"F8502"},{"_id":"7bdd2f70-9f16-11ee-852c-b7950bc6d277","name":"SeCure, privAte, and interoperabLe layEr 2","grant_number":"ICT22-045"}],"_id":"21017","doi":"10.1145/3769423","type":"journal_article","publication":"ACM Transactions on Computer Systems","ddc":["000"],"acknowledgement":"We thank the ACM TOCS Editors and the reviewers for their help in improving the manuscript. This work was partially supported by CAPES - Brazil (Coordenação de Aperfeiçoamento de Pessoal de Nível Superior) and byFundação para a Ciência e Tecnologia (FCT) under project UIDB/50021/2020 and grant 2020.05270.BD, and via project COSMOS (via the OE with ref. PTDC/EEI-COM/29271/2017, via the łPrograma Operacional Regional de Lisboa na sua componente FEDER” with ref. Lisboa-01-0145-FEDER-029271) and project Angainor with reference LISBOA-01-0145-FEDER-031456, grant agreement number 952226, and project GLOG, with reference LISBOA2030-FEDER-00771200, and project BIG (Enhancing the research and innovation potential of Tecnico through blockchain technologies and design Innovation for social Good), and project ScalableCosmosConsensus, and the Austrian Science Fund (FWF) SFB project SpyCoDe F8502 and the Vienna Science and Technology Fund (WWTF) project SCALE2 CT22-045","citation":{"apa":"Neiheiser, R., Matos, M., &#38; Rodrigues, L. (2025). Kauri: BFT consensus with pipelined tree-based dissemination and aggregation. <i>ACM Transactions on Computer Systems</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3769423\">https://doi.org/10.1145/3769423</a>","ama":"Neiheiser R, Matos M, Rodrigues L. Kauri: BFT consensus with pipelined tree-based dissemination and aggregation. <i>ACM Transactions on Computer Systems</i>. 2025. doi:<a href=\"https://doi.org/10.1145/3769423\">10.1145/3769423</a>","mla":"Neiheiser, Ray, et al. “Kauri: BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation.” <i>ACM Transactions on Computer Systems</i>, 3769423, Association for Computing Machinery, 2025, doi:<a href=\"https://doi.org/10.1145/3769423\">10.1145/3769423</a>.","ieee":"R. Neiheiser, M. Matos, and L. Rodrigues, “Kauri: BFT consensus with pipelined tree-based dissemination and aggregation,” <i>ACM Transactions on Computer Systems</i>. Association for Computing Machinery, 2025.","chicago":"Neiheiser, Ray, Miguel Matos, and Luis Rodrigues. “Kauri: BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation.” <i>ACM Transactions on Computer Systems</i>. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3769423\">https://doi.org/10.1145/3769423</a>.","short":"R. Neiheiser, M. Matos, L. Rodrigues, ACM Transactions on Computer Systems (2025).","ista":"Neiheiser R, Matos M, Rodrigues L. 2025. Kauri: BFT consensus with pipelined tree-based dissemination and aggregation. ACM Transactions on Computer Systems., 3769423."}},{"date_updated":"2026-02-18T07:36:42Z","publication_status":"published","month":"08","date_published":"2025-08-17T00:00:00Z","publisher":"Springer Nature","oa":1,"article_processing_charge":"No","conference":{"end_date":"2025-08-21","location":"Santa Barbara, CA, United States","start_date":"2025-08-17","name":"CRYPTO: International Cryptology Conference"},"department":[{"_id":"KrPi"}],"publication_identifier":{"issn":["0302-9743"],"isbn":["9783032019127"],"eissn":["1611-3349"],"eisbn":["9783032019134"]},"OA_place":"repository","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","alternative_title":["LNCS"],"OA_type":"green","year":"2025","status":"public","main_file_link":[{"url":"https://eprint.iacr.org/2025/1035","open_access":"1"}],"language":[{"iso":"eng"}],"title":"Continuous group-key agreement: Concurrent updates without pruning","volume":16007,"date_created":"2026-02-17T07:41:04Z","abstract":[{"lang":"eng","text":"Continuous Group Key Agreement (CGKA) is the primitive underlying secure group messaging. It allows a large group of N users to maintain a shared secret key that is frequently rotated by the\r\ngroup members in order to achieve forward secrecy and post compromise security. The group messaging scheme Messaging Layer Security (MLS) standardized by the IETF makes use of a CGKA called TreeKEM which arranges the N group members in a binary tree. Here, each node is associated with a public-key, each user is assigned one of the leaves, and a user knows the corresponding secret keys from their leaf to the root. To update the key material known to them, a user must just replace keys at log(N) nodes, which requires them to create and upload log(N) ciphertexts. Such updates must be processed sequentially by all users, which for large groups is impractical. To allow for concurrent updates, TreeKEM uses the “propose and commit” paradigm, where multiple users can concurrently propose to update (by just sampling a fresh leaf key), and a single user can then commit to all proposals at once. Unfortunately, this process destroys the binary tree structure as the tree gets pruned and some nodes must be “blanked” at the cost of increasing the in-degree of others, which makes the commit operation, as well as, future commits more costly. In the worst case, the update cost (in terms of uploaded ciphertexts) per user can grow from log(N) to Ω(N). In this work we provide two main contributions. First, we show that MLS’ communication complexity is bad not only in the worst case but also if the proposers and committers are chosen at random: even if there’s just one update proposal for every commit the expected cost is already over √N, and it approaches N as this ratio changes towards more proposals. Our second contribution is a new variant of propose and commit for\r\nTreeKEM which for moderate amounts of update proposals per commit provably achieves an update cost of Θ(log(N)) assuming the proposers and committers are chosen at random."}],"day":"17","publication":"45th Annual International Cryptology Conference","type":"conference","acknowledgement":"B. Auerbach and B. Erol—Conducted part of this work at ISTA.","citation":{"ista":"Auerbach B, Cueto Noval M, Erol B, Pietrzak KZ. 2025. Continuous group-key agreement: Concurrent updates without pruning. 45th Annual International Cryptology Conference. CRYPTO: International Cryptology Conference, LNCS, vol. 16007, 141–172.","short":"B. Auerbach, M. Cueto Noval, B. Erol, K.Z. Pietrzak, in:, 45th Annual International Cryptology Conference, Springer Nature, 2025, pp. 141–172.","chicago":"Auerbach, Benedikt, Miguel Cueto Noval, Boran Erol, and Krzysztof Z Pietrzak. “Continuous Group-Key Agreement: Concurrent Updates without Pruning.” In <i>45th Annual International Cryptology Conference</i>, 16007:141–72. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-01913-4_5\">https://doi.org/10.1007/978-3-032-01913-4_5</a>.","ieee":"B. Auerbach, M. Cueto Noval, B. Erol, and K. Z. Pietrzak, “Continuous group-key agreement: Concurrent updates without pruning,” in <i>45th Annual International Cryptology Conference</i>, Santa Barbara, CA, United States, 2025, vol. 16007, pp. 141–172.","mla":"Auerbach, Benedikt, et al. “Continuous Group-Key Agreement: Concurrent Updates without Pruning.” <i>45th Annual International Cryptology Conference</i>, vol. 16007, Springer Nature, 2025, pp. 141–72, doi:<a href=\"https://doi.org/10.1007/978-3-032-01913-4_5\">10.1007/978-3-032-01913-4_5</a>.","ama":"Auerbach B, Cueto Noval M, Erol B, Pietrzak KZ. Continuous group-key agreement: Concurrent updates without pruning. In: <i>45th Annual International Cryptology Conference</i>. Vol 16007. Springer Nature; 2025:141-172. doi:<a href=\"https://doi.org/10.1007/978-3-032-01913-4_5\">10.1007/978-3-032-01913-4_5</a>","apa":"Auerbach, B., Cueto Noval, M., Erol, B., &#38; Pietrzak, K. Z. (2025). Continuous group-key agreement: Concurrent updates without pruning. In <i>45th Annual International Cryptology Conference</i> (Vol. 16007, pp. 141–172). Santa Barbara, CA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-01913-4_5\">https://doi.org/10.1007/978-3-032-01913-4_5</a>"},"intvolume":"     16007","quality_controlled":"1","author":[{"orcid":"0000-0002-7553-6606","last_name":"Auerbach","first_name":"Benedikt","full_name":"Auerbach, Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"last_name":"Cueto Noval","orcid":"0000-0002-2505-4246","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","first_name":"Miguel","full_name":"Cueto Noval, Miguel"},{"full_name":"Erol, Boran","first_name":"Boran","last_name":"Erol"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"}],"page":"141-172","_id":"21262","doi":"10.1007/978-3-032-01913-4_5"},{"citation":{"ama":"Belohorec J, Dvořák P, Hoffmann C, Hubáček P, Mašková K, Pastyřík M. On extractability of the KZG family of polynomial commitment schemes. In: <i>45th Annual International Cryptology Conference</i>. Vol 16005. Springer Nature; 2025:584-616. doi:<a href=\"https://doi.org/10.1007/978-3-032-01887-8_19\">10.1007/978-3-032-01887-8_19</a>","apa":"Belohorec, J., Dvořák, P., Hoffmann, C., Hubáček, P., Mašková, K., &#38; Pastyřík, M. (2025). On extractability of the KZG family of polynomial commitment schemes. In <i>45th Annual International Cryptology Conference</i> (Vol. 16005, pp. 584–616). Santa Barbara, CA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-01887-8_19\">https://doi.org/10.1007/978-3-032-01887-8_19</a>","ieee":"J. Belohorec, P. Dvořák, C. Hoffmann, P. Hubáček, K. Mašková, and M. Pastyřík, “On extractability of the KZG family of polynomial commitment schemes,” in <i>45th Annual International Cryptology Conference</i>, Santa Barbara, CA, United States, 2025, vol. 16005, pp. 584–616.","mla":"Belohorec, Juraj, et al. “On Extractability of the KZG Family of Polynomial Commitment Schemes.” <i>45th Annual International Cryptology Conference</i>, vol. 16005, Springer Nature, 2025, pp. 584–616, doi:<a href=\"https://doi.org/10.1007/978-3-032-01887-8_19\">10.1007/978-3-032-01887-8_19</a>.","short":"J. Belohorec, P. Dvořák, C. Hoffmann, P. Hubáček, K. Mašková, M. Pastyřík, in:, 45th Annual International Cryptology Conference, Springer Nature, 2025, pp. 584–616.","chicago":"Belohorec, Juraj, Pavel Dvořák, Charlotte Hoffmann, Pavel Hubáček, Kristýna Mašková, and Martin Pastyřík. “On Extractability of the KZG Family of Polynomial Commitment Schemes.” In <i>45th Annual International Cryptology Conference</i>, 16005:584–616. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-01887-8_19\">https://doi.org/10.1007/978-3-032-01887-8_19</a>.","ista":"Belohorec J, Dvořák P, Hoffmann C, Hubáček P, Mašková K, Pastyřík M. 2025. On extractability of the KZG family of polynomial commitment schemes. 45th Annual International Cryptology Conference. CRYPTO: International Cryptology Conference, LNCS, vol. 16005, 584–616."},"acknowledgement":"Juraj Belohorec, Pavel Hubáček, and Kristýna Mašková were partially supported by the Academy of Sciences of the Czech Republic (RVO 67985840), Czech Science Foundation GAČR grant No. 25-16311S, and by Zircuit. Pavel Dvořák was supported by Czech Science Foundation GAČR grant No. 22-14872O. Juraj Belohorec and Kristýna Mašková were supported by the grant SVV–2025–260822.","intvolume":"     16005","publication":"45th Annual International Cryptology Conference","type":"conference","doi":"10.1007/978-3-032-01887-8_19","_id":"21323","quality_controlled":"1","page":"584-616","author":[{"last_name":"Belohorec","first_name":"Juraj","full_name":"Belohorec, Juraj"},{"full_name":"Dvořák, Pavel","first_name":"Pavel","last_name":"Dvořák"},{"first_name":"Charlotte","full_name":"Hoffmann, Charlotte","id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7","orcid":"0000-0003-2027-5549","last_name":"Hoffmann"},{"last_name":"Hubáček","full_name":"Hubáček, Pavel","first_name":"Pavel"},{"first_name":"Kristýna","full_name":"Mašková, Kristýna","last_name":"Mašková"},{"first_name":"Martin","full_name":"Pastyřík, Martin","last_name":"Pastyřík"}],"abstract":[{"text":"We present a unifying framework for proving the knowledge-soundness of KZG-like polynomial commitment schemes, encompassing both univariate and multivariate variants. By conceptualizing the proof technique of Lipmaa, Parisella, and Siim for the univariate KZG scheme (EUROCRYPT 2024), we present tools and falsifiable hardness assumptions that permit black-box extraction of the multivariate KZG scheme. Central to our approach is the notion of a canonical Proof-of-Knowledge of a Polynomial (PoKoP) of a polynomial commitment scheme, which we use to capture the extractability notion required in constructions of practical zk-SNARKs. We further present an explicit polynomial decomposition lemma for multivariate polynomials, enabling a more direct analysis of interpolating extractors and bridging the gap between univariate and multivariate commitments. Our results provide the first standard-model proofs of extractability for the multivariate KZG scheme and many of its variants under falsifiable assumptions.","lang":"eng"}],"day":"17","date_created":"2026-02-18T10:59:58Z","title":"On extractability of the KZG family of polynomial commitment schemes","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/514"}],"language":[{"iso":"eng"}],"volume":16005,"alternative_title":["LNCS"],"oa_version":"Preprint","OA_type":"green","OA_place":"repository","publication_identifier":{"isbn":["9783032018861"],"issn":["0302-9743"],"eisbn":["9783032018878"],"eissn":["1611-3349"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","status":"public","publisher":"Springer Nature","month":"08","date_published":"2025-08-17T00:00:00Z","publication_status":"published","date_updated":"2026-02-19T07:50:33Z","article_processing_charge":"No","conference":{"end_date":"2025-08-221","location":"Santa Barbara, CA, United States","start_date":"2025-08-17","name":"CRYPTO: International Cryptology Conference"},"department":[{"_id":"KrPi"}],"oa":1},{"day":"01","abstract":[{"lang":"eng","text":"In this work, we explore route discovery in private payment channel networks. We first determine what “ideal\" privacy for a routing protocol means in this setting. We observe that protocols achieving this strong privacy definition exist by leveraging Multi-Party Computation but they are inherently inefficient as they must involve the entire network. We then present protocols with weaker privacy guarantees but much better efficiency (involving only a small fraction of the nodes). The core idea is that both sender and receiver gossip a message which propagates through the network, and the moment any node in the network receives both messages, a path is found. In our first protocol the message is always sent to all neighbouring nodes with a delay proportional to the fees of that edge. In our second protocol the message is only sent to one neighbour chosen randomly with a probability proportional to its degree. We additionally propose a more realistic notion of privacy in order to measure the privacy leakage of our protocols in practice. Our realistic notion of privacy challenges an adversary that join the network with a fixed budget to create channels to guess the sender and receiver of a transaction upon receiving messages from our protocols. Simulations of our protocols on the Lightning network topology (for random transactions and uniform fees) show that 1) forming edges with high degree nodes is a more effective attack strategy for the adversary, 2) there is a tradeoff between the number of nodes involved in our protocols (privacy) and the optimality of the discovered path, and 3) our protocols involve a very small fraction of the network on average."}],"date_created":"2025-04-20T22:01:28Z","volume":15263,"title":"Route discovery in private payment channel networks","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1539"}],"language":[{"iso":"eng"}],"scopus_import":"1","project":[{"grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"doi":"10.1007/978-3-031-82349-7_15","_id":"19600","author":[{"first_name":"Zeta","full_name":"Avarikioti, Zeta","last_name":"Avarikioti"},{"full_name":"Bastankhah, Mahsa","first_name":"Mahsa","last_name":"Bastankhah"},{"first_name":"Mohammad Ali","full_name":"Maddah-Ali, Mohammad Ali","last_name":"Maddah-Ali"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"},{"last_name":"Svoboda","orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","first_name":"Jakub"},{"orcid":"0009-0001-3676-4809","last_name":"Yeo","first_name":"Michelle X","full_name":"Yeo, Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"page":"207-223","quality_controlled":"1","intvolume":"     15263","acknowledgement":"This work was supported in part by the ERC CoG 863818 (ForM-SMArt), Austrian Science Fund (FWF) 10.55776/COE12, and MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms) grants.","citation":{"ama":"Avarikioti Z, Bastankhah M, Maddah-Ali MA, Pietrzak KZ, Svoboda J, Yeo MX. Route discovery in private payment channel networks. In: <i>Computer Security. ESORICS 2024 International Workshops</i>. Vol 15263. Springer Nature; 2025:207-223. doi:<a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">10.1007/978-3-031-82349-7_15</a>","apa":"Avarikioti, Z., Bastankhah, M., Maddah-Ali, M. A., Pietrzak, K. Z., Svoboda, J., &#38; Yeo, M. X. (2025). Route discovery in private payment channel networks. In <i>Computer Security. ESORICS 2024 International Workshops</i> (Vol. 15263, pp. 207–223). Bydgoszcz, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">https://doi.org/10.1007/978-3-031-82349-7_15</a>","mla":"Avarikioti, Zeta, et al. “Route Discovery in Private Payment Channel Networks.” <i>Computer Security. ESORICS 2024 International Workshops</i>, vol. 15263, Springer Nature, 2025, pp. 207–23, doi:<a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">10.1007/978-3-031-82349-7_15</a>.","ieee":"Z. Avarikioti, M. Bastankhah, M. A. Maddah-Ali, K. Z. Pietrzak, J. Svoboda, and M. X. Yeo, “Route discovery in private payment channel networks,” in <i>Computer Security. ESORICS 2024 International Workshops</i>, Bydgoszcz, Poland, 2025, vol. 15263, pp. 207–223.","short":"Z. Avarikioti, M. Bastankhah, M.A. Maddah-Ali, K.Z. Pietrzak, J. Svoboda, M.X. Yeo, in:, Computer Security. ESORICS 2024 International Workshops, Springer Nature, 2025, pp. 207–223.","chicago":"Avarikioti, Zeta, Mahsa Bastankhah, Mohammad Ali Maddah-Ali, Krzysztof Z Pietrzak, Jakub Svoboda, and Michelle X Yeo. “Route Discovery in Private Payment Channel Networks.” In <i>Computer Security. ESORICS 2024 International Workshops</i>, 15263:207–23. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">https://doi.org/10.1007/978-3-031-82349-7_15</a>.","ista":"Avarikioti Z, Bastankhah M, Maddah-Ali MA, Pietrzak KZ, Svoboda J, Yeo MX. 2025. Route discovery in private payment channel networks. Computer Security. ESORICS 2024 International Workshops. ESORICS: European Symposium on Research in Computer Security, LNCS, vol. 15263, 207–223."},"type":"conference","publication":"Computer Security. ESORICS 2024 International Workshops","conference":{"location":"Bydgoszcz, Poland","end_date":"2024-09-20","name":"ESORICS: European Symposium on Research in Computer Security","start_date":"2024-09-16"},"department":[{"_id":"KrPi"},{"_id":"KrCh"}],"article_processing_charge":"No","oa":1,"ec_funded":1,"publisher":"Springer Nature","date_published":"2025-04-01T00:00:00Z","month":"04","date_updated":"2025-11-05T07:52:35Z","publication_status":"published","year":"2025","status":"public","OA_type":"green","alternative_title":["LNCS"],"oa_version":"Submitted Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"repository","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031823480"],"eissn":["1611-3349"]}},{"scopus_import":"1","volume":15606,"main_file_link":[{"url":"https://www.research-collection.ethz.ch/handle/20.500.11850/732894","open_access":"1"}],"language":[{"iso":"eng"}],"title":"On the soundness of algebraic attacks against code-based assumptions","date_created":"2025-05-19T14:15:01Z","day":"28","abstract":[{"lang":"eng","text":"We study recent algebraic attacks (Briaud-Øygarden EC’23) on the Regular Syndrome Decoding (RSD) problem and the assumptions underlying the correctness of their attacks’ complexity estimates. By relating these assumptions to interesting algebraic-combinatorial problems, we prove that they do not hold in full generality. However, we show that they are (asymptotically) true for most parameter sets, supporting the soundness of algebraic attacks on RSD. Further, we prove—without any heuristics or assumptions—that RSD can be broken in polynomial time whenever the number of error blocks times the square of the size of error blocks is larger than 2 times the square of the dimension of the code.\r\nAdditionally, we use our methodology to attack a variant of the Learning With Errors problem where each error term lies in a fixed set of constant size. We prove that this problem can be broken in polynomial time, given a sufficient number of samples. This result improves on the seminal work by Arora and Ge (ICALP’11), as the attack’s time complexity is independent of the LWE modulus."}],"publication":"44th Annual International Conference on the Theory and Applications of Cryptographic Techniques","type":"conference","intvolume":"     15606","acknowledgement":"We thank Pierre Briaud and Morten Øygarden for helpful discussions on algebraic attacks on RSD, and the EC reviewers for helpful comments.","citation":{"ista":"Cueto Noval M, Merz S-P, Stählin P, Ünal A. 2025. On the soundness of algebraic attacks against code-based assumptions. 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol. 15606, 385–415.","chicago":"Cueto Noval, Miguel, Simon-Philipp Merz, Patrick Stählin, and Akin Ünal. “On the Soundness of Algebraic Attacks against Code-Based Assumptions.” In <i>44th Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, 15606:385–415. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-91095-1_14\">https://doi.org/10.1007/978-3-031-91095-1_14</a>.","short":"M. Cueto Noval, S.-P. Merz, P. Stählin, A. Ünal, in:, 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer Nature, 2025, pp. 385–415.","ieee":"M. Cueto Noval, S.-P. Merz, P. Stählin, and A. Ünal, “On the soundness of algebraic attacks against code-based assumptions,” in <i>44th Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, Madrid, Spain, 2025, vol. 15606, pp. 385–415.","mla":"Cueto Noval, Miguel, et al. “On the Soundness of Algebraic Attacks against Code-Based Assumptions.” <i>44th Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, vol. 15606, Springer Nature, 2025, pp. 385–415, doi:<a href=\"https://doi.org/10.1007/978-3-031-91095-1_14\">10.1007/978-3-031-91095-1_14</a>.","apa":"Cueto Noval, M., Merz, S.-P., Stählin, P., &#38; Ünal, A. (2025). On the soundness of algebraic attacks against code-based assumptions. In <i>44th Annual International Conference on the Theory and Applications of Cryptographic Techniques</i> (Vol. 15606, pp. 385–415). Madrid, Spain: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-91095-1_14\">https://doi.org/10.1007/978-3-031-91095-1_14</a>","ama":"Cueto Noval M, Merz S-P, Stählin P, Ünal A. On the soundness of algebraic attacks against code-based assumptions. In: <i>44th Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>. Vol 15606. Springer Nature; 2025:385-415. doi:<a href=\"https://doi.org/10.1007/978-3-031-91095-1_14\">10.1007/978-3-031-91095-1_14</a>"},"page":"385-415","author":[{"last_name":"Cueto Noval","orcid":"0000-0002-2505-4246","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","full_name":"Cueto Noval, Miguel","first_name":"Miguel"},{"last_name":"Merz","full_name":"Merz, Simon-Philipp","first_name":"Simon-Philipp"},{"last_name":"Stählin","full_name":"Stählin, Patrick","first_name":"Patrick"},{"orcid":"0000-0002-8929-0221","last_name":"Ünal","first_name":"Akin","full_name":"Ünal, Akin","id":"f6b56fb6-dc63-11ee-9dbf-f6780863a85a"}],"quality_controlled":"1","_id":"19712","doi":"10.1007/978-3-031-91095-1_14","publication_status":"published","date_updated":"2025-05-28T06:12:39Z","date_published":"2025-04-28T00:00:00Z","month":"04","publisher":"Springer Nature","oa":1,"conference":{"start_date":"2025-05-04","name":"EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques","end_date":"2025-05-08","location":"Madrid, Spain"},"department":[{"_id":"KrPi"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031910944"],"eissn":["1611-3349"],"eisbn":["9783031910951"]},"OA_place":"repository","OA_type":"green","oa_version":"Submitted Version","alternative_title":["LNCS"],"year":"2025","status":"public","corr_author":"1"},{"title":"Securely instantiating ‘Half Gates’ garbling in the standard model","main_file_link":[{"url":"https://eprint.iacr.org/2025/281","open_access":"1"}],"language":[{"iso":"eng"}],"volume":15677,"day":"05","abstract":[{"lang":"eng","text":"Garbling is a fundamental cryptographic primitive, with numerous theoretical and practical applications. Since the first construction by Yao (FOCS’82, ’86), a line of work has concerned itself with reducing the communication and computational complexity of that construction. One of the most efficient garbling schemes presently is the ‘Half Gates’ scheme by Zahur, Rosulek, and Evans (Eurocrypt’15). Despite its widespread adoption, the provable security of this scheme has been based on assumptions whose only instantiations are in idealized models. For example, in their original paper, Zahur, Rosulek, and Evans showed that hash functions satisfying a notion called circular correlation robustness (CCR) suffice for this task, and then proved that CCR secure hash functions can be instantiated in the random permutation model.\r\nIn this work, we show how to securely instantiate the Half Gates scheme in the standard model. To this end, we first show how this scheme can be securely instantiated given a (family of) weak CCR hash function, a notion that we introduce. Furthermore, we show how a weak CCR hash function can be used to securely instantiate other efficient garbling schemes, namely the ones by Rosulek and Roy (Crypto’21) and Heath (Eurocrypt’24). Thus we believe this notion to be of independent interest.\r\nFinally, we construct such weak CCR hash functions using indistinguishability obfuscation and one-way functions. The security proof of this construction constitutes our main technical contribution. While our construction is not practical, it serves as a proof of concept supporting the soundness of these garbling schemes, which we regard to be particularly important given the recent initiative by NIST to standardize garbling, and the optimizations in Half Gates being potentially adopted."}],"date_created":"2025-05-25T22:17:02Z","scopus_import":"1","quality_controlled":"1","page":"37-75","author":[{"first_name":"Anasuya","full_name":"Acharya, Anasuya","last_name":"Acharya"},{"last_name":"Azari","full_name":"Azari, Karen","first_name":"Karen"},{"last_name":"Baig","full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"last_name":"Hofheinz","full_name":"Hofheinz, Dennis","first_name":"Dennis"},{"last_name":"Kamath","first_name":"Chethan","full_name":"Kamath, Chethan"}],"doi":"10.1007/978-3-031-91829-2_2","_id":"19738","type":"conference","publication":"28th IACR International Conference on Practice and Theory of Public-Key Cryptography","citation":{"ama":"Acharya A, Azari K, Baig MA, Hofheinz D, Kamath C. Securely instantiating ‘Half Gates’ garbling in the standard model. In: <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>. Vol 15677. Springer Nature; 2025:37-75. doi:<a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">10.1007/978-3-031-91829-2_2</a>","apa":"Acharya, A., Azari, K., Baig, M. A., Hofheinz, D., &#38; Kamath, C. (2025). Securely instantiating ‘Half Gates’ garbling in the standard model. In <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i> (Vol. 15677, pp. 37–75). Roros, Norway: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">https://doi.org/10.1007/978-3-031-91829-2_2</a>","ieee":"A. Acharya, K. Azari, M. A. Baig, D. Hofheinz, and C. Kamath, “Securely instantiating ‘Half Gates’ garbling in the standard model,” in <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, Roros, Norway, 2025, vol. 15677, pp. 37–75.","mla":"Acharya, Anasuya, et al. “Securely Instantiating ‘Half Gates’ Garbling in the Standard Model.” <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, vol. 15677, Springer Nature, 2025, pp. 37–75, doi:<a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">10.1007/978-3-031-91829-2_2</a>.","short":"A. Acharya, K. Azari, M.A. Baig, D. Hofheinz, C. Kamath, in:, 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Springer Nature, 2025, pp. 37–75.","chicago":"Acharya, Anasuya, Karen Azari, Mirza Ahad Baig, Dennis Hofheinz, and Chethan Kamath. “Securely Instantiating ‘Half Gates’ Garbling in the Standard Model.” In <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, 15677:37–75. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">https://doi.org/10.1007/978-3-031-91829-2_2</a>.","ista":"Acharya A, Azari K, Baig MA, Hofheinz D, Kamath C. 2025. Securely instantiating ‘Half Gates’ garbling in the standard model. 28th IACR International Conference on Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography, LNCS, vol. 15677, 37–75."},"intvolume":"     15677","oa":1,"article_processing_charge":"No","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"conference":{"end_date":"2025-05-15","location":"Roros, Norway","start_date":"2025-05-12","name":"PKC: Public-Key Cryptography"},"month":"05","date_published":"2025-05-05T00:00:00Z","date_updated":"2025-06-02T07:01:45Z","publisher":"Springer Nature","year":"2025","status":"public","OA_place":"repository","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031918285"],"issn":["0302-9743"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"oa_version":"Preprint","OA_type":"green"},{"volume":15674,"title":"Watermarkable and zero-knowledge Verifiable Delay Functions from any proof of exponentiation","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://ia.cr/2024/481"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"20920","status":"public"},{"status":"public","id":"20556","relation":"dissertation_contains"}]},"day":"01","abstract":[{"lang":"eng","text":"A verifiable delay function VDF(x, T)->(y, π) maps an input x and time parameter T to an output y together with an efficiently verifiable proof π certifying that y was correctly computed. The function runs in T sequential steps, and it should not be possible to compute y much faster than that. The only known practical VDFs use sequential squaring in groups of unknown order as the sequential function, i.e., y = x^2^T. There are two constructions for the proof of exponentiation (PoE) certifying that y = x^2^T, with Wesolowski (Eurocrypt’19) having very short proofs, but they are more expensive to compute and the soundness relies on stronger assumptions than the PoE proposed by Pietrzak (ITCS’19).\r\nA recent application of VDFs by Arun, Bonneau and Clark (Asiacrypt’22) are short-lived proofs and signatures, which are proofs and signatures that are only sound for some time t, but after that can be forged by anyone. For this they rely on “watermarkable VDFs”, where the proof embeds a prover chosen watermark. To achieve stronger notions of proofs/signatures with reusable forgeability, they rely on “zero-knowledge VDFs”, where instead of the output y, one just proves knowledge of this output. The existing proposals for watermarkable and zero-knowledge VDFs all build on Wesolowski’s PoE, for the watermarkable VDFs there’s currently no security proof.\r\n\r\nIn this work we give the first constructions that transform any PoEs in hidden order groups into watermarkable VDFs and into zkVDFs, solving an open question by Arun et al. Unlike our watermarkable VDF, the zkVDF (required for reusable forgeability) is not very practical as the number of group elements in the proof is a security parameter. To address this, we introduce the notion of zero-knowledge proofs of sequential work (zkPoSW), a notion that relaxes zkVDFs by not requiring that the output is unique. We show that zkPoSW are sufficient to construct proofs or signatures with reusable forgeability, and construct efficient zkPoSW from any PoE, ultimately achieving short lived proofs and signatures that improve upon Arun et al.’s construction in several dimensions (faster forging times, arguably weaker assumptions).\r\nA key idea underlying our constructions is to not directly construct a (watermarked or zk) proof for y = x^2^T, but instead give a (watermarked or zk) proof for the more basic statement that \r\nx^l, y^l satisfy x^l = x ^r, y^l = y^r for some r, together with a normal PoE for y^l = (x^l)^2^T."}],"date_created":"2025-06-03T07:30:21Z","scopus_import":"1","author":[{"full_name":"Hoffmann, Charlotte","first_name":"Charlotte","id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7","orcid":"0000-0003-2027-5549","last_name":"Hoffmann"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"page":"36-66","quality_controlled":"1","doi":"10.1007/978-3-031-91820-9_2","_id":"19778","publication":"28th IACR International Conference on Practice and Theory of Public-Key Cryptography","type":"conference","intvolume":"     15674","citation":{"apa":"Hoffmann, C., &#38; Pietrzak, K. Z. (2025). Watermarkable and zero-knowledge Verifiable Delay Functions from any proof of exponentiation. In <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i> (Vol. 15674, pp. 36–66). Roros, Norway: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-91820-9_2\">https://doi.org/10.1007/978-3-031-91820-9_2</a>","ama":"Hoffmann C, Pietrzak KZ. Watermarkable and zero-knowledge Verifiable Delay Functions from any proof of exponentiation. In: <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>. Vol 15674. Springer Nature; 2025:36-66. doi:<a href=\"https://doi.org/10.1007/978-3-031-91820-9_2\">10.1007/978-3-031-91820-9_2</a>","ieee":"C. Hoffmann and K. Z. Pietrzak, “Watermarkable and zero-knowledge Verifiable Delay Functions from any proof of exponentiation,” in <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, Roros, Norway, 2025, vol. 15674, pp. 36–66.","mla":"Hoffmann, Charlotte, and Krzysztof Z. Pietrzak. “Watermarkable and Zero-Knowledge Verifiable Delay Functions from Any Proof of Exponentiation.” <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, vol. 15674, Springer Nature, 2025, pp. 36–66, doi:<a href=\"https://doi.org/10.1007/978-3-031-91820-9_2\">10.1007/978-3-031-91820-9_2</a>.","chicago":"Hoffmann, Charlotte, and Krzysztof Z Pietrzak. “Watermarkable and Zero-Knowledge Verifiable Delay Functions from Any Proof of Exponentiation.” In <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, 15674:36–66. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-91820-9_2\">https://doi.org/10.1007/978-3-031-91820-9_2</a>.","short":"C. Hoffmann, K.Z. Pietrzak, in:, 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Springer Nature, 2025, pp. 36–66.","ista":"Hoffmann C, Pietrzak KZ. 2025. Watermarkable and zero-knowledge Verifiable Delay Functions from any proof of exponentiation. 28th IACR International Conference on Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography, LNCS, vol. 15674, 36–66."},"oa":1,"department":[{"_id":"KrPi"},{"_id":"GradSch"}],"conference":{"start_date":"2025-05-12","name":"PKC: Public-Key Cryptography","end_date":"2025-05-15","location":"Roros, Norway"},"article_processing_charge":"No","month":"01","date_published":"2025-01-01T00:00:00Z","publication_status":"published","date_updated":"2026-04-16T09:11:09Z","publisher":"Springer Nature","year":"2025","status":"public","corr_author":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","OA_place":"repository","publication_identifier":{"eissn":["1611-3349"],"eisbn":["9783031918209"],"issn":["0302-9743"],"isbn":["9783031918193"]},"OA_type":"green","alternative_title":["LNCS"],"oa_version":"Preprint"},{"publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","type":"conference","external_id":{"isi":["001525534800030"]},"ddc":["000"],"citation":{"apa":"Chatterjee, K., Gilbert, S., Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2025). When is liquid democracy possible?: On the manipulation of variance. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i> (pp. 241–251). Huatulco, Mexico: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3732772.3733544\">https://doi.org/10.1145/3732772.3733544</a>","ama":"Chatterjee K, Gilbert S, Schmid S, Svoboda J, Yeo MX. When is liquid democracy possible?: On the manipulation of variance. In: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2025:241-251. doi:<a href=\"https://doi.org/10.1145/3732772.3733544\">10.1145/3732772.3733544</a>","mla":"Chatterjee, Krishnendu, et al. “When Is Liquid Democracy Possible?: On the Manipulation of Variance.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2025, pp. 241–51, doi:<a href=\"https://doi.org/10.1145/3732772.3733544\">10.1145/3732772.3733544</a>.","ieee":"K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, and M. X. Yeo, “When is liquid democracy possible?: On the manipulation of variance,” in <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Huatulco, Mexico, 2025, pp. 241–251.","chicago":"Chatterjee, Krishnendu, Seth Gilbert, Stefan Schmid, Jakub Svoboda, and Michelle X Yeo. “When Is Liquid Democracy Possible?: On the Manipulation of Variance.” In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, 241–51. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3732772.3733544\">https://doi.org/10.1145/3732772.3733544</a>.","short":"K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, M.X. Yeo, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025, pp. 241–251.","ista":"Chatterjee K, Gilbert S, Schmid S, Svoboda J, Yeo MX. 2025. When is liquid democracy possible?: On the manipulation of variance. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 241–251."},"acknowledgement":"This work was partially supported by MOE-T2EP20122-0014 (DataDriven Distributed Algorithms), German Research Foundation (DFG) project ReNO (SPP 2378) from 2023-2027, ERC CoG 863818 (ForMSMArt) and Austrian Science Fund (FWF) 10.55776/COE12.","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Gilbert, Seth","first_name":"Seth","last_name":"Gilbert"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"},{"orcid":"0000-0002-1419-3267","last_name":"Svoboda","first_name":"Jakub","full_name":"Svoboda, Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"},{"orcid":"0009-0001-3676-4809","last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"page":"241-251","quality_controlled":"1","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"_id":"20053","doi":"10.1145/3732772.3733544","isi":1,"file_date_updated":"2025-08-05T07:15:31Z","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://eprint.iacr.org/2025/745","open_access":"1"}],"title":"When is liquid democracy possible?: On the manipulation of variance","date_created":"2025-07-21T08:18:26Z","day":"13","abstract":[{"text":"Liquid democracy is a transitive vote delegation mechanism over voting graphs. It enables each voter to delegate their vote(s) to another better-informed voter, with the goal of collectively making a better decision. The question of whether liquid democracy outperforms direct voting has been previously studied in the context of local delegation mechanisms (where voters can only delegate to someone in their neighbourhood) and binary decision problems. It has previously been shown that it is impossible for local delegation mechanisms to outperform direct voting in general graphs. This raises the question: for which classes of graphs do local delegation mechanisms yield good results?\r\nIn this work, we analyse (1) properties of specific graphs and (2) properties of local delegation mechanisms on these graphs, determining where local delegation actually outperforms direct voting. We show that a critical graph property enabling liquid democracy is that the voting outcome of local delegation mechanisms preserves a sufficient amount of variance, thereby avoiding situations where delegation falls behind direct voting1. These insights allow us to prove our main results, namely that there exist local delegation mechanisms that perform no worse and in fact quantitatively better than direct voting in natural graph topologies like complete, random d-regular, and bounded degree graphs, lending a more nuanced perspective to previous impossibility results.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["9798400718854"]},"OA_place":"publisher","OA_type":"hybrid","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","file":[{"relation":"main_file","date_created":"2025-08-05T07:15:31Z","file_name":"2025_PODC_Chatterjee.pdf","file_id":"20122","success":1,"checksum":"cd628fe54d96e9fc6cc789bb8145422b","content_type":"application/pdf","file_size":783297,"access_level":"open_access","creator":"dernst","date_updated":"2025-08-05T07:15:31Z"}],"year":"2025","status":"public","corr_author":"1","has_accepted_license":"1","date_updated":"2026-02-16T11:46:51Z","publication_status":"published","month":"06","date_published":"2025-06-13T00:00:00Z","ec_funded":1,"publisher":"Association for Computing Machinery","oa":1,"department":[{"_id":"KrCh"},{"_id":"KrPi"}],"conference":{"location":"Huatulco, Mexico","end_date":"2025-06-20","name":"PODC: Symposium on Principles of Distributed Computing","start_date":"2025-06-16"},"article_processing_charge":"No"},{"related_material":{"record":[{"id":"13143","relation":"part_of_dissertation","status":"public"},{"status":"public","id":"12176","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"20701","status":"public"},{"id":"20920","relation":"later_version","status":"public"},{"id":"19778","relation":"part_of_dissertation","status":"public"}]},"language":[{"iso":"eng"}],"title":"Theory and applications of verifiable delay functions","file_date_updated":"2026-01-08T14:11:39Z","date_created":"2025-10-27T14:16:56Z","day":"31","abstract":[{"lang":"eng","text":"Verifiable Delay Functions (VDFs) introduced by Boneh et al. (CRYPTO'18) are functions that require a prescribed number of sequential steps T to evaluate, yet their output can be verified in time much faster than T. Since their introduction, VDFs have gained a lot of attention due to their applications in blockchain protocols, randomness beacons, timestamping and deniability. This thesis explores the theory and applications of VDFs, focusing on enhancing their soundness, efficiency and practicality.\r\n\r\nThe only practical VDFs known to date are based on repeated squaring in hidden order groups. Consider the function VDF(x,T)=x^(2^T).\r\nThe iterated squaring assumption states that, for a random group element x, the result of VDF cannot be computed significantly faster than performing T sequential squarings if the group order is unknown. To make the result verifiable a prover can compute a proof of exponentiation (PoE) \\pi. Given \\pi, the output of VDF can be verified in time much less than T.\r\n\r\nWe first present new constructions of statistically sound proofs of exponentiation, which are an important building block in the construction of SNARKs (Succinct Non-Interactive Argument of Knowledge). Statistical soundness means that the proofs remain secure against computationally unbounded adversaries, in particular, it remains secure even when the group order is known. We thereby address limitations in previous PoE protocols which either required (non-standard) hardness assumptions or a lot of parallel repetitions. Our construction significantly reduces the proof size of statistically sound PoEs that allow for a structured exponent, which leads to better efficiency of SNARKs and other applications.\r\n\r\nSecondly, we introduce improved batching techniques for PoEs, which allow multiple proofs to be aggregated and verified with minimal overhead. These protocols optimize communication and computation complexity in large-scale blockchain environments and enable scalable remote benchmarking of parallel computation resources.\r\n\r\nWe then construct VDFs with enhanced properties such as zero-knowledge and watermarkability. It was shown by Arun, Bonneau and Clark (ASIACRYPT'22) that these features enable new cryptographic primitives called short-lived proofs and signatures. The validity of such proofs and signatures expires after a predefined amount of time T, i.e., they are deniable after time T. Our constructions improve upon the constructions by Arun, Bonneau and Clark in several dimensions (faster forging times, arguably weaker assumptions).\r\n\r\nFinally, we apply PoEs in the realm of primality testing, providing cryptographically sound proofs of non-primality for large Proth numbers. This work gives a surprising application of VDFs in the area of computational number theory.\r\n\r\nTogether, our contributions advance both the theoretical foundations and the real-world usability of VDFs in general and in particular of PoEs, making them more adaptable and secure for current and emerging cryptographic applications."}],"supervisor":[{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"}],"page":"116","author":[{"orcid":"0000-0003-2027-5549","last_name":"Hoffmann","full_name":"Hoffmann, Charlotte","first_name":"Charlotte","id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7"}],"_id":"20556","doi":"10.15479/AT-ISTA-20556","type":"dissertation","ddc":["004"],"citation":{"ama":"Hoffmann C. Theory and applications of verifiable delay functions. 2025. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20556\">10.15479/AT-ISTA-20556</a>","apa":"Hoffmann, C. (2025). <i>Theory and applications of verifiable delay functions</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-20556\">https://doi.org/10.15479/AT-ISTA-20556</a>","mla":"Hoffmann, Charlotte. <i>Theory and Applications of Verifiable Delay Functions</i>. Institute of Science and Technology Austria, 2025, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20556\">10.15479/AT-ISTA-20556</a>.","ieee":"C. Hoffmann, “Theory and applications of verifiable delay functions,” Institute of Science and Technology Austria, 2025.","short":"C. Hoffmann, Theory and Applications of Verifiable Delay Functions, Institute of Science and Technology Austria, 2025.","chicago":"Hoffmann, Charlotte. “Theory and Applications of Verifiable Delay Functions.” Institute of Science and Technology Austria, 2025. <a href=\"https://doi.org/10.15479/AT-ISTA-20556\">https://doi.org/10.15479/AT-ISTA-20556</a>.","ista":"Hoffmann C. 2025. Theory and applications of verifiable delay functions. Institute of Science and Technology Austria."},"article_processing_charge":"No","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"publication_status":"published","date_updated":"2026-04-16T09:11:09Z","month":"10","date_published":"2025-10-31T00:00:00Z","publisher":"Institute of Science and Technology Austria","status":"public","year":"2025","degree_awarded":"PhD","corr_author":"1","has_accepted_license":"1","publication_identifier":{"issn":["2663-337X"]},"OA_place":"publisher","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","oa_version":"Published Version","file":[{"file_id":"20573","date_created":"2025-10-28T14:33:03Z","file_name":"2025_Hoffmann_Charlotte_Thesis.pdf","relation":"main_file","date_updated":"2026-01-08T14:11:39Z","file_size":2259304,"access_level":"closed","checksum":"1fffa4e2c33dd0b9f883d615504a2858","content_type":"application/pdf","creator":"choffman"},{"date_updated":"2025-11-11T09:34:54Z","access_level":"closed","content_type":"application/x-zip-compressed","checksum":"076ea98a1f0a86c3bbc990b6b9460dc2","file_size":9987633,"creator":"choffman","file_id":"20574","relation":"source_file","date_created":"2025-10-28T14:35:06Z","file_name":"2025_Hoffmann_Charlotte_Source.zip"}],"alternative_title":["ISTA Thesis"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","short":"CC BY-NC-SA (4.0)","image":"/images/cc_by_nc_sa.png","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"}},{"corr_author":"1","has_accepted_license":"1","year":"2025","status":"public","OA_type":"gold","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","file":[{"relation":"main_file","date_created":"2025-11-04T08:19:02Z","file_name":"2025_LIPIcsAFT_Baig.pdf","file_id":"20598","success":1,"file_size":1061847,"content_type":"application/pdf","access_level":"open_access","checksum":"b638adcd4fbffa77116c35393e165eb7","creator":"dernst","date_updated":"2025-11-04T08:19:02Z"}],"alternative_title":["LIPIcs"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774000"]},"OA_place":"publisher","article_number":"16","department":[{"_id":"KrPi"}],"conference":{"name":"AFT: Conference on Advances in Financial Technologies","start_date":"2025-10-08","location":"Pittsburgh, PA, United States","end_date":"2025-10-10"},"article_processing_charge":"Yes","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","date_updated":"2026-04-15T08:45:18Z","date_published":"2025-10-06T00:00:00Z","month":"10","project":[{"grant_number":"F8512","name":"Security and Privacy by Design for Complex Systems","_id":"34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f"},{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","name":"Security and Privacy by Design for Complex Systems","grant_number":"F8509"}],"_id":"20587","doi":"10.4230/LIPIcs.AFT.2025.16","author":[{"last_name":"Baig","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad","full_name":"Baig, Mirza Ahad"},{"last_name":"Günther","first_name":"Christoph Ullrich","full_name":"Günther, Christoph Ullrich","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"}],"quality_controlled":"1","intvolume":"       354","arxiv":1,"external_id":{"arxiv":["2508.01448"]},"ddc":["000"],"citation":{"ieee":"M. A. Baig, C. U. Günther, and K. Z. Pietrzak, “Nakamoto consensus from multiple resources,” in <i>7th Conference on Advances in Financial Technologies</i>, Pittsburgh, PA, United States, 2025, vol. 354.","mla":"Baig, Mirza Ahad, et al. “Nakamoto Consensus from Multiple Resources.” <i>7th Conference on Advances in Financial Technologies</i>, vol. 354, 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">10.4230/LIPIcs.AFT.2025.16</a>.","apa":"Baig, M. A., Günther, C. U., &#38; Pietrzak, K. Z. (2025). Nakamoto consensus from multiple resources. In <i>7th Conference on Advances in Financial Technologies</i> (Vol. 354). Pittsburgh, PA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">https://doi.org/10.4230/LIPIcs.AFT.2025.16</a>","ama":"Baig MA, Günther CU, Pietrzak KZ. Nakamoto consensus from multiple resources. In: <i>7th Conference on Advances in Financial Technologies</i>. Vol 354. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">10.4230/LIPIcs.AFT.2025.16</a>","ista":"Baig MA, Günther CU, Pietrzak KZ. 2025. Nakamoto consensus from multiple resources. 7th Conference on Advances in Financial Technologies. AFT: Conference on Advances in Financial Technologies, LIPIcs, vol. 354, 16.","chicago":"Baig, Mirza Ahad, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Nakamoto Consensus from Multiple Resources.” In <i>7th Conference on Advances in Financial Technologies</i>, Vol. 354. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">https://doi.org/10.4230/LIPIcs.AFT.2025.16</a>.","short":"M.A. Baig, C.U. Günther, K.Z. Pietrzak, in:, 7th Conference on Advances in Financial Technologies, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025."},"acknowledgement":"This research was funded in whole or in part by the Austrian Science Fund (FWF)\r\n10.55776/F85. For open access purposes, the author has applied a CC BY public copyright license\r\nto any author-accepted manuscript version arising from this submission.","type":"conference","publication":"7th Conference on Advances in Financial Technologies","date_created":"2025-11-02T23:01:34Z","day":"06","abstract":[{"text":"The blocks in the Bitcoin blockchain \"record\" the amount of work W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via a proof of space) and sequential computational steps V (through a VDF).\r\nIn this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks.\r\nWe completely classify such functions in an idealized \"continuous\" model: Γ(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the \"timed\" resources V and W, i.e., αΓ(S,V,W) = Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W) = W and the Chia rule Γ(S,V,W) = S ⋅ V. In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S (basically, the weight should not grow too much if S is slightly increased, say linear as in Chia).\r\nOur classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W₁ and a memory-hard PoW W₂. Previous work suggested to use W₁+W₂ as weight. Our results show that using e.g., √{W₁}⋅ √{W₂} or min{W₁,W₂} are also secure, and we argue that in practice these are much better choices.","lang":"eng"}],"volume":354,"file_date_updated":"2025-11-04T08:19:02Z","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://eprint.iacr.org/2025/1410","open_access":"1"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"21651","status":"public"}]},"title":"Nakamoto consensus from multiple resources","scopus_import":"1"},{"month":"03","article_type":"original","date_published":"2024-03-21T00:00:00Z","date_updated":"2025-12-02T14:02:37Z","publication_status":"published","publisher":"Elsevier","ec_funded":1,"oa":1,"article_processing_charge":"Yes (via OA deal)","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"article_number":"114353","publication_identifier":{"issn":["0304-3975"]},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","file":[{"file_id":"17263","file_name":"2024_TheorComputerScience_Schmid.pdf","date_created":"2024-07-16T12:02:25Z","relation":"main_file","date_updated":"2024-07-16T12:02:25Z","creator":"dernst","content_type":"application/pdf","checksum":"efd5b7e738bf845312ba53889a3e13e4","access_level":"open_access","file_size":603570,"success":1}],"oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"year":"2024","status":"public","has_accepted_license":"1","corr_author":"1","scopus_import":"1","isi":1,"title":"Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation","language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"19985"}]},"file_date_updated":"2024-07-16T12:02:25Z","volume":989,"keyword":["General Computer Science","Theoretical Computer Science"],"abstract":[{"text":"We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how many nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity on \r\n increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+E) . (1+3)  for some arbitrary E>0.","lang":"eng"}],"day":"21","date_created":"2024-01-16T13:40:41Z","publication":"Theoretical Computer Science","type":"journal_article","acknowledgement":"We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful discussions about different variants of the problem. This work is supported by the European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025, the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant 470029389 (FlexNets), 2021-2024.","citation":{"short":"S. Schmid, J. Svoboda, M.X. Yeo, Theoretical Computer Science 989 (2024).","chicago":"Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>Theoretical Computer Science</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">https://doi.org/10.1016/j.tcs.2023.114353</a>.","ista":"Schmid S, Svoboda J, Yeo MX. 2024. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. 989, 114353.","ama":"Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. 2024;989. doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>","apa":"Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2024). Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">https://doi.org/10.1016/j.tcs.2023.114353</a>","mla":"Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>Theoretical Computer Science</i>, vol. 989, 114353, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>.","ieee":"S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” <i>Theoretical Computer Science</i>, vol. 989. Elsevier, 2024."},"ddc":["000"],"external_id":{"isi":["001168211400001"]},"intvolume":"       989","quality_controlled":"1","author":[{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"last_name":"Svoboda","orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","full_name":"Svoboda, Jakub"},{"orcid":"0009-0001-3676-4809","last_name":"Yeo","first_name":"Michelle X","full_name":"Yeo, Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"doi":"10.1016/j.tcs.2023.114353","_id":"14820","project":[{"grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}]},{"doi":"10.4230/LIPIcs.OPODIS.2023.12","_id":"15007","author":[{"last_name":"Alpos","first_name":"Orestis","full_name":"Alpos, Orestis"},{"first_name":"Ignacio","full_name":"Amores-Sesar, Ignacio","last_name":"Amores-Sesar"},{"last_name":"Cachin","full_name":"Cachin, Christian","first_name":"Christian"},{"orcid":"0009-0001-3676-4809","last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"quality_controlled":"1","arxiv":1,"intvolume":"       286","citation":{"ista":"Alpos O, Amores-Sesar I, Cachin C, Yeo MX. 2024. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 12.","chicago":"Alpos, Orestis, Ignacio Amores-Sesar, Christian Cachin, and Michelle X Yeo. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” In <i>27th International Conference on Principles of Distributed Systems</i>, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.12</a>.","short":"O. Alpos, I. Amores-Sesar, C. Cachin, M.X. Yeo, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"Alpos, Orestis, et al. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” <i>27th International Conference on Principles of Distributed Systems</i>, vol. 286, 12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">10.4230/LIPIcs.OPODIS.2023.12</a>.","ieee":"O. Alpos, I. Amores-Sesar, C. Cachin, and M. X. Yeo, “Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks,” in <i>27th International Conference on Principles of Distributed Systems</i>, Tokyo, Japan, 2024, vol. 286.","apa":"Alpos, O., Amores-Sesar, I., Cachin, C., &#38; Yeo, M. X. (2024). Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In <i>27th International Conference on Principles of Distributed Systems</i> (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.12</a>","ama":"Alpos O, Amores-Sesar I, Cachin C, Yeo MX. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In: <i>27th International Conference on Principles of Distributed Systems</i>. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">10.4230/LIPIcs.OPODIS.2023.12</a>"},"acknowledgement":"We would like to thank Krzysztof Pietrzak and Jovana Mićić for useful discussions. This work has been funded by the Swiss National Science Foundation (SNSF) under grant agreement Nr. 200021_188443 (Advanced Consensus Protocols).\r\n","external_id":{"arxiv":["2307.02954"],"isi":["001585185800012"]},"ddc":["000"],"publication":"27th International Conference on Principles of Distributed Systems","type":"conference","abstract":[{"text":"Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead.","lang":"eng"}],"day":"18","date_created":"2024-02-18T23:01:02Z","file_date_updated":"2024-02-26T10:16:57Z","volume":286,"title":"Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks","language":[{"iso":"eng"}],"isi":1,"scopus_import":"1","has_accepted_license":"1","corr_author":"1","status":"public","year":"2024","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"file":[{"file_id":"15031","relation":"main_file","date_created":"2024-02-26T10:16:57Z","file_name":"2024_LIPICs_Alpos.pdf","date_updated":"2024-02-26T10:16:57Z","success":1,"checksum":"2993e810a45e8c8056106834b07aea92","content_type":"application/pdf","access_level":"open_access","file_size":1505994,"creator":"dernst"}],"alternative_title":["LIPIcs"],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["9783959773089"],"issn":["1868-8969"]},"department":[{"_id":"KrPi"}],"conference":{"start_date":"2023-12-06","name":"OPODIS: Conference on Principles of Distributed Systems","end_date":"2023-12-08","location":"Tokyo, Japan"},"article_number":"12","article_processing_charge":"No","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","month":"01","date_published":"2024-01-18T00:00:00Z","publication_status":"published","date_updated":"2025-12-02T13:38:53Z"}]